0.前言 也是被我同学鄙视了好吧！！！ 那么，从今天开始，我要认真学数学了。最近数学社团在讲 sigmasigmasigma，那就写一篇关于 sigmasigmasigma 的介绍吧。 希望大家积极点赞 1.SIGMA的由来 sigmasigmasigma(表示为 ΣΣΣ)是希腊字母表中的第 181818 个字母，在数学中被用来表示 “求和”。 想象一下，如果要计算 1+2+3+4+51+2+3+4+51+2+3+4+5，虽然不难，但如果要计算 1+2+3+……+10001+2+3+……+10001+2+3+……+1000，逐个书写就太麻烦了。这时，sigmasigmasigma 符号就能派上大用场，用它可以把长长的加法算式浓缩成一个简洁的表达式。 2.SIGMA的理解 在写法上的理解 sigmasigmasigma 的基本写法是：∑i=abf(i)\sum_{i=a}^{b} f(i)∑i=ab f(i)，其中： ΣΣΣ是 $igma $ 符号，代表 “总和”； iii 是求和变量，也叫 “索引”，可以是任何字母，常见的有 i,j,ki,j,ki,j,k等； aaa 是下限，表示求和开始时变量的值； bbb 是上限，表示求和结束时变量的值； f(i)f(i)f(i)是求和表达式，表示每个项的计算规则。 整个表达式的意思是：当变量 iii 从 aaa 开始，每次增加 111，一直到 bbb 时，将所有f(i)f(i)f(i)的值加起来。 在C++中的理解 我们可以把 sigmasigmasigma 函数当作 forforfor循环，进行一系列累计，具体见下面的代码。 3.SIGMA的用法 基本用法：简单数列求和 最基础的 sigmasigmasigma 用法是计算连续整数的和。例如，∑i=15i\sum_{i=1}^{5} i∑i=15 i，这里下限 a=1a=1a=1，上限 b=5b=5b=5，表达式f(i)=if(i)=if(i)=i，它表示的就是 1+2+3+4+5，计算结果为 15。 再比如，∑k=36k\sum_{k=3}^{6} k∑k=36 k，就是 3+4+5+63+4+5+63+4+5+6，结果是 181818。 表达式含常数的求和 当求和表达式中出现常数时，计算方法也很简单。比如 ∑i=143\sum_{i=1}^{4} 3∑i=14 3，表示有 444 个 333 相加，即3+3+3+3=123+3+3+3=123+3+3+3=12。这里可以总结出一个规律：∑i=abc=c×(b−a+1)\sum_{i=a}^{b} c = c \times (b - a + 1)∑i=ab c=c×(b−a+1)，其中 ccc是常数，(b−a+1)(b−a+1)(b−a+1)是项数。 表达式含变量倍数的求和 如果表达式是变量的倍数，如∑i=132i\sum_{i=1}^{3} 2i∑i=13 2i，它表示的是 2×1+2×2+2×3=2+4+6=122×1 + 2×2 + 2×3 = 2 + 4 + 6 = 122×1+2×2+2×3=2+4+6=12。也可以把倍数提到 sigmasigmasigma 外面，即2×∑i=13i=2×(1+2+3)=2×6=122\times\sum_{i=1}^{3} i = 2\times(1 + 2 + 3)=2\times6=122×∑i=13 i=2×(1+2+3)=2×6=12，结果是一样的。 多个表达式的求和 当 sigmasigmasigma 的表达式是多个项的和或差时，可以拆分成多个 sigmasigmasigma 的和或差。例如∑i=12(i+2i2)\sum_{i=1}^{2} (i + 2i^2)∑i=12 (i+2i2)，可以拆分为∑i=12i+∑i=122i2\sum_{i=1}^{2} i + \sum_{i=1}^{2} 2i^2∑i=12 i+∑i=12 2i2。 先计算∑i=12i=1+2=3\sum_{i=1}^{2} i = 1 + 2 = 3∑i=12 i=1+2=3；再计算 ∑i=122i2=2×12+2×22=2+8=10\sum_{i=1}^{2} 2i^2 = 2×1^2 + 2×2^2 = 2 + 8 = 10∑i=12 2i2=2×12+2×22=2+8=10；最后相加得 3+10=133 + 10 = 133+10=13，和直接计算 (1+2×12)+(2+2×22)=(1+2)+(2+8)=3+10=13(1 + 2×1²)+(2 + 2×2²)= (1 + 2)+(2 + 8)=3 + 10=13(1+2×12)+(2+2×22)=(1+2)+(2+8)=3+10=13结果一致。 进阶用法：双重 SIGMA 求和 双重 sigmasigmasigma 是指存在两个求和变量的情况，形如∑i=ab∑j=cdf(i,j)\sum_{i=a}^{b}\sum_{j=c}^{d}f(i,j)∑i=ab ∑j=cd f(i,j)，表示先固定 iii 的值，对 jjj 从 ccc 到 ddd 的所有 f(i,j)f (i,j)f(i,j) 求和，再将得到的结果对 iii 从 aaa 到$ bbb 求和。 例如∑i=12∑j=12(i+j)\sum_{i=1}^{2}\sum_{j=1}^{2}(i + j)∑i=12 ∑j=12 (i+j)，先计算 i=1i=1i=1 时，jjj 从 111 到 222 的和：(1+1)+(1+2)=2+3=5(1+1)+(1+2)=2+3=5(1+1)+(1+2)=2+3=5；再计算 i=2i=2i=2 时，jjj 从 111 到 222 的和：(2+1)+(2+2)=3+4=7(2+1)+(2+2)=3+4=7(2+1)+(2+2)=3+4=7；最后将两个结果相加，5+7=125+7=125+7=12。 变量步长不为 1 的求和 之前我们接触的求和变量都是每次增加 1，其实变量的步长可以是其他数值。比如∑i=1i+=25i\sum_{\substack{i=1 \\ i+=2}}^{5}i∑i=1i+=2 5 i，这里 iii 从 111 开始，每次增加 222，到 555 结束，它表示的是 1+3+5=91+3+5=91+3+5=9。 含分式的求和 当表达式中含有分式时，计算过程稍显复杂，但原理不变。例如∑i=13ii****um_{i=1}^{3}\frac{i}{i + 1}∑i=13 i+1i ，分别计算每一项： i=1i=1i=1时，11+1=12\frac{1}{1+1}=\frac{1}{2}1+11 =21 i=2i=2i=2时，22+1=23\frac{2}{2+1}=\frac{2}{3}2+12 =32 i=3i=3i=3时，33+1=34\frac{3}{3+1}=\frac{3}{4}3+13 =43 求和，12+23+34=612+812+912=2312\frac{1}{2}+\frac{2}{3}+\frac{3}{4}=\frac{6}{12}+\frac{8}{12}+\frac{9}{12}=\frac{23}{12}21 +32 +43 =126 +128 +129 =1223 . 4.SIGMA在C++中的例题 题目传送门 题目描述 给定一个长度为 NNN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)A=(A1 ,A2 ,…,AN )。定义 f(l,r)f(l,r)f(l,r) 如下： * f(l,r)f(l,r)f(l,r) 表示区间 (Al,Al+1,…,Ar−1,Ar)(A_l,A_{l+1},\ldots,A_{r-1},A_{r})(Al ,Al+1 ,…,Ar−1 ,Ar ) 中不同数的个数。 请计算下式的值： ∑i=1N∑j=iNf(i,j)\sum_{i=1}^{N}\sum_{j=i}^N f(i,j) i=1∑N j=i∑N f(i,j) 输入格式 输入以如下格式从标准输入中给出。 > NNN A1A_1A1 A2A_2A2 …\ldots… ANA_NAN 输出格式 请输出答案。 输入输出样例 #1 输入 #1 输出 #1 输入输出样例 #2 输入 #2 输出 #2 限制条件 * 1≤N≤2×1051\leq N\leq 2\times 10^51≤N≤2×105 * 1≤Ai≤N1\leq A_i\leq N1≤Ai ≤N * 输入的所有数均为整数 样例解释 1 以 f(1,2)f(1,2)f(1,2) 为例，(A1,A2)=(1,2)(A_1,A_2)=(1,2)(A1 ,A2 )=(1,2)，其中不同的数有 222 个，所以 f(1,2)=2f(1,2)=2f(1,2)=2。再看 f(2,3)f(2,3)f(2,3)，(A2,A3)=(2,2)(A_2,A_3)=(2,2)(A2 ,A3 )=(2,2)，其中不同的数有 111 个，所以 f(2,3)=1f(2,3)=1f(2,3)=1。fff 的总和为 888。 分析 ABC371E 对于每个区间，如果有重复的数，我们认为最早出现的那个数有贡献。 例如 1,2,3,4,1,4,51,2,3,4,1,4,51,2,3,4,1,4,5 中，第 1,2,3,4,71,2,3,4,71,2,3,4,7 个数对答案有贡献。 统计每个数对答案的贡献即可。 我们设 jjj 为满足 aj=aia_ j=a_iaj =ai 且 j<ij<ij<i 的最大值（若不存在为 000），那么aia_iai 的贡献就是 (i−j)×(n−i+1)(i−j)×(n−i+1)(i−j)×(n−i+1)，其中 (i−j)(i−j)(i−j) 为左端点的可能数，(n−i+1)(n−i+1)(n−i+1) 为右端点的可能数。 5.完结撒花 @AC君 求加精 @洛谷：姚昕辰,看到没有！！！ 怎么只有3个赞QAQ，大家加吧劲

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 看了别人的题解后我自愧不如，所以我又在原题解上做了一点点的修改（包括T4的代码，请放心食用） T1 午枫的切蛋糕 个人难度：入门|考察内容：分支结构 由题意得，要沿着直径或者半径平分成（n+1）块蛋糕。不难看出，如果（n+1）是偶数，就能沿着直径切（因为直径只能平均切成2份，所以只能为2的倍数），否则要沿着半径切。但是我们会发现n是大于等于0的，所以（n+1）可能会等于1，因为整个蛋糕已经是1份，所以无需再切。 代码如下： T2 午枫的卡片游戏 个人难度：入门|考察内容：排序 这道题要我们比较卡片点数大小，虽然小枫的出牌顺序已经固定，但是答案不会因为将位置改变而发生变化，所以我们可以先用两个数组存放卡牌点数并升序排序，如果小午的牌大于小枫的牌，那么就将小午胜的局数加一并弃掉小午和小枫的牌，否则只弃掉小午的牌并让小午的下一张牌和小枫当前的牌比较。 代码如下： T3 午枫的分割数组 个人难度：入门|考察内容：贪心 既然要数量最多的数的大小，那我们可以直接只选数组中最大的一个数，因为是小午将数组切分成前后两部分，所以可以“邪恶地”只给小枫数组最后一个数，如果第1~n-1个数没有大于第n个数的数（注意，这里是大于），就输出“NO”。 代码如下： T4 小午的构造 个人难度：普及-|考察内容：模拟 仔细观察后就会发现，ac,aa,wa三个单词都含a，所以需要多增一个变量wordx并一直重复以下操作： 如果 x > y+z+wordx : wordx++; x--; 结束后又出现了一个问题，如果还剩一个a呢？题目中要wa的数量尽可能少并且还要在最多单词的情况下，所以我们可以把一个wa拆开: wa a->w a a->w aa 这样就需要再做一次判断： 如果 x < y+z+wordx 并且 z>0 : z--; 最后输出，x > y+z 的情况就完成了。 接着再来考虑 y+z > x >y 的情况，如果a的数量大于c，那么a的数量就是能组成的最多单词数，wa的数量就是a减去c的数量。 最后剩下了 x < y 的情况，那么最多只能输出a的数量，输出 x 和 0 。 代码如下： T5 午枫的MEX 个人难度：入门|考察内容：位运算 这道题需要先列一个表格： n 1 2 3 4 5 6 7 8 答案 1 4 4 8 8 8 8 16 答案看上去就是2log2(n)+1,但是我们会发现一个特殊情况，在1的时候输出的是1，所以需要一个判断。 代码如下： 答案虽然已经分析出来了，但是背后的原理我们也可以分析一下（如果不感兴趣可以直接跳过） 因为是异或，所以位数只减不增，我们随便举一个二进制数做例子： 1010100011 那么能使它变成最大的数就是取反之后的数： 0101011100 因为每个数取反后都会比原数小，所以取反的数就无需考虑，最后的最大值+1就是2log2(n)+1。 那么为什么1的答案是1呢？因为1只有它自己能异或，而自己异或自己的答案是0，所以最大值+1=1。 T6 午枫的陪伴时间 个人难度：普及/提高-|考察内容：贪心，动态规划 这一道题让我们选择小午的要求并计算最少花费，在n项要求中可能会有重复的日期，所以我们先需要算出一日的最少花费： 我们先举个例子： 陪之前 陪之后 省了多少钱 15 13 2 21 18 3 （这个省的最多，选这个） 1000 2000 -1000 1111 1111 0 接着再用动态规划解决多日的最少花费： 代码如下： 以上是全部内容，如果觉得哪里可以优化或更正可以在评论区留言（qwq）

广度优先搜索精讲 什么是广度优先搜索？ 广度优先搜索（英文:Breadth First Search，简称 bfs），又称宽度优先搜索，是一种搜索算法。顾名思义，就是更大范围内搜索，先访问完当前顶点的所有邻接点，然后再访问下一层的所有节点，该算法适用于解决最短、最小路径等问题。 广度优先搜索使用队列实现，每次将周围的邻接点加入队列，逐层搜索。 广度优先搜索因为其采用层级遍历，像洪水一样逐层扩散，无需重复访问、无需回溯，所以较深度优先搜索的指数级时间复杂度的效率有着显著提升。 广度优先搜索的原理和实现 广度优先搜索的步骤 广度优先搜索通过队列实现，将起始点加入队列，然后只要队列不为空，对于合法的邻接点加入队列，一层一层的进行遍历。 例如对于一个无向图，有 (1,2)(1,2)(1,2) ,(1,3)(1,3)(1,3) , (3,4)(3,4)(3,4), (2,4)(2,4)(2,4) 四条边。广度优先搜索的步骤如下： * 定义一个队列 qqq，用于维护当前待处理的节点； * 从 111 开始搜索，将 111 节点加入队列 qqq； * 111 的邻接边有 (1,2)(1,2)(1,2) 和 (1,3)(1,3)(1,3) ，然后将节点 222 和 333 加入队列 qqq，将节点 111 退出队列； * 然后对于节点 222 ，它的邻接边有 (1,2)(1,2)(1,2) 和 (2,4)(2,4)(2,4) ，因为节点 111 已被访问过，跳过，将节点 444 加入队列 qqq， 将节点 222 退出队列； * 对于节点 333，它的邻接边有 (1,3)(1,3)(1,3) 和 (3,4)(3,4)(3,4) ，但是节点 111 和 444 都已被访问，跳过； * 对于节点 444，它的邻接边有 (2,4)(2,4)(2,4) 和 (3,4)(3,4)(3,4)，但是节点 222 和 333 都已被访问过，跳过； * 队列空了，遍历结束。 广度优先搜索模版代码 题目练习 迷宫类问题 A8036.走迷宫 这道题是一个经典的迷宫问题，相对与用 dfs 算法，bfs 算法效率更高。 这道题中，角色要在 n×mn \times mn×m 的地图里走路，每次只能向上下左右走 111 格，并且只有.的位置才能走。 对于这类题型，我们可以用 dx 和 dy数组记录运动轨迹，每次遍历 dx ， dy 数组，移动到对应位置。 注意：对于走迷宫类题型需要注意当前位置是否合法，即是否满足当前位置不越界，当前位置可以走。 代码： 预期分数： 100pts100pts100pts 时间复杂度： O(nm)⁡\operatorname{O(nm)}O(nm) 空间复杂度：O(nm)⁡\operatorname{O(nm)}O(nm) 连通块问题 A8040.细胞 本题目是一道经典的连通块问题。 这道题具有一定思维含量，可以通过循环遍历，对于每个不属于其他连通块的格子（visi,jvis_{i,j}visi,j === 000）通过 bfs 搜索确定大小并标记所属的格子，最后记录有多少个连通块。 代码： 预期分数：100pts100pts100pts 时间复杂度：O(nm)⁡\operatorname{O(nm)}O(nm) 空间复杂度：O(nm)⁡\operatorname{O(nm)}O(nm) 课后作业 必做 * 复习 dfs 的逻辑，找一找 bfs 和 dfs的不同之处。 * 将之前 dfs 的题想想可不可以用 bfs 优化 * 完成连通块问题，图的遍历，迷宫问题普及难度题目各 222 道 选做 * 分析对于不同题目下 bfs 的优化和时间复杂度，尝试利用剪枝等方法提升效率。 * 学习更多题型，练习 333 道以上，并借助题解理解他人解法； * 做 101010 道搜索提高题 感谢大家的观看！ @AC君 我要加精华

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的切蛋糕 入门 T2 午枫的卡片游戏 普及- T3 午枫的分割数组 普及- T4 小午的构造 普及- T5 午枫的mex 普及/提高- T6 午枫的陪伴时间 普及+/提高 T1 午枫的切蛋糕 题目大意 有 n+1n+1n+1 个人分蛋糕，蛋糕可以沿着直径或半径切开，问平均分配最少需要切几刀。 解题思路 因为需要平均分且切蛋糕时只能沿着直径或者半径切开，所以我们可以考虑人数的奇偶性。 如果有偶数个人分蛋糕，则每一刀可以沿着直径切开；如果有奇数的人分蛋糕，则每一刀只能沿着半径切开。 注意总人数为 n+1n+1n+1 人，当只有一个人的时候，不需要切蛋糕。 时间复杂度 O(1)O(1)O(1) 参考代码 T2 午枫的卡片游戏 题目大意 双方都有 nnn 卡片，小枫告诉了小午自己的出牌顺序，双方进行比较点数，如果小午点数大本轮小午获胜，否则小枫获胜。求最终谁的胜场多。 解题思路 我们可以通过“田忌赛马”的思想，用自己尽量小点数的卡片和对方尽量大点数的卡片进行比较，最大化的减少敌方战力的同时最小化减少己方战力。让我们赢的时候尽量也选取最接近对方点数的卡片。 因此原本的卡片顺序已经不重要了，我们可以将双方的卡片排序，通过双指针模拟比较双方的点数。 时间复杂度 O(nlogn)O(nlogn)O(nlogn) 参考代码 T3 午枫的分割数组 题目大意 小午可以将一个数组分成前后两部分，第一部分给小午，第二部分给小枫，之后小午和小枫分别可以在各自的数组中选取 k1k_1k1 和 k2k_2k2 个数，然后比较两人选出的数的众数，大的一方获胜。判断小午是否可以获胜。 解题思路 题目中所选的数中数量最多的数称为众数，以下都称众数。 考虑当前有一个数组，最多选 kkk 个数，如何让选出来的数的众数最大，显然，我们只要选一个最大的数即可。 那么对于小午来说，他需要让小枫拿到的数尽可能少，因为小枫拿到越少的数，能选出比小午大的数的可能就更小。所以小午的最优选择一定是把前 n−1n-1n−1 个数分给自己，最后一个数分给小枫。 时间复杂度 O(n)O(n)O(n) 参考代码 T4 小午的构造 题目大意 有 a 、c 、w 三个字母若干个，有 ac 、wa 、aa 三种组合，求最多能得到多少组合，并且在得到最多组合的情况下，wa 的个数最少是多少? 解题思路 首先考虑组合出最多数量的单词：由于 c 和 w 只会被用于组成 ac 和 wa ，所有我们优先消耗 c 和 w ，最后剩下的 a 两两组合。 再来考虑如何让 wa 的个数尽量少： * 在消耗 c 和 w 的情况下，我们一定优先消耗 c ，再消耗 w ； * 当 w 被消耗完且 a 两两组合成 aa ，a 还有剩余时，我们可以将 wa 拆开，用其中的 a 去和剩余的 a 组合。 对于上述第二点，我们会发现最终如果有 a 剩余，那么一定只会剩下一个 a ，所有我们最后要拆 wa 时也只会拆一个，那么我们只需要判断组合完 ac 之后的 a 和 w 的奇偶性就可确定是否需要拆 wa 。 参考代码 T5 午枫的MEX 题目大意 求 mex{i⊕j∣i∈[1,n],j∈[1,n]}mex\{i\oplus j \mid i\in [1,n],j\in[1,n] \}mex{i⊕j∣i∈[1,n],j∈[1,n]} . 解题思路 通过打表，善于观察的同学可能会发现一定规律：{1,n≤22⌈log⁡n⌉,n>2\begin{cases} \begin{aligned} 1,n\leq 2\\ 2^{\lceil\log{n}\rceil},n>2 \end{aligned} \end{cases}{1,n≤22⌈logn⌉,n>2 。 证明：对于 nnn 的最高位 111，仅保留这一位 111，对于低位可以任取，此时覆盖了 nnn 最高位为 111 的所有情况；然后 nnn 的最高位 111 这一位为 000，次高位为 111，对于低位可以任取，此时覆盖了 nnn 次高位为 111 的所有情况。依次类推，所以最小的不能被表示的就是 2⌈log⁡n⌉2^{\lceil\log{n}\rceil}2⌈logn⌉，n=1,2n=1,2n=1,2 特判。 时间复杂度 O(Tlogn)O(Tlogn)O(Tlogn) 参考代码 T6 午枫的陪伴时间 题目大意 有 nnn 个开始陪伴的时间，每次陪伴必续连续陪 ttt 天，期间不能进行别的陪伴的任务，如果陪伴需要花费 costcostcost 元，否则需要花费 valvalval 元，求最少花费。 解题思路 首先我们可以考虑按照 aia_iai 从小到大排序，然后考虑通过DP如何解决。 设 dpi,0dp_{i,0}dpi,0 表示前 iii 个选项，其中没选第 iii 项的最小花费； dpi,1dp_{i,1}dpi,1 表示前 iii 个选项，其中选择了第 iii 项的最小花费。 其中 dpi,0dp_{i,0}dpi,0 的状态转移很简单： dpi,0=min(dpi−1,0,dpi−1,1)+vidp_{i,0}=min(dp_{i-1,0},dp_{i-1,1})+v_idpi,0 =min(dpi−1,0 ,dpi−1,1 )+vi 。 令 sis_isi 为 viv_ivi 的前缀和，pospospos 为 iii 左侧第一个小于 ai−ma_i-mai −m 的下标。那么 dpi,1dp_{i,1}dpi,1 的状态转移为：dpi,1=min(dppos,0,dppos,1)+si−1−spos+costidp_{i,1}=min(dp_{pos,0},dp_{pos,1})+s_{i-1}-s_{pos}+cost_idpi,1 =min(dppos,0 ,dppos,1 )+si−1 −spos +costi 最后答案取 dpi,0dp_{i,0}dpi,0 和 dpi,1dp_{i,1}dpi,1 的最小值即可。 参考代码

T1.午枫的切蛋糕 题目大意 小枫有n个朋友，加上自己共n+1人，需要将蛋糕平均分成n+1份，每刀沿直径或半径切，求最少刀数。 题目思路分析 总人数m = n+1，如果m=1，无需切刀输出0。如果m为偶数，沿直径切m/2刀，每刀分两份，可平均分。如果m为奇数，沿半径从中心切m刀，直接分m份。代码通过判断m的奇偶性直接计算结果。 易错点注意 注意n=0时m=1，输出0而非其他。边界如n=1（m=2，偶，输出1）需验证奇偶逻辑正确。 AC代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2.午枫的卡片游戏 题目大意 小枫卡片顺序固定为a[0..n-1]，小午卡片b可任意排列，每轮比大小，相同算小枫胜，求小午能否胜超过n/2轮（严格多数）。 题目思路分析 将a和b升序排序，从大到小匹配：用小午的最大b[j]尝试赢小枫的最大未匹配a[i]，若b[j]>a[i]则小午胜一轮，同时i--,j--，否则只i--丢弃a[i]。统计胜轮c，若c >= n/2 +1则YES否则NO。此贪心确保小午用最小必要的大牌赢最多轮。 易错点注意 注意相同算小枫胜，故比时严格>才计小午胜。n=1时n/2+1=1，需仔细检查边界。 AC代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3.午枫的分割数组 题目大意 将数组v分割成前后两非空部分，小午前小枫后，各选<=k1/k2个数，最优使各自子集中频率最高数的数值最大，求小午是否一定胜（其值>小枫值）。 题目思路分析 由于k1,k2>=1，各部分最优频率最高数的值即部分最大值（选只含最大值的子集即可）。计算前缀最大p[i]（0到i的最大）和后缀最大s[i]（i到n-1的最大）。遍历分割点i=0到n-2，若存在p[i] > s[i+1]则小午取前获胜，输出YES否则NO。 易错点注意 注意分割必须非空，故i<n-1。数组索引从0，p[0]=v[0],s[n-1]=v[n-1]需正确初始化。 AC代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4.小午的构造 题目大意 用x个a、y个c、z个w构造ac、aa、wa三种单词，最大化单词数m，并在m最大下最小化wa数。 题目思路分析 先用min(x,y)做ac，剩余ra = x - min(x,y)个a。最大wa为mw = min(ra,z)，最大m = ac + mw + (ra - mw)/2（剩余a做aa）。从wa=0到mw枚举，计算m = ac + wa + (ra - wa)/2，找到首个达最大m的wa作为最小wa。 易错点注意 注意ra - wa须偶数才能全做aa，否则/2 floor。T<=1e5，x,y,z<=100，枚举wa<=100高效。 AC代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5.午枫的MEX 题目大意 求mex{i ⊕ j | i ∈ [1, n], j ∈ [1, n]}，多组查询n<=1e18。 题目思路分析 对于n<=2，直接输出1（验证集合缺1或为{0,3}缺1）。对于n>2，i xor j范围[0,2n-1]内，集合覆盖[0,2k2^k2k -1]其中2k2^k2k > n-1的最大幂，mex为2k2^k2k（floor(log2(n-1))+1位）。代码计算n-1的最高位k+1，输出1LL<<k。 易错点注意 n=1或2特殊处理，避免log2(0)未定义。n=1e18用ll，移位小心溢出。 AC代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6.午枫的陪伴时间 题目大意 n选项Each从aia_iai 起连续t天陪伴，costicost_icosti ，或不选买v_i礼物；选后[aia_iai ,aia_iai +t-1]内其他选项不可选，求最小总花费。 题目思路分析 初始花费s = sum viv_ivi （全买礼物）。每个选项收益w = viv_ivi - costicost_icosti ，若w>0更新起始d=a_i的最大b[d]。用dp f[i]表示前i个起始日最大收益：f[i] = max(f[i-1], f[i-t] + max(0,b[i]))，避免重叠。最终花费s - f[m]，m=n-t+1。 易错点注意 aia_iai <=n-t+1，b[1..m]。dp索引从1，f[0]=0，i-t>=0检查。 AC代码

ACGO欢乐赛第53场全题解\color{#FFC800}ACGO欢乐赛第53场全题解 ACGO欢乐赛第53场全题解 T1.早起 > 思路分析：判断小明是否迟到。周一到周五（星期1~ 5）需要7点及之前起床，周六周日（星期6~7）可以赖床。因此，如果今天是周一到周五且起床时间晚于7点，则输出YES（迟到），否则输出NO。 时间复杂度：O(1)时间复杂度：O(1)时间复杂度：O(1) 空间复杂度：O(1)空间复杂度：O(1)空间复杂度：O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2.小明的期末复习 > 思路分析：将复习时间D小时转换为外星时间单位。从最小单位开始逐级转换： > > 1. 小时数 = d % c > 2. 总天数 = d / c > 3. 剩余天数 = 总天数 % b > 4. 剩余月数 = (总天数 / b) % a > 5. 年数 = 总天数 / (a*b) 时间复杂度：O(1)时间复杂度：O(1)时间复杂度：O(1) 空间复杂度：O(1)空间复杂度：O(1)空间复杂度：O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3.小明的视疲劳回文串 > 思路分析：不区分大小写判断回文串。遍历字符串前半部分，将对应字符转为小写后比较： > > * 若s[i]与s[n-1-i]的小写形式不同，则需修改（计数+1） > * 当修改次数 ≤ m 时输出YES，否则NO 时间复杂度：O(n)时间复杂度：O(n)时间复杂度：O(n) 空间复杂度：O(1)空间复杂度：O(1)空间复杂度：O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4.求奇数和 > 思路分析：奇数和=奇+偶。寻找： > > 1. 最大奇数（mx1） > 2. 最大偶数（mx2） > 若两者均存在，则和为最大值；否则输出-1。 时间复杂度：O(n)时间复杂度：O(n)时间复杂度：O(n) 空间复杂度：O(n)空间复杂度：O(n)空间复杂度：O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5.小明的斜线总和 > 思路分析：左上到右下的斜线特征：行号-列号为定值。用偏移数组D[K]存储斜线和（K=I-J+M-1保证非负）。遍历所有斜线求最大和。 时间复杂度：O(n×m)时间复杂度：O(n×m)时间复杂度：O(n×m) 空间复杂度：O(n+m)空间复杂度：O(n+m)空间复杂度：O(n+m) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6.小明和论坛发帖 > 思路分析：检查每个单词是否包含任意暴戾性子串。对每个单词S，遍历所有暴戾性字符串B[J]，若S.FIND(B[J])能找到子串，则标记为违禁词。 时间复杂度：O(n×m×L)时间复杂度：O(n×m×L)时间复杂度：O(n×m×L)（L为平均单词长度） 空间复杂度：O(m)空间复杂度：O(m)空间复杂度：O(m)（存储暴戾性字符串）

📋 ACGO社区帮助手册 🌟 站务汇总 * 站务汇总 🏆 赛事信息 * 巅峰排行榜规则介绍 * 排位分机制揭秘 🗨️ 讨论区指南 * 发帖规范 * 删帖原因 团队招募帖子通常不应发布在“学习讨论”板块； 发布无意义内容； 发布违反社区规范的内容； 发布格式混乱，难以阅读的题解，不符合题解规范的题解。 📘 格式手册 * LaTeX数学公式语法 * Markdown语法教程 🤔 提问与解答 * 提问的智慧 * 题解编写技巧 🤖 AC助手使用指南 * AC助手的正确食用方法 🧠 知识点精华贴 * 知识点精华贴

一点都不帅

XP03 - DAY 01 时间复杂度 二分查找元素 X 是否存在 前置要求: 数组从小到大排序 二分查找大于等于 X 的第一个元素 前置条件：数组从小到大排序 二分查找大于 X 的第一个元素 前置条件：数组从小到大排序 二分答案 TLE 代码（非模板） 二分答案代码 前缀和 已经有一个 a 数组。 创建 pre 数组，pre[i] 的定义 a 数组前 i 项元素之和。 定义：pre[i] = a[1] + a[2] + ... + a[i] 求前缀和：pre[i] = pre[i-1] + a[i] ，前 i 项之和 = 前 i-1 项之和 + 第 i 项。 求 [l, r] 区间的和：pre[r] - pre[l-1] ，注意！！！不能写成 pre[r] - pre[l] 01DFS 概念：使用 DFS 去枚举数字或者数组元素，0 表示不选，1 表示选，最后对选择出来的方案进行判断。 二进制枚举 通过枚举数字，使用数字的二进制位去决定某个数字选还是不选。 例: 1011 第 1,2,4 个数选, 第 3 个数不选。 连通块问题 邻接矩阵存图 邻接表存图 深搜实现连通块 广搜实现连通块 结构体排序 结构体的定义 关键词: struct 结构体里的变量称为成员变量，如果要使用成员变量，需要用 . 结构体变量的定义 结构体排序 sort(起始地址, 结束地址, 排序函数); 例题代码（奖学金） 快速幂 分治做法 最大公约数 辗转相除法 ALGORITHM 自带函数 八皇后问题 使用多个标记数组记录列和斜线的情况。

有聊天的吗

DAY01 DAY02 Day03 Day04

#include <iostream> #include <algorithm> using namespace std; int main() { int t; cin >> t; while (t--) { long long x, y; cin >> x >> y; long long area = x * y; // 面积必须是偶数 if (area % 2 != 0) { cout << "No" << endl; continue; } long long mn = min(x, y); long long mx = max(x, y); if (mn == 1) { // 最小边为1时，最大边需要是4的倍数 if (mx % 4 == 0) { cout << "Yes" << endl; } else { cout << "No" << endl; } } else if (mn == 2) { // 最小边为2时，最大边需要是3的倍数 if (mx % 3 == 0) { cout << "Yes" << endl; } else { cout << "No" << endl; } } else { // 最小边≥3且面积为偶数时，总可以铺满 cout << "Yes" << endl; } } return 0; }

#include <iostream> #include <vector> using namespace std; const int MOD = 998244353; int count_pairs(int n, int k) { int res = 0; for (int x = 0; x <= n; ++x) { for (int y = x + 1; y <= n; ++y) { int diff = x ^ y; int cnt = 0; while (diff) { cnt += diff & 1; diff >>= 1; } if (cnt <= k) { res = (res + 1) % MOD; } } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); }

//复习题目的时候看了两遍此题正解代码，仍然做不出，遂急，书此篇。 链接描述 这道题目属于动态规划，但是思路有点难想。 在我初见这道题的时候，我使用了自己的聪明才智，尝试了出一个40pts40pts40pts的代码。 事情是这样的，我认为这道题就是自己“内部消化”。 如果说有一个aia_iai 能被aja_jaj 整除，那么这个aia_iai 就能被移除。 后来被测试点卡出。 因为第一个测试点的“19”是不能被其他三个数中的任意一个数整除的。 但是它可以有3和10凑出。 所以我就尝试

红绿灯： 复习次数：1遍。 完成证据&完成时间： 括号序列计数： 复习次数：1遍。 完成证据&完成时间： 8.15 12:07

给定两个整数 A 和 B，A 模 B 是当 A 除以 B 时的余数。例如，数字 7、14、27 和 38 对 3 取模分别得到 1、2、0 和 2。编写一个程序，接受 10 个数字作为输入，并输出这些数字在考虑模 42 时的不同数字的数量。 输入格式：输入将包含 10 个非负整数，每个整数均小于 1000，每行一个。 输出格式：在一行上输出在模 42 时的不同值的数量。 说明/提示：在第一个示例中，模 42 的数字为 1、2、3、4、5、6、7、8、9 和 10。 在第二个示例中，所有模 42 的数字均为 0。 在第三个示例中，模 42 的数字为 39、40、41、0、1、2、40、41、0 和 1。有 6 个不同的数字。

到此一游

#include <iostream> using namespace std; int main() { int N; cin >> N; }

链接描述 这道题有点非人。 可以一点一点的做出来。 1.32ptsptspts做法-暴力搜索： 注意到前八个测试点n≤10n\le10n≤10，m≤3m\le3m≤3。 是可以使用DFS的数据范围。 顺便提一下题意：她会做ai,ja_{i,j}ai,j 道不同的使用方法iii和主要食材jjj的菜。 然后就是思考如何使用DFS了。 因为Rin的要求是每道菜的烹饪方式互不相同，所以在DFS的过程中可以将参数xxx设为使用的烹饪方式。 然后对于每种烹饪方式，选择一种主要食材，然后在最后进行一些操作。 错误的代码： 正确的代码： 正确的对比错误的，主要改了这几个点： 首先在check()check()check()函数的第二个forforfor循环中，当vis[i]vis[i]vis[i]等于零时，是需要先跳过的，不然之前的全都会清零。 其次，sumsumsum的取余应该放在里面。ansansans也应该取余。 接着第二个forforfor循环当中的sumsumsum的计算应该是乘法而不是加法。 因为有ai,ja_{i,j}ai,j 种使用iii烹饪方式和jjj个主要食材的菜。 所以最终方案数应该是乘在一起产生xxx种排饭方式，具体可以参考排列组合。 然后就是64pts64pts64pts的暴力DP。 是这样的：可以建立一个四维DP数组：dp[45][45][45][45]dp[45][45][45][45]dp[45][45][45][45]。 通过某些观察发现前十六个点都拥有m≤3m\le3m≤3的测试数据。 也就是说，只有3种主要食材。 dp[i][x][y][z]dp[i][x][y][z]dp[i][x][y][z]表示使用了前iii种烹饪方式，做了xxx道使用了第一种主要食材的菜，做了yyy道使用了第二种主要食材的菜，做了zzz道使用了第三种主要食材的菜的方案数。 思考一下状态转移方程： 第一种：不做任何菜f[i][x][y][z]+=f[i−1][x][y][z]f[i][x][y][z]+=f[i-1][x][y][z]f[i][x][y][z]+=f[i−1][x][y][z] 第二种：做第一种食材的菜f[i][x][y][z]+=f[i−1][x−1][y][z]∗a[i][1]f[i][x][y][z]+=f[i-1][x-1][y][z]*a[i][1]f[i][x][y][z]+=f[i−1][x−1][y][z]∗a[i][1] 第三种：做第二种食材的菜f[i][x][y][z]+=f[i−1][x][y−1][z]∗a[i][2]f[i][x][y][z]+=f[i-1][x][y-1][z]*a[i][2]f[i][x][y][z]+=f[i−1][x][y−1][z]∗a[i][2] 第四种：做第三种食材的菜f[i][x][y][z]+=f[i−1][x][y][z−1]∗a[i][3]f[i][x][y][z]+=f[i-1][x][y][z-1]*a[i][3]f[i][x][y][z]+=f[i−1][x][y][z−1]∗a[i][3] 做完了一个神秘的四层循环后，你会得到一个完善的四维DP数组。 然后要做的就是在这些方案中剔除一些错误的，保留正确的。 判断的话就跟DFS的判断是差不多的。 这是错误代码： 这是正确的代码： 只有一个错误，就是dpdpdp数组要开longlonglonglonglonglong。 因为在四维DP和数组A相乘的过程中，可能会爆intintint。 然后就是84pts84pts84pts的做法。 注意到（注意力惊人）对于每一种方案，其实我们只关心使用最多的食材和其他食材总数，所以我们可以尝试钦定主要食材。 注意：最多1个食材会超过使用食材的一半。 所以，可以将四维DP简化成这样:dp[45][405][405]dp[45][405][405]dp[45][405][405]。 dp[i][x][y]dp[i][x][y]dp[i][x][y]的状态表示是在有iii种烹饪方式，选中的主要食材kkk有xxx个，其他主要食材的数量为yyy的方案数。 这个状态表示有点怪怪的，因为有一个不表示在下标中的变量：kkk。 所以说，你可能需要循环nnn次去进行一个三维的循环，不过还好。 因为在前21个测试点中，有n≤40n\le40n≤40的限制。 所以其实不会超时。 再考虑一下它的状态转移方程： 1.不做新的菜：dp[i][x][y]+=dp[i−1][x][y]dp[i][x][y]+=dp[i-1][x][y]dp[i][x][y]+=dp[i−1][x][y] 2.做kkk号食材的菜：dp[i][x][y]+=dp[i−1][x−1][y]∗a[i][k]dp[i][x][y]+=dp[i-1][x-1][y]*a[i][k]dp[i][x][y]+=dp[i−1][x−1][y]∗a[i][k] 3.做其他食材的菜：dp[i][x][y]+=dp[i−1][x][y−1]∗(∑j=1ma[i][j]−a[i][k])dp[i][x][y]+=dp[i-1][x][y-1]* (\sum_{j = 1}^{m} a[i][j]-a[i][k])dp[i][x][y]+=dp[i−1][x][y−1]∗(∑j=1m a[i][j]−a[i][k])。 注释： 其实这种方法到最后求的不是“满足条件的方案数”而是将所有可能的方案全部算出后，再去求“不满足条件的方案数” 然后就可以开始写一些神秘的代码。 终于，要写100pts100pts100pts的代码了。 经过观察返现最后的几个测试点的范围是m≤2000m\le2000m≤2000。 这代表我们开不了三维数组。 时间复杂度方面也无法支撑。 这里就需要提一提DP的优化方法了。（其实前面就应该提了，忘了）。 DP的时间复杂度组成：O(状态∗转移)O(状态*转移)O(状态∗转移)。 那么优化自然也有两类优化： 1.优化状态：可以将两维做差值，压缩成一维（这种方法相当常见，除了本题，相似的还有那个前几天的括号序列）。 2.优化转移：优化转移的方法有很多，可以使用一些普及组算法，比如这道题就使用了前缀和。 那么现在要将84pts84pts84pts的做法优化成100pts100pts100pts的做法，考虑继续使用优化状态。 其实观察可发现，在这道题中，我们并不关心主要食材和其他食材具体有多少个。 我们只是希望通过知道它们的个数，从而得出它们相差几个，会不会不满足条件。 那么逻辑慢慢清晰。 我们将后两维优化成一维的差值。 也就是说现在是这样的：dp[i][j[dp[i][j[dp[i][j[表示有前iii种烹饪方式，主要食材-其他食材的个数是jjj。 但是问题在于，如何设计状态转移方程？ 可以参考前几种做法的状态转移方程。 大概是这样： 1.不做：dp[i][j]+=dp[i−1][j]dp[i][j]+=dp[i-1][j]dp[i][j]+=dp[i−1][j]。 2.做主要食材的菜：dp[i][j]+=dp[i−1][j−1]∗a[i][k]dp[i][j]+=dp[i-1][j-1]*a[i][k]dp[i][j]+=dp[i−1][j−1]∗a[i][k]。 kkk是主要食材编号。 3.做其他食材的菜：dp[i][j]+=dp[i−1][j+1]∗(sum[i]−a[i][k])dp[i][j]+=dp[i-1][j+1]*(sum[i]-a[i][k])dp[i][j]+=dp[i−1][j+1]∗(sum[i]−a[i][k])。 然后需要注意一个问题：有没有一张可能，主要食材的数量≤\le≤其他食材的数量。 那么也就是说，j≤0j\le0j≤0。 （虽然说这种情况肯定不会算在“不满足条件”的方案数种）但是，想要求出“不满足条件”的方案数，是需要知道这些情况的数量的。 此时有一个聪明又机智的方法： 直接将jjj加上2000.（2000来源于mmm的范围）。 然后，在计算“不满足条件的方案数”的时候，就去计算大于2000的jjj的数量即可。 差不多了，代码跟84的差不多，甚至更简单。 有问题的代码： 正确的代码： 其实这两段代码只改了一个地方： 就是在solve()solve()solve()函数中，两层循环里的第一行代码： 错误的： 正确的： 注意：多次使用的函数就像多测一样，需要重新初始化。 如果不进行初始化，你的计算可能就会多一点注意事项。