嘴巴记录II

状态不佳时会嘴巴，题目来源非常随机。

CF1603D Artistic Partition

我们发现 \(c(l,r)\) 当 \(l=x,r=2x-1\) 时，一定等于 \(r-l+1\) ，所以如果 \(n<2^k\) ，那么一定是可以拆分成若干段满足上面要求的式子的，所以我们只需要考虑 \(n>2^k\) 的情况，即 \(k\) 我们只需要处理 \(O(\log_2n)\) 级别的答案。

考虑到 \(c(l,r)\) 是满足四边形不等式的，所以我们干脆考虑暴力求解 \(\log_2n\) 个 \(k\) 的答案。

现在的问题是如何快速求出 \(c(l,r)\) ，考虑推式子：

\[c(l,r)=\sum_{i=l}^r\sum_{j=i}^r[\gcd(i,j)\ge l]\\ =\sum_{i=l}^r\sum_{j=i}^r\sum_{k=l}^r[\gcd(i,j)=k]\\ =\sum_{k=l}^r\sum_{i=1}^{ik\le r}\sum_{j=i}^{jk\le r}[\gcd(i,j)=1]\\ =\sum_{k=l}^r\sum_{i=1}^{ik\le r}\varphi(i)\\ \]

维护一波 \(\varphi(x)\) 的前缀和即可。

然后做完了！！！

CF1363D Guess The Maximums

首先一个全部查询可以让我们获得全局最大，但是我们需要找到这个全局最大的位置，所以我们要二分查找。

然后对于不包含这个全局最大位置的集合，我们实际上已经得到答案了，然后查询一下剩下的最大即可。

~~为什么这种题也能进我的任务计划。~~

CF700D Huffman Coding on Segment

我们回忆一下哈夫曼编码，其是自底向上建树，每次合并最小的两个子树。

我好像没啥想法。考虑能否在已有哈夫曼树上加入一个数并维护。。。

考虑我们可以使用莫队维护每一个数出现的数量，我们现在需要考虑的是如何快速求出他的哈夫曼树的权值。

我们考虑到出现的数的数量的和是为区间的长度的，所以这启发我们使用根号分治。

我们令设定一个上界 \(B\) ，超过 \(B\) 的我们直接考虑用堆做，不超过 \(B\) 的我维护出一个桶 \(b_i\) 表示出现次数为 \(i\) 的数有几个，考虑扫一遍这个桶并合并，如果合并之后超过了 \(B\) 就丢到堆里。

可以发现丢到堆里的数的个数还是 \(\frac{n}{B}\) 级别的，因为 \(\sum i\times b_i=n\) 始终是定值。

我们取 \(B=\sqrt{n\log n}\) 可以达到最优复杂度。

AT3954 [AGC023C] Painting Machines

首先涛神搞出了一个式子：

\[\text{res}=\max_{i=1}^n\min(t_i,t_{i+1})\\ \]

其中 \(t_i\) 表示每一个操作的出现时间。

我们考虑算出前 \(i\) 步覆盖完全的排列数量 \(f_i\) ，然后我们的答案必然可以通过这个 \(f_i\) 求得。

然后考虑到实际上这个排列的数量只和我们前 \(i\) 步选了哪些位置有关，所以我们可以设 \(g_i\) 表示选择 \(i\) 个位置能够覆盖满的集合数量，可得 \(f_i=g_i\times i!(n-i-1)!\) ，意为 \(i\) 个被选择的元素的位置可以随意调换，剩下元素的位置也可以随意调换。

我们再来考虑求这个 \(g_i\) ，我们要使得其中的元素有 \(1,n-1\) 且相邻的元素的差不能超过 \(2\) 。

由于差不能超过 \(2\) ，相当于我们就是需要选出 \(k\) 个差作为 \(2\) ，剩下 \(i-1-k\) 个作为 \(1\) ，同时满足和是 \(n-2\) 。

\[2k+(i-1-k)=n-2\\ k=n-1-i\\ \]

所以方案数就是：

\[g_i=\binom{i-1}{n-1-i}\\ \]

然后我们考虑再用 \(f_i\) 计算出答案，即

\[\text{res}=\sum_{i=1}^{n}(f_i-f_{i-1})i \]

然后做完了。

P7828 [CCO2021] Swap Swap Sort

感觉这题可以从两个角度思考，一个是逆序对的角度，另一个是交换之后的贡献的角度。

如果从逆序对的角度，我们需要快速求出交换的两个元素所构成的逆序对的数量，或许不需要快速，因为交换只进行 \(O(q)\) 次，我们可以预处理。

具体是用根号分治预处理：

如果两个数的出现次数都小于根号，暴力做即可。
如果存在一个数的出现次数大于根号，我们就预处理好其前缀和，同时暴力扫一遍其余所有数的答案，此过程不会超过根号次。

然后就好了。

P2336 [SCOI2012]喵星球上的点名

好像我可以直接嘴巴掉？

直接考虑将所有喵星人的串的所有后缀和询问串混在一起排序，然后就是一个区间数颜色的问题了！！！

P3265 [JLOI2015]装备购买

给我一种线性基的感觉，但是我们要使得装备花的钱最少。

我们直接考虑从小到大的价格维护即可？

P7824 「RdOI R3」毒水

这不就是一个二分查找吗？假设我们没有变异鼠。

类似于这样的，以 \(16\) 瓶毒水举例：

0000000011111111
0000111100001111
0011001100110011
0101010101010101

我们直接可以通过这种方式（即二进制）来获得哪瓶是有毒的。

但是存在一个变异鼠，而且变异鼠会给我们相反的信息。也就是如果我们询问的鼠中存在变异鼠，我们必然不能正确作答。所以我们还需要通过剩下的 \(6\) 只老鼠找到这只变异鼠，或者得出变异鼠不在我询问的老鼠中的结论。

我们意识到我们可以通过将两次询问的询问区域异或，这样我们也能得到两次询问的答案异或。

而异或运算存在一个优点就是只改变其中一个的值是一定错的。

我们就考虑将相邻三个的配对进行异或查询，花费了 \(3\) 只老鼠。

考虑再将 \(1,4,7\) 异或检测，\(2,5,8\) 异或检测，\(3,6,9\) 异或检测，花费了 \(3\) 只老鼠。

我们发现我们是可以利用上面的检测判断出变异老鼠的位置的。

如果 \(6\) 次检测中只错了一个，那么必然是检测的老鼠是变异鼠，不然如果错了两次，找到错的交集即可判断变异鼠位置。

CF1535F String Distance

首先如果可行答案最大就是 \(2\) ，所以我们只需要判断是否是 \(1\) 以及是否可行。

可行非常好判断，字符集不相同一定不可行，这是充要的。

判断是否是一的话相当于就是两个串需要满足他们存在一定的前后缀相同，且剩下部分其中一个串是有序的。

所以说我们已经有了一个快速判断是否是 \(1\) 的方法，找出两个串的最长公共前后缀，查看剩下部分是否是一个有序的。

首先判断串是否相同的话我们就直接暴力排序加哈希搞就行了。

有一个很关键的点没有发现，就是如果中间部分是有序的，那么他一定是位于跟他有着相同最长前缀的串的第一个（在经过排序后）。

所以我们直接利用单调栈来维护 \(\text{lcp}\) ，现在的问题就是怎么找出这个极大有序子区间呢？我们可以预处理每一个子序列的有序区间的分界点，然后二分找到即可，我竟然没有想到。

然后我们现在又需要统计出相同末尾的位于这段相同 \(\text{lcp}\) 区间的字符串个数，这个直接每一个串反向塞入一个 \(\text{trie}\) 上，每一个节点储存过该点的字符串编号，然后查询的时候记录一下位置，在对应节点上二分即可。

咕咕咕。

CF1427G One Billion Shades of Grey

感觉又是一道网络流。

就是直接最小割？感觉权值如果是取差值的绝对值的话，是可以离散化的？然后直接搞？

发现图的大小是 \(O(n^3)\) 的，根本流不动。

考虑贡献是可以被拆分成若干段的差的，我们每一次网络流统计这个差值的贡献，建图方式就是我们上面的这个方式，只不过是割的边数只有两种——小于等于的和大于的。

然后相邻的两次差值的计算实际上就是需要我们将若干个点改变其选择的边，这就需要网络流退流的技巧了。

我们发现，如果是加边的话，可以直接加进去然后直接在原来跑完的基础上继续跑，而难处理的是减边。

这个时候我们就用到优秀的退流啦！假设源点和汇点是 \(S\) 和 \(T\)，要删去一条边 \((u,v)\)，那么我们只需要以 \(u\) 为源点，向 \(S\) 跑一次最大流，然后再以 \(T\) 为源点，向 \(v\) 跑一次最大流即可。最后将 \((u,v)\) 这条边以及其反向边的流量设为 \(0\) 即可。
————————————————
版权声明：本文为CSDN博主「Hypoc_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/a_forever_dream/article/details/105306468

应该就可以了吧。

好像直接跑最大流我会出现一些未知错误，但是你可以通过限制退的流量来保证正确性（？）。

好消息是，我的代码T飞了，不知道是常数问题还是复杂度问题。

CF1100D Dasha and Chess

我们必须要满足每一行或列到白色国王这段区间的黑车的个数小于等于该行或列到白色国王的距离。

感觉必然存在，直接搞就行了？向最多的三个方格所在的方向前进即可。

好像还有亿点细节，判断一下就行了。

CF1207E XOR Guessing

先问前七位再问后七位？秒了。

CF1592D Hemose in ICPC ?

好像直接找就行了？首先答案必然是一条树边。

卧槽，直接二分欧拉序，有点牛的。

P6957 [NEERC2017]The Final Level

考虑每次根据当前位置向 \((a,b)\) 走，同时分类讨论：

\(dis_a\ge n,dis_b\ge n\) ，那么直接距离远的走 \(n\) ，近的走 \(n-1\) 。
\(dis_a 或 \(dis_a\ge n,dis_b ，远的走 \(n\) ，近的走 \(dis\) 。
\(dis_a ，移动一下就可以使得 L 形一定穿过目标点。

可以证明，上面的做法是一定最优的。

考虑情况只有两种，一开始一侧大，后来便轮流比对方大；一开始一侧大，然后抵到边界后横向加。

考虑上述两种情况必然都是不能通过一定的调整变得更小的（有点意会。。。）。

CF1451E2 Bitwise Queries (Hard Version)

感觉问题的关键是要找到两个相同的？

直接异或过去，找到相同的一对，同时记录一波与第一个异或的值，如果没有说明互不相同，这里花费了 \(n-1\) 步。如果有相同的，考虑与或或一下相同的一对，即可得到具体数值，然后就知道了每一个数。如果两两不同，必然存在异或是 \(2^k-1\) 的，找到这个之后跟其中一个取一个或，一个取一个与，就能得到取或的那个数，然后就得到整个序列了。

CF1370F2 The Hidden Pair (Hard Version)

首先我们考虑通过一次询问找到链上的一点，然后可以二分两次，但是询问次数就是 \(21\) 次了。会是 \(21\) 次吗？考虑只有在两边深度都大于 \(1000\) 才会这样，而不可能同时为 \(1000\) 。应该是可以的。

一个想法是最大深度的下界为 \(\lceil\frac{l}{2}\rceil\) ，可以减少一次。

CF1466I The Riddle of the Sphinx

存在一个 \(naive\) 的想法就是每次给所有数问一样的数，每次区分出一些数就可以找到最大了。

看了题解，感觉很妙妙。

考虑用一个类似于单调栈的结构来维护一个叫做最大前缀的东西，其定义为栈中的所有数的前缀都等于最大前缀，如果一个数加入最大前缀后可以抬高最大前缀，就考虑弹出栈顶，同时其中的每一个元素对于最大前缀的贡献就是其在栈中的位置，其位于第 \(i\) 个就为最大前缀贡献从高到低数的第 \(i\) 位。

这个定义十分奇怪，但是可以让我们得到若干个有着相同最大开头的数，且比较方便我们递归处理。

考虑分析一下操作次数，首先考虑一开始维护这个东西是 \(O(n)\) 的，然后我们可以得到答案的前 \(k\) 位，同时递归处理长度为 \(k\) 的子问题（为什么长度为 \(k\) 可以结合栈的构建过程反证法证明），复杂度是 \(O(n+k)\) 的，具体可以再结合一定的性质将常数减少到 \(3\) 。

题解 CF1466I 【The Riddle of the Sphinx】 - CXY07 的小屋 - 洛谷博客

CF1364E X-OR

按位或？首先我们可以将一个数与其他所有数或一次，其中的答案的最小值就是这个数，但是 \(0\) 除外。

我们考虑这样一件事情，一个数拼命和后面的数或，直到这个或值等于自己，那么这个或上的数必然比自己小，换成或上的数往后扫，这样扫一遍就可以找到 \(0\) 的位置。再通过 \(0\) 得出其他每一个就行了。

哦不太对，我们不能知道我们取到的这个数的值是多少。

我们考虑一直维护最小的两个异或值，找到 \(0\) 之后查询一次即可。

CF1392E Omkar and Duck

请注意，你给出的路径必须和答案文件中的路径一致。

这告诉我们对于每一条路径，其权值必须是唯一的？所以我们就需要构造一个 \(n\times n\) 的矩阵，使得路径权值和路径两两对应，并且能通过权值快速求出路径。

存在一个比较 \(naive\) 的想法就是左下右上对角线取一样的值，这样的话我们就可以通过对角线取值的位置得到其的路径，但是如果对角线是满的显然不能知道位置，所以我们考虑对角线只有奇数行存在值。可以发现，这样必然可以唯一确定一条路径。

AT2336 [ARC069D] Flags

考虑二分答案，然后用 2-sat 判断是否可行（要么在 x 轴上，要么在 y 轴上），连边使用线段树优化建图。

CF671D Roads in Yusland

给定有根树和若干条有权值的路径，选择若干条路径，满足覆盖树上每一条边，且路径权值和最小，保证路径是祖先-后代路径。

感觉有一个很想线段树合并的东西，用 \(f_{u,i}\) 表示点 \(u\) 向上到深度 \(i\) 都存在路径的时候最小的权值和是多少。考虑合并两个节点的时候就是 \(f'_{u,\min(i,j)}=\min_{i,j}f_{u,i}+f_{v,j}\) ，这个取 \(\min\) 应该是可以在线段树合并上做的。然后考虑单点向上添加路径的话相当于也是一个类似于取 \(\min\) 的操作。

应该就行了。

P5488 差分与前缀和

原本我以为是什么高妙数据结构，原来是多项式，我小丑了。

前缀和即求

\[G=F\cdot (\frac{1}{1-x})^k\pmod {x^{n+1}}\\ (\frac{1}{1-x})^k=\exp(k\cdot\ln(\frac{1}{1-x}))\\ \]

考虑泰勒展开

\[\exp(k\cdot\ln(\frac{1}{1-x}))=\sum_{i=0}^{\infty}\frac{k^i\cdot\ln^i(\frac{1}{1-x})}{i!}\\ \]

意识到这个 \(k\) 是可以直接 \(\bmod 1004535809\) 的，然后就可以直接搞了。

差分就求逆即可。

CF914G Sum the Fibonacci

这个花里胡哨的五元组是个啥啊。我感觉是要容斥的？

艹，我是猪，\(\text{fwt}\) 和子集卷积的板子题啊。

「PA 2021」Poborcy podatkowi

考虑一个子树内我们可以用 \(f_{u,i}\) 表示子树内全部选择完全后剩下长度为 \(i\) 的向上的链需要继续合并。我们考虑怎么合并这个信息。对于一个子树来说，我们需要让 \(1,3\) 尽量配对，\(2,2\) 配对尽量，那么我们最后剩下要给即可。

考虑我们只需要知道 \(1\) 的数量减去 \(3\) 的数量的值和 \(2\) 的奇偶性，发现前者是有达到 \(O(n)\) 级别的。但是考虑到如果最后这个位置可以传递上去，必然是绝对值小于等于 \(1\) 的，如果我们通过随机顺序添加每一个子树的贡献的话，实际上是可以将其控制在 \(O(\sqrt n)\) 的级别的。

CF1466H Finding satisfactory solutions

这就是 *3300 吗？完全不会做。

不是很能理解 \(\forall i\in S,a'_i\in S\) 的意义在何。

不过我们依据这个条件的话，似乎只有置换环才能作为一个集合 \(S\) 。

意思就是说，不存在一个置换环被完全吊打，完全吊打指存在一个位置优的情况下，其他位置严格不劣。

我们干脆先来考虑暴力一点的做法，如果暴力枚举置换环，实际上我们就可以得到这个环对应的方案了，然后我们实际上只需要让题目给的 \(a_i\) 比置换环的 \(a'_i\) 均不劣或者存在一个位置劣其余随意就行了，然后我们就可以求出这个置换环的方案数，然后跑一个状压就行了。

但是我们暴力枚举置换环是 \(O(n!)\) 的，而且后面的状压是 \(O(2^n)\) 的，这个复杂度我们是不能接受的。

发现理解错题目了，感觉这个题目的题面巨难理解。

不是置换环，意思是对于一个任意一个非空子集，不能通过集合内部的调换使得出现完全吊打。

我们不妨让每一个人都先向自己最喜欢的物品连边。

先跳这题了，有点懵。

嘴巴记录