杂题,记录CF上2000左右乃至更高的题,只写点思路,没得目录也没有顺序.为了保证大小不贴代码只贴submission链接.看情况会分开.
1451E1. Bitwise Queries (Easy Version)
一个非常直截了当的想法就是用异或还原出整个数组,因为其他两个操作都不能做到"还原".只要能求出一个数,就可以还原出整个数组.但是可以注意到只用或与操作表示不出来异或,比较难找等式关系.但是可以借用另外一种非位运算的操作:即加法:\(a + b = a \oplus b + 2 * (a \& b)\),这样可以得到两个数的和,为了求出一个解,把\(a_1+a_2,a_2+a_3,a_1+a_3\)求出来,这一部分可以用\(5\)次操作实现.剩下\(n-3\)个数每个数操作一次,总操作数\(n+2\)刚好通过本题.
代码:E1. Bitwise Queries (Easy Version)
1447E. Xor Tree
首先做个转换:把删除最少的点变成保留最多的点,因为删除的时候还要重定向边这很难维护.由于一共只有\(n\)个数,所以在没有一对数互相是各自的最小值的时候,整个图有\(n\)条边,那么结论显然就是:有且仅有一对数互相是各自的最小值的时候,这个图会是一棵树.问题等价于保留最多的点使互相是最小值的数对有且仅有一个.为了找出异或值最小的点,不妨建出Trie,在树上考虑:对每个数来说,如果下面还有子节点,那么与它捆绑的点只会在下面.借着这个想法可以尝试分割子问题并且把问题转换成一个树上DP:考虑对每个子树求最多能保留多少点.当一个点只有一个儿子的时候,显然取儿子的值.如果有两个儿子,那么取两者中的最大值并加一,表示选取其中一个儿子的所有点并且另外一个儿子只选一个.
代码:E. Xor Tree
909D. Colorful Points
把所有点缩成{val,cnt}的形式.对于端点只减一,内部所有元素减二.时间复杂度:设一共有\(cnt\)组数对,那么每次操作会踢掉\(O(cnt)\)个数,点数一共就\(n\)个,所以复杂度是\(O(n)\)的.
1311D. Three Integers
不知道为啥这也是2000.枚举最小的数\(x\),那么次大的\(y\)一定要是他的倍数,最大的\(z\)要是\(y\)的倍数,数据范围不大直接枚举就可以了.当然,可能\(c\)扩大之后答案会变得更小,那么需要枚举到\(2c\)为止.
916B. Jamie and Binary Sequence (changed after round)
好像是因为unrated的缘故导致的分数过高.姑且还是加进来.思路的话比较直接,因为\(2^k\)等价于在把二进制位上第\(k\)位掰成\(1\),所以从二进制的角度考虑配出\(n\),将\(n\)二进制分解之后,可以通过样例想到通过两个较低位凑出高位,那么先贪心地把较高位完全以较低位表示出来,使目标尽可能的小.其次考虑如果\(k\)还有剩余,应该从最小值掰成更小的,要使字典序最大,同时还应该每次只掰一个最小值,因为如果直接把所有最小值全部掰下去,字典序会有损失,换句话说一个一个掰是更优的,而且好写.注意空间问题.
代码:B. Jamie and Binary Sequence (changed after round)
916E. Jamie and Tree
换根操作+树链剖分.显然不能多次构造轻重链剖分,只记录root的位置,但只使用\(1\)为根的剖分.思路是比较明确的,就是直接把各个操作结合root的位置讨论.首先是修改操作:如果\(x\)和root重合,那么直接对整个树修改;如果\(x\)是root的子节点,那么可以假想把root提起来,直接对原树里\(x\)的子树修改就可以了.最后是root是x的子节点,考虑简单的冗斥:对整个树加一个权值,再把\(x\)的子节点中含有root的部分全部删掉,为了找这个点可以做一个倍增预处理再跳上来.求lca同样:考虑两个点相对于root的位置,把几种情况直接混合在一起的话,可以表达成:\(lca(x,y),lca(x,root),lca(y,root)\)中深度最大的点即答案.
916D. Jamie and To-do List
由于存在撤销操作,所以必须得糊一个可持久化数据结构上去.考虑使用主席树,那么现在方向就是考虑怎么用权值线段树维护题目所需的信息:首先需要一颗树维护每个字符串对应的权值,这一步可以先给每个字符串映射到一个整数再放到权值线段树上维护.其次需要知道某个值比他小的个数有多少个,那么这个维护一个cnt就可以了.空间往大了开,这题一共有两颗树,需要给多点.
909D. GCD of Polynomials
首先A的次数一定高于B,不妨猜测两者的度数分别是\((n,n-1)\),因为每次执行系数都会下降,所以执行\(n\)次肯定是每次都恰好系数都减一的过程,不妨反推:设\(p(i)\)是gcd递推过程中出现的度数为\(i\)的多项式,那么可以推出:\(p(n) \% p(n - 1) = p(n-2)\),根据定义\(p(n)=D(x)*p(n-1)\pm p(n-2)\)其中\(D(x)\)是一个多项式,简单起见直接定义为\(x\),那么就拿到了通项公式,可以直接构造\(p(0)=1,p(1)=x\).剩下最后一个问题:系数的绝对值不超过\(1\),这里有个很神棍的做法:直接把系数模2.根据一开始定义的初项来看,会产生超过边界的情况只有\(1+1=2\)这种,处理也就是\(1-1=0\)等同于模2.
897D. Ithea Plays With Chtholly
很奇妙的题.考虑顺推:由于不知道下一手会发什么牌,所以每次更新的策略应该是找到第一个空的位置,或者第一个值严格大于当前手上的值的位置,并覆盖.考虑最坏情况:首先每个位置至少被覆盖一次,其次最坏的情况每个位置被额外的替代了\(c-1\)次,总的情况就是\(n*c\)次.但是限制是\(c/2(↑)*n \leq m\)的.那么把问题拆解成:构造两个序列,一个单调不降,一个单调不升,两个拼起来的时候就达成了条件,同时在构造的时候对值域分割,第一个序列里面只使用\(\leq c/2(↓)\)的,另外一个相反.这样操作次数结合在一起就满足条件了,并且由于值域的分割,当所有位置完成的时候自然完成序列构造.
代码:D. Ithea Plays With Chtholly
903D. Almost Difference
简单题,按常规套路去思考枚举\(a_i\)和\(j>i\)就可以了,发现分类只有两种:\(=a_i-1,=a_i+1,=a_i\)以及其他.之后明显第一类没有贡献,贡献的只有不属于如上集合的部分,贡献的形式是求和:\(a_j-a_i\),那么维护后缀的和,后缀各个元素值的个数即可得到答案.唯一坑点:数据爆ll.换成long double可以通过本题.
903E. Swapping Characters
考虑拿第一条串作为结果串,枚举两个位置进行交换.交换完毕后枚举每个位置求不同位置的个数,如果为\(2\)且形式上是交换的,则可行;如果个数是\(0\)那么在存在相同字符的前提下,可行.这样暴力枚举的复杂度是\(O(n^3*k)\)的,考虑降掉一个\(n\):为了求不同位置的个数,交换之后只会对\(i,j\)两个位置上的元素产生影响,考虑预处理出每个串与第一个串的不同的位置个数,再增量求出交换后的不同的个数,维护即可.特判频率不同的情况.
895D. String Mark
要求\(a\)的排列\(c\)满足\(a < c < b\)的个数，由于直接统计排列是\(n!\)级别的，显然不可能。考虑分割集合的划分：将答案的统计划分为这样一些串：\([1,i-1]\)部分完全与\(a\)相同，且恰好在\(i\)的时候，有\(c_i > a_i\)。同时还有一个下标\(j\)类似，只是\(c_j < b_j\)，这样直接统计显然是\(O(n^2)\)的也不可承受，但是可以类似前缀和的办法继续拆分：定义函数\(f(s)\)表示只使用某个特定的字符集\(\sum\),组合出来的字符串字典序小于\(s\)的方案数，答案转化为\(ans=f(b)-f(a)-1\).考虑计算\(f(s)\)：直接通过定义枚举每一位\(i\)表示\([1,i-1]\)完全与\(s\)相同的前提下，得到的方案数。枚举第\(i\)位的取值，之后的\([i+1,n]\)任意填，多重集排列数即可。整体复杂度\(O(26^2*|S|*2)\).不可通过，通过逆元本身的性质，同时维护实际的值的变化即可减少一层26，通过本题。
895C. Square Subsets
经典结论：平方数的质因数分解幂次都是偶数。由于值域很小，只有19个质数，所以直接压二进制状态进去，由于只看奇偶所以只需要模2意义的值，同时可以发现多个数选在一起事实上等价于各个二进制状态异或的结果。所以问题等价于选出若干个数使异或和结果为\(0\)的方案数。如果直接按每个数dp的话会发现开不下去，但是可以借助值域较小的条件，把第一维从枚举到哪个数变成枚举值域，复杂度就可以通过了。Dp方程可以有一个小合并。
895E. Eyes Closed
考虑维护期望：\(E[i]\)表示第\(i\)个位置上的值的期望。对于询问：\(ans = \sum E[i]\)。对于修改：设\(i\in[l1,r1]\)，那么\(E[i] = (L1 - 1) / L1 * E[i] + \sum E[l2,r2] / L1 / L2\)。对于\(i\in[l2,r2]\)同理。用一个支持区间乘，区间加，区间求和的线段树即可维护。
894D. Gluttony
构造：对每个\(a_i\)选用第一个比它大的数，对于最大值，选用最小值与之对应。正确性：如果不包含最大值的话，每个元素对应的元素都比之小，所以肯定不相同。如果包含最大值，考虑其补集，同样不可能相等，由于和相同，所以偏序关系逆转，最终还是不相同。正确性得证。\(n\)特别小的原因估计是spj的问题，有点误导人。
代码:D. Gluttony
888G. Xor-MST
把所有元素插入Trie，首先说明：相同权值的点之间可以连\(0\)边不会对MST产生贡献。所以只考虑权值不同的点之间的连接。其次可以发现在\(Trie\)结构上，两个权值异或是在lca之后的部分才会产生贡献的，前面相同的部分完全相同可以不管。结论：\(n\)个叶子必定有\(n-1\)个\(lca\)，反过来\(n-1\)个lca每个合并两个点所在的集合，一开始所有点都属于自己一个集合。所以问题就是对于每个lca，向下选两个点且两个权值异或起来值最小值之和是多少，可以发现只有有两个儿子的点会是lca，所以找到这样的点的时候走两个指针向下贪心尽量走相同位权的点就可以了。
代码:G. Xor-MST
887D. Ratings and Reality Shows
结论：talk show的选取起始时间一定在某次活动之后一秒开始。由于只问：开之前和开中间rating不能到负数，所以我们维护这个区间内的就可以了。
代码:copy了网上的题解，发现人写错了我自己交了之后AC就懒得管了D. Ratings and Reality Shows
879D. Teams Formation
比较复杂的模拟。首先求单个的，把单个内部的用栈模拟踢掉所有可能合并的。再考虑多个bus首尾相连，做左右指针向中心移动合并相同部分的长度。接下来讨论：若这样做之后已经只剩一个元素或者清空，以及剩下多个元素的情况。前者特判：中心部分完全清除时，边界左右额外消除一次。后者特判：前后消除之后中心拼接又可以消去一些。
884D. Boxes And Balls
简单想到：正着想的话是每次贪心都选三组分配，尽量先让大的放到合适的位置。实现上比较奇怪，可以反向考虑：一开始所有颜色的球就已经放在合适的位置了，那么问题等价于把所有球合并到第一个盒子里的最小总代价，每次移动的代价等于移动的球的总数量。问题等价于合并果子，只是本题可以合并两堆/三堆。手推样例之后可以发现因为每次选取三堆的时候，事实上等价于踢掉两堆，所以当\(n%2=0\)时会导致剩下两堆需要合并，这个时候根据按小到大合并的做法来看最后合并的话反而代价很高，不如一开始的时候就用一次两堆合并的，使结果缩小。
877D. Olya and Energy Drinks
直接BFS，加个k层拓展。理论上来说是\(O(nmk)\)的，但是跑不满。可以考虑空白或者障碍多的情况都会被踢掉。事实上也确实跑的挺快的。
877E. Danil and a Part-time Job
树链剖分转成区间问题：支持区间异或1，区间求和即可。
代码:E. Danil and a Part-time Job
864E. Fire
容易想到一个朴素的dp：\(f[i][j]\)表示选取前\(i\)个元素当前时刻为\(j\)的最大价值。但是这个dp无法直接转移，因为直接按\(i\)进行划分是没有依据的，但是如果把所有元素按\(d[i]\)排序，因为对于物品的选择，一个更早消失的物品应该比更晚消失的物品更先考虑，这样顺序划分第\(i\)个就是对的，模型等同于01背包，每个物品只有选和不选两种情况。对于输出路径：记录所有选择即可。
代码:E. Fire