ACGO信奥新闻 第36届国际信息学奥林匹克竞赛（International Olympiad in Informatics，IOI2024）将于2024年9月1-8日在埃及举行。CCF组队代表中国参加IOI2024。NOI科学委员会副主席、清华大学韩文弢博士担任领队，NOI科学委员会委员、北京大学罗国杰教授担任副领队，观察员由NOI科学委员会主席、北京大学蒋婷婷教授和NOI科学委员会副主席、北京航空航天大学赵启阳博士担任。他们将带领周康阳（杭州学军中学教育集团文渊中学）、郭羽冲（华东师范大学第二附属中学）、黄洛天（中国人民大学附属中学）和沈吉滪（杭州学军中学教育集团文渊中学）出征埃及，与其他来自五湖四海的选手们同场竞技。

这 不 set 吗

幸福小区的电费计算是有三个阶层， 用电15及以下，每度0.47元。 用电15以上，30及以下的部分，每度0.89元。 用电30以上的部分，每度1元。 现在给你某家一个月的用电量，请问他家这个月要付多少？ 输入格式 输入一个正整数，代表用电度数。 输出格式 输出用电额度，保留两位小数。 输入输出样例 输入#1 复制 3 输出#1 复制 1.41

这是什莫玩意儿

这题也太水了把！ 我直接全题用时最少好吧

正解：

汇总 广度优先搜索（Breadth-First Search，BFS）是另一种常见的图遍历算法，与深度优先搜索不同的是，BFS从起始节点开始，依次访问其所有未访问过的邻居节点，然后逐层向外扩展搜索。 BFS算法步骤： 1. 将起始节点放入队列：将起始节点放入队列中。 2. 标记起始节点为已访问：标记起始节点为已访问。 3. 从队列中取出一个节点：从队列中取出一个节点，访问该节点，并且将其所有未访问过的邻居节点放入队列中。 4. 重复步骤3：重复步骤3，直到队列为空。 示例代码： 让我们继续使用之前的无向图作为示例来说明BFS算法。同样假设有以下图： 我们仍然使用邻接表来表示这个无向图，但这次我们会使用队列来实现BFS算法：（C++） 在这个示例中，我们从节点A开始进行BFS。程序会按照广度优先的顺序访问各个节点，并输出每个节点的名称。通过逐层访问邻居节点，BFS能够探索整个连通图。您可以运行这段代码，并修改图的结构来验证BFS算法的工作原理。 希望这个示例能够帮助您理解广度优先搜索算法的实现及应用。如果您需要更多说明或有任何问题，请随时告诉我！

贪心算法 写在前面 > 贪心是一种思想（策略），不是一种算法！ 贪心算法(greedy algorithm)，又称贪婪算法。 提醒：选择当前局部最优解，不一定全局最优。 贪心要求：无后效性 进制转换(X转10) 1.按照小数点划分左右； 2.小数点往左写上对应权值 3.小数点往右写上对应权值 4.结果=a∗x2+b∗x1+c∗x0+c∗x−1+d∗x−2+e∗x−3a*x^2+b*x^1+c*x^0+c*x^{-1}+d*x^{-2}+e*x^{-3}a∗x2+b∗x1+c∗x0+c∗x−1+d∗x−2+e∗x−3. 位运算 1.按位与 & 按位与&的运算规则，将两个二进制数低位对齐，不足高位补零。对两个数字进行比较，只有当两个相对应的二进制位都为1时，结果相应位才为1，其余为0. x&(x-1)可以快速判断一个数是不是2n2^n2n ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2.按位或 | 按位与|的运算规则，将两个二进制数低位对齐，不足高位补零。对两个数字进行比较，只有当两个相对应的二进制位其中一个为1时，结果相应位才为1，其余为0. ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3.按位非 ~ 按位与~的运算规则，将两个二进制数每一位取反，0变1，1变0. > 应用：~1=0 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4.按位异或^ 按位与|的运算规则，将两个二进制数低位对齐，不足高位补零。对两个数字按位进行比较，当两个相对应的二进制位同时为0时，不同时为1.异或满足交换率：aba=aab ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5.按位右移>> * 按位右移>>的运算规则，>>a就将二进制数右移a位，低位丢弃。 * 右移1相当于x÷2x \div 2x÷2。 * 2n2^n2n ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6.按位左移<< * 按位左移<<的运算规则，<<a就将二进制数左移a位，高位左移，低位补零。 * 左移1相当于x×2x \times 2x×2。 * 2n\sqrt[n]{2}n2 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 例题： 12^32&9|18 A.26 B.30 C.32 D.44 参考答案:B

贪心算法（GREEDY ALGORITHM） 概念 不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 由局部最优解得到全局最优解。 位运算 X进制转十进制 abc.deabc.deabc.de转十进制=$ ax2+bx1+cx0+dx-1+dx^-2 $ 二进制常见位运算 1.按位与& 2.按位或| 3.按位非~ 4.按位异或^ 5.按位右移>> 6.按位左移<< 优先级 单目运算符>双目运算符 ~ (单目运算符) << >> & ^ |

贪心算法（GREEDY ALGORITHM） 在对问题求解时，总是做出在当前看来是最好的选择，最终得到的是某种意义上的局部最优解。 它没有固定的模板，重要的是贪心策略的选择 后效性 指当前决策会影响后续决策，这种情况下不能用贪心。 结构体排序 定义cmp函数，或者在结构体中加上 二进制转十进制 1.按照小数点划分左右 2.小数点往左右分别写上对应权值 3.结果=a1*xn+a2*x(n-1)+......+a(n-1)*x1+an*x0+a(n+1)*x-1+......+a(2n)*x-n 二进制位运算 按位与：& 将两个二进制数低位对齐，高位补0，当两位同时为1时为1，否则为0。 按位或：| 将两个二进制数低位对齐，高位补0，当两位同时为0时为0，否则为0。 按位非：~ 将一个二进制数每一位取反 按位异或：^ 将两个二进制数低位对齐，高位补0，当两位相同时为0，否则为1。 按位左移：>> 将一个二进制数集体左移，高位舍弃，空位补0。 按位右移：<< 将一个二进制数集体右移，低位舍弃。 运算优先级：~ > 左移右移 > & > ^ > |

贪心 并不是一种算法，是策略 带有“greedy”标签：贪心题 贪心没有固定模板，重要的是贪心策略的选择 X进制转十进制 小数点往左写上对应权值； 小数点往右写上对应权值； 结果等于所有次方结果相加 #位运算 1.按位与& 同位同时为‘1’才为1； 2.按位或| 同位同为0为0，其余为1； 3.按位非 将二进制每一位取反 ~（-1）=0 4.按位异或^ 相同时为1，不同为0 5.按位右移>> 右移等于整除2 6.按位左移<< 左移等于乘以2

第三课 1.贪心 英文：greedy 不从整体最优上考虑，算法得到的是某种意义上的局部最优解 贪心算法没有固定的模板，重要的是贪心策略的选择 结构体排序 后效性 前面的贪心决策会影响后面的贪心决策 因此 没有后效性才能使用贪心算法 2.任意进制转十进制 x进制：abc.cde 结果：a∗x2+b∗x1+c∗x0+c∗x−1+d∗−2+e∗x−3a*x^2+b*x^1+c*x^0+c*x^-1^+d*^-2+e*x^-3a∗x2+b∗x1+c∗x0+c∗x−1+d∗−2+e∗x−3 3.位运算 1.按位与& 按位与&的运算规则，将两个二进制低位对齐，不足高位补零。对两个数字进行比较，只有当两个相应的二进制位都为1时，结果的相应位才为1，其余为0. 例如：计算7&10 0111&1010=0010 应用：x&(x-1)=0 是否为2的幂次 2.按位或| 按位或|的运算规则，将两个二进制低位对齐，不足高位补零。对两个数字进行比较，只有当两个相应的二进制位都为0时，结果的相应位才为0，其余为1. 例如：计算6|10 0110|1010=1110 3.按位非~ 按位非·~的运算规则，将一个二进制每一位取反，0变1，1变0. 例如：计算~6 ~0110=1001 注意：1.按位非运算会修改符号位，因此与实际结果不一致 2.~-1=0 4.按位异或^ 按位异或^的运算规则，将两个二进制低位对齐，不足高位补零。对两个数字进行比较，当两个位相同时为0，不同时为1 5.按位右移>> 按位右移>>的运算规则，>>a就将二进制右移a位，高位丢弃，低位补零 相当于除二 6.按位左移<< 按位右移<<的运算规则，<<a就将二进制左移a位，高位丢弃，低位补零 相当于乘二 7.运算优先级 1.按位非~ 2.左移右移 3.按位与& 4.按位异或^ 5.按位或|

AKSZ-算法第三课 贪心 贪心不是一种算法！！！！ （greedy）又称贪婪算法，在问题求解每一步时，求局部最优解 贪心算法一定要推导至局部最优解可达到全局最优解 贪心没有固定的模板，更重要的是贪心策略 X进制转十进制 按权展开法 1、按照小数点划分左右 2、小数点往左又写上对应权值 3、结果=a∗X2+b∗X1+c∗X0+c∗X−1a*X^2+b*X^1+c*X^0+c*X^-1a∗X2+b∗X1+c∗X0+c∗X−1 位运算 所有的东西都按二进制操作 按位 & 7&10= 0111 &1010 =0010 x&(x-1)可以快速判断一个数是不是2n2^n2n | 7|10 =0111 |1010 =1111 ~ ~6 =~0110 =1001 反码： x但第一位不变~x但第一位不变 x但第一位不变 补码：反x+1反x+1反x+1 ^ 相同为零，不同为一 << x<<1==x*2 x<<n=x左移n位 左移一次乘二 (1<<n)-1=全集和 >> n>>1==n/2 右移一位，高位补零 右移一次除以二 优先级 ~ > << = >> > & > ^ > |

#NO3.贪心“算法”:greedy algorithm ###不是算法是(思想策略) **贪心算法无法推出全局最优解，只可求出局部最有解 ** 结构体排序 P1056 派座椅 ##位运算 ###按位与 "&" 同为1为1，否则为0 ps:7&10 0111 1010 ——— 0010 x&(x-1) = 0 -->是二的次方 ###按位或 "|" 同为0为0，否则为1 6|10 0110 1010 ——— 1110 ###按位非 "~" 0变1，1变0 ~6 0110 ——— 1001 ~-1 = 0 ###按位异或 "^" 相同时为0，不同时为1 5^9 0101 1001 ——— 1100 a^a = 0 ###按位右移 ">>" 右移，高位丢弃，低位补零 9>>1 1001 ——— 0100 1 相当于整除2 ###按位左移 "<<" 右移逆运算，相当于乘2 优先级： ~ (单目) << >> （算数） & （逻辑） ^ | 1.截止时间排序 c[i]+cost>d[i] 不能修 c[i]+cost<=d[i] 能修 1.如何保存 优先队列 堆

贪心算法 简介 贪心算法（greedy algorithm），在对问题求解时，总是做出在当时看是最好的选择。 得到某种意义上的局部最优解。 贪心算法没有固定的模板重要在于贪心策略的选择。 进制 按权展开法 abc.cde=a∗x2+a∗x2+a∗x2+a∗x2+a∗x2+a∗x2abc.cde = a*x^2+a*x^2+a*x^2+a*x^2+a*x^2+a*x^2 abc.cde=a∗x2+a∗x2+a∗x2+a∗x2+a∗x2+a∗x2 位运算 常见位运算 运算优先级

贪心算法 贪心算法_（greedy algorithm，又称贪婪算法）_是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。 贪心算法没有固定的模板。 常见位运算符 * 按位与 &：按位与运算符“&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位都为1时，结果位才为1。参与运算的两个数均以补码出现。 * 按位或 |：按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1时，结果位就为1。当参与运算的是负数时，参与两个数均以补码出现。 * 按位非 ~：对该整数的二进制形式逐位取反，参与两个数均以补码出现。 * 按位异或 ^：将两个二进制数低位对齐，不足高位补零。对两个数字按位进行比较，当两个位相同时为零，不同时为1。 * 按位左移 <<：>>a就将二进制数左移a位，高位丢弃，低位补零。 * 按位右移 >>：>>a就将二进制数右移a位，高位补零，低位丢弃。 ##优先级 逻辑运算符<位运算符

很简单，不多说

哈士瓦欸得睡

进制转换 枚举算法 1.三要素：枚举对象，枚举范围，判定条件。 计时程序： clock_t start,end; ... start=clock(); ... end=clock(); printf("%.2lf Ms",double(end-start)/CLOCKS_PER_SEC*1000); 埃氏筛时间复杂度 O(n loglogn).