逆天记录 - 4

CF1882E2 Two Permutations (Hard Version)

好题啊，E1 的构造已经让我想了好久了，E2 的第一步转化真的很妙！

需要最优化，首先考虑 dp，但是发现 dp 状态难以定义，所以需要对操作进行一些转化。

考虑在排列的开头加一个 $0$，标记整个排列的开头位置。当对位置 $x$ 进行一次操作时，等价于将位置 $x$ 与 $0$ 的位置进行交换。

操作完后，整个序列就是从 $0$ 开始往后的数循环构成的排列，这样我们就完成了 $O(1)$ 的交换操作，而且交换两个元素也比原题意的神笔操作正常一些。

由于 $n,m\le 2500$，所以考虑枚举两个排列最后的形态（即 $0$ 的位置），随后对于每一种最终状态。

对于一种对应的状态，对应点之间连边后，最少步数是去除所有一元环后，所有 $0$ 不在的环的步数是环长 $+1$，$0$ 所在的环的步数是环长 $-1$。而如果要多一些步数去拟合另一个排列，可以操作 $2$ 次。

将所有结束状态分为奇偶两类，对应的取 $\min$ 即可，构造方案是容易的。

感觉最为逆天的地方还是在于第一步加入一个 $0$ 的转化，后面的做法还是较为套路的。

CF1879F Last Man Standing

这个题的意义在于让你突破思维定势，如果你被套路所局限，那么你终究只能度过一个相对失败的人生，，。

比较套路的想法是你对于每个 $a$ 进行上取整的整出分块，然后直接去扫描这 $n\sqrt A$ 个分界点，时时维护最大值与次大值，但这种做法实现最优秀时复杂度也只能做到 $O(n\sqrt A)$，根本无法通过该题。

接下来尝试打破思维定势（其实这也是另一种套路吧），先去枚举 $x$，随后枚举 $\lceil\frac{a}{x}\rceil$，这个枚举量是 $O(A\log A)$ 的，可以接受。

接下来，对于每个 $\lceil\frac{a}{x}\rceil$，可能成为最大值的只有可能对应区间内的 $h$ 最大的两个，但是这样就要求区间最大与次大，直接维护还是要带 $\log$。如果我们把 $l\le a\le r$ 的条件弱化为 $a\ge l$，然后对于 $a>r$ 的仍然当作现在枚举的 $\lceil\frac{a}{x}\rceil$ 来算，发现并不影响结果，我们只需要在维护最大与次大时记录一个 $id$，不要让最大与次大的 $id$ 相同即可。

这样，我们要求的问题转化为 $a\ge l$ 的 $h$ 的最大与次大，这可以通过一个类似后缀 $\max$ 的操作来线性预处理。

至此，我们在 $O(n+A\log A)$ 的时间复杂度内解决了这个问题，突破了思维定势！

CF995F Cowmpany Cowmpensation

相比于前两题，就更像是一道套路的题目了，没有什么人类智慧难度。

考虑朴素的 dp，令 $f_{u,i}$ 为以 $u$ 为根子树内，$u$ 的点权 $\le i$ 的方案数。

考虑转移是什么，首先忽略 $u$ 填的值，那么就是将所有子树的 $f$ 进行点积，求出 $g_{u,i}$ 表示 $u$ 子树内，所有儿子节点的点权都 $\le i$ 的方案数。

再考虑 $u$ 填什么，我们钦定每个 $g_{u,i}$ 中，$u$ 的点权都选择 $i$，这样不会算重，而 $f_{u,i}=\sum_{j\le i} g_{u,j}$。

因此转移的本质是对一个点所有子节点的 dp 值进行点积，随后求一遍前缀和。

将 $f_{u,i}$ 看作一个函数（注意不是生成函数），即考虑 $F_u$，其中 $F_{u}(x)=f_{u,x}$。容易发现每一次转移 $F$ 的度数会 $+1$，因此最终 $F$ 的度数 $\le n$，因此只要记录 $O(n)$ 个 $F_u$ 的值，就可以在计算答案的时候插值出 $F_{1}(d)$ 了。

ARC124E Pass to Next

考虑赋予 $\prod x_i$ 实际意义，假设第 $i$ 个位置有 $x_i$ 个球，那么这个式子的意义就是每个位置选择一个球，选球的方案数。

先不考虑本质不同的方案，令 $f_{i,0/1}$ 表示考虑了前 $i$ 个位置，最后一个位置是选择了自己原本的球 / 选择了上一个传过来的球的方案数。

此处，自己原本的球在往后传的过程中计算，上一个传过来的球在 $i-1\to i$ 的转移时计算。

那么容易列出转移方程：

$$\begin{bmatrix}f_{i,0}&f_{i,1}\end{bmatrix}\times \begin{bmatrix} \sum_{x=0}^{a_i}x&\sum_{x=0}^{a_i}x(a_i-x)\\ \sum_{x=0}^{a_i}1&\sum_{x=0}^{a_i}x \end{bmatrix}=\begin{bmatrix}f_{i+1,0}&f_{i+1,1}\end{bmatrix}$$

此时还有两个问题：原问题是一个环 与 原问题 $b$ 相同的只算一次。

对于第一个问题，可以破环为链，然后枚举破环为链割开的点选了什么球来计算。

对于第二个问题，发现如果所有点都向后传了至少一个，那么每个都少传一个最终的 $b$ 是一样的，而如果有至少一个间隔没有往后传，那么一定没有另一个 $b$ 序列与之相同，因此只需要在 dp 时再记录一维 $0/1$ 表示是否有一个间隔出现过没有往后传的情况即可。

AGC016F Games on DAG

首先发现两枚棋子其实是两个独立的游戏，我们对于每一个为起点放一枚棋子求出 SG 后，只需要 $1,2$ 节点的 SG 值不同那么就是先手必胜。

如果一个点的 SG 值 $=x$，那么对于每个 $y< x$ 他必须向至少一个 SG 值 $=y$ 的点连边，而不能像任何一个 SG $=x$ 的点连边，对于 SG $>x$ 的点，是否连边都行。

考虑从大到小分层确定每个点的 SG，令 $f(S)$ 表示已经确定了 $S$ 点集的点相对 SG 值（因为我们是从大到小确定 SG 值的，所以并不能确定 SG 值具体是多少，但是最后一层 dp 到的点就可以看作 SG $=0$ 的）的不同的连边方案。

转移时，枚举最后一层填 SG 最小 $=x$ 的是哪个集合的点集，设为 $s$，那么 $t=S\setminus s$ 集合的点就是确定了的 SG $>x$ 的点。

考虑转移的方案：

• 对于每个 $u\in t$ 的点，都至少向 $s$ 中的点连一条边，方案是 $2^{\mid e_u\cap s\mid}-1$。
• 对于每个 $u\in s$ 的点，都可以向 $t$ 中的点任意连边，方案是 $2^{\mid e_u\cap t\mid}$。

由于需要 $1,2$ 的 SG 值不同，所以在转移时只需要保证 $s$ 中不能同时出现 $1,2$ 即可。复杂度 $O(3^n\cdot n)$。

AGC016E Poor Turkeys

发现如果想让一直火鸡最后生存下来，那么必然会牺牲一些火鸡，并且对于一只火鸡，如果他最后能生存下来，那么必须牺牲的火鸡是确定的。

对于每一只火鸡 $a$，我们想让他最后生存下来，那么倒序考虑，时刻维护一个集合 $S=\{a\}$ $\cup$ 必须牺牲的火鸡集合。如果出现了一对 $(x,y)$,分如下情况考虑：

• $x\in S,y\in S$，那么两者在之后的操作中都是必须牺牲的或者就是 $a$，但是这一次操作必须牺牲一个，所以直接导致 $a$ 不可能生存。
• $x\in S,y\not\in S$，那么 $x$ 在之后操作中有用，这一次不能牺牲，所以 $y$ 只能牺牲，所以将 $y$ 加入 $S$。
• $x\not\in S,y\not\in S$，那么这一次操作对于 $S$ 没有影响。

对于每一个火鸡 $x$ 求出 $S_x$ 后，考虑如何判断两只火鸡 $x,y$ 能否同时生存，如果 $x,y$ 分别都有可能最终生存，结论是 $S_x\cap S_y=\emptyset$。考虑证明：

• 充分性：两者无交，所以每只火鸡最多只会影响到最终一只火鸡的状态，不会有重复，一定有解。
• 必要性：考虑上述加入元素到 $S$ 中的过程，如果一对 $(x,y)$ 满足原来 $x\in S,y\not\in S$，导致 $y$ 加入了 $S$，那么连一条从 $y\to x$ 的有向边，死火鸡的过程其实等价于在这张 DAG 上不断删点，如果 $S_x\cap S_y\not=\emptyset$，那么最终一定会有至少一个点 $u$ 满足有 $u\to v$ 与 $u\to w$ 两条边，且 $v\not=w$，那么两条边上都要让 $u$ 死一次，但是 $u$ 只能死一次，所以不合法，因此 $S_x\cap S_y=\emptyset$。

使用 bitset 维护每个 $S_x$，最后数数的时候暴力枚举即可，时间复杂度 $O(nm+\frac{n^3}{\omega})$。

ARC117F Gateau

感觉没有铜牌难度啊。

首先考虑二分答案，暴力做法是破环成链，将每个限制转化为一段区间的和 $\ge$ 或 $\le$ 某个值。考虑对前缀和做差分约束即可，时间复杂度 $O(n^2\log A)$。

考虑瓶颈在于每次都要使用 spfa 判断是否存在负环，我们希望能更快的判断负环。

观察到这张图其实就是上下两层，层间从下到上连边权为负的边，从上到下连边权为正的边，每个都都能往前连边权为 $0$ 的边，第二层的头向第一层的尾边权为 $0$ 的边，第一层的头向第二层的尾连边权为二分到的和的边。

负环的形态一定是如下三种之一：

• 直接从一对上下的点走一个二元环。
• 经过了从第一行头到第二行尾的边，此时一定是一个按照顺序上下交替的路径，起点和终点的方向没有限制。
• 经过了从第二行头到第一行尾的边，此时一定是一个按照顺序上下交替的路径，并且头尾都是从上往下的路径。

对于第一种情况，可以直接判断，对于后面两种情况，可以 dp 求解最小值，判断其是否 $<0$，即可做到 $O(n)$ 判断是否存在负环。

综上，时间复杂度被优化为 $O(n\log A)$。

P9746 「KDOI-06-S」合并序列

感觉是一道比较套路的题，但是我怎么没想出来。。。以下称 $s[l,r]=\oplus_{i=l}^r a_i$。

首先考虑区间 dp，令 $f_{i,j}$ 表示区间 $[i,j]$ 能否被操作成为一个数。发现转移一定是 $[\dots]\dots[\dots]\dots[\dots]$，其中三段 $[\dots]$ 都是能被操作为一个数的区间，且三段的异或和 $=0$，直接转移复杂度爆炸。

考虑减少枚举的位置，我们枚举第一个段的右端点，即第一个 $[\dots]$ 的 $]$ 位置，假设该位置为 $k$，那么第一段的异或和 $=s[i,k]$，我们要 check 是 $(k,j]$ 能否找出两个合法的不交的区间，且第二个区间的右端点 $=j$，使得两个区间的异或和 $=s[i,k]$。

观察到一个性质，如果 $[l,r]$ 内能找到两个不交的合法区间，第二个区间的右端点 $=r$，且两段区间的异或和 $=s$，那么对于 $l'< l$，$[l',r]$ 一定也能找到。

所以考虑记 $g_{i,w}$ 表示以 $i$ 为右端点，找到两段合法区间异或和 $=k$ 的最右边的左端点，即一个 $\dots[\dots]\dots[\dots]$ 这样一个子结构的最右左端点位置。

那么在转移 $f$ 时只需要枚举 $i,j,k$，然后判断 $g_{j,s[i,k]}$ 是否 $>k$ 即可。此时 $f$ 的转移已经做到 $O(n^3)$ 了，但是我们仍然无法快速计算 $g$。

考虑再记录一个 $h_{i,w}$ 代表寻找一个 $i$ 左边的区间，且这个区间异或和 $=w$ 的最右边的左端点，即 $[\dots]\dots$ 这样一个结构，以 $i$ 为右端点，左边区间异或和 $=w$ 的最右左端点。

那么在转移 $g$ 时，考虑枚举 $\dots[\dots]\dots[\dots]$ 种右边那个合法区间的左端点，即对于 $g_{i,w}$，枚举 $j$，那么 $g_{i,w}\leftarrow h_{j,s[i,j]\oplus w}$。

而 $h$ 是可以在求出 $f$ 后直接刷表更新的，综上所有 dp 数组的转移复杂度均为 $O(n^3)$ 或 $O(n^2w)$，注意一下转移顺序即可。

P6682 [BalticOI 2020 Day1] 染色

想了好久啊，感觉那个人类智慧的做法确实不好想。

朴素的想法是直接二分，每次先把位置移动到 $1$，然后往后移动 $mid$ 的距离，这样的询问次数是 $2\log n$，无法通过，发现瓶颈在于每次想要二分一个值时都需要从 $1$ 开始移动。

如果我们能够找到一种移动方法，使得每次无论二分到哪个值，都能够成功的走过这个距离，那么就能够做到 $\log n$ 次询问了。

考虑极限情况，每次都往上二分，即 $\frac{n}{2},\frac{3n}{4},\frac{7n}{8},\dots$ 的情况。

接下来有一个非常人类智慧的做法，考虑倒序确定，假设最后会到达 $1$，那么倒序地左右交替跳，由于倒序情况下每次跳的长度都比上一次短，所以一定不会跳出界。

考虑如果有一次二分没有顶到上界，那么相当于整体的向左或向右平移，依旧并不会跳出界。因此我们可以直接跳来二分了，询问次数 $\log n$。

CF1622F Quadratic Set

结论题也算逆天题嘛。。。可能这才是真的逆天吧！

首先考虑 $n$ 是偶数的情况，设 $m=\frac{n}{2}$，那么有如下式子：

$$\prod_{i=1}^n i! =\prod_{i=1}^{2m} i! =\prod_{i=1}^m (2i-1)!(2i)! = \prod_{i=1}^m (2i-1)^2\cdot 2i=2^m\cdot m!\cdot(\prod_{i=1}^m (2i-1)^2)$$

• 如果 $m$ 是奇数，那么删除一个 $2$，删除一个 $m$ 后，式子变成 $2^{m-1}\cdot(\prod_{i=1}^m (2i-1)^2)$，是完全平方数。
• 如果 $m$ 是偶数，那么删除一个 $m$ 后，式子变成 $2^m\cdot(\prod_{i=1}^m (2i-1)^2)$，是完全平方数。

因此对于 $n$ 为偶数是，答案 $\ge n-2$，而对于 $n$ 是奇数，再删掉一个 $n$ 可以变为 $n$ 是偶数的情况，因此答案 $\ge n-3$。

接下来就比较套路了，对于每一个质因数随机一个 hash 值，做异或哈希，对于删除 $0,1,2$ 个数是容易判的，删除三个数的直接构造即可。复杂度 $O(n\log n)$。