CF2207G Toothless
link
trick：找到一个方案，总价值不小于 \(\frac 2 3 P\) 等价于 找到三个方案，总价值之和不小于 \(2P\)。
把网格按照 \((i+j)\bmod 3\) 三染色，枚举 \(k\in\{0,1,2\}\)，如果只染色 \(col_{i, j}\neq k\) 的点，会形成森林的结构。
接下来还要加入这样的 \((i, j)\): \((i, j)\) 是 needy 的，并且 \(col_{i, j}=k\)。在加入这样的 \((i, j)\) 后可能产生环，对于新产生的环我们要至少删掉其中的一个点。
注意到题目中保证了每个 needy 点周围的点都是价值为 \(a\) 的点，因此每次删掉环上的点时我们可以选择只删价值为 \(a\) 的。
如此可以得到三个合法方案。容易证明至少一个方案价值合法。
9642. 冲刺
link
本质调整法。
我们先考虑序列 \(a=[1\dots n,1\dots n]\)，接下来我们对 \(a\) 进行一些调整来满足 \(i\) 和 \(v_i\) 互相包含。
我们有一个想法是，对 \((i, v_i)\) 连边建树，对于奇数层的 \(i\)，在序列前一半中我们把它移到 \(v_i\) 前面去；对于偶数层的 \(i\)，在序列后一半中我们把它移到 \(v_i\) 前面去。
两边互不干扰，那么这样就做完了。
#9647. 数位 DP
link
结论：每次能得到的 \(m\) 一定是一段前缀 \([0, x]\)。
归纳证明：
- 如果当前的操作是 \(\texttt{and}\)，\(x\gets min(x, c)\)。
- 如果当前的操作是 \(\texttt{or}\) 或 \(\texttt{xor}\)，\(x\gets x \operatorname{or} c \operatorname{or} (2^{\operatorname{highbit}{(x\operatorname{and} c})}-1)\)。容易发现 \(or\) 和 \(xor\) 是等价的。
倒着考虑，我们已知操作完后的 \(x\) 的最小值，求操作之前的 \(x'\) 至少是多少。
- \(\texttt{and}\)：要求 \(c\ge x\)，\(x\) 不变，有方案数 \(2^k-x\)。
- \(\texttt{or}\)：相当于要求 \(x' \operatorname{or} c\ge x\)，从大到小依次判断每一位 \(p\)：
- \(c_p=0\)，保持原状。
- \(x_p=1, c_p=1\)，把 \(x_p\) 修改成 \(0\)。
- \(x_p=0, c_p=1\)，把 \(x_p\) 以下的位全部修改成 \(0\)，结束判断。
所以我们可以枚举 \(p\) 满足 \(x_p=0\)，这个 \(p\) 是第一个满足 case 3 的位置，则 \(>p\) 的位置可以选择变成 \(0\) 或不变，\(
的位置全部变成 \(0\)，且这样有贡献系数 \(2_p\)。另外还有不存在 \(p\) 的情况，可以视作 \(p=-1\)，贡献系数为 \(1\)。
由此可以得到一个 \(O(2^{P}nqP)\) 的做法，其中 \(P=\operatorname{popcount}(m)\)。
考虑利用模数 \(2^{32}\) 性质，我们把 \(\texttt{and}\) 操作中 \(2^k-x\) 拆成若干个 \(2\) 的幂次之和，相当于每次可以选择 \(2^k\)，或者钦定 \(x\) 中第 \(p\) 位是 \(1\) 并乘上 \(-2^p\) 的系数。
考虑第 \(i\) 个位置的 \(\texttt{or}\) 操作，我们发现其选则的位置 \(p\) 必须 \(<\) \(1\dots i-1\) 操作钦定最小的 \(x\) 为 \(1\) 的位 \(d\)。由于我们是倒着做的，在 \(i\) 之前我们都不需要考虑 \([0, d-1]\) 的位置的值，所以这样选对于 \([0, d-1]\) 的位来说贡献就是 \(2^d\)。
我们还需要计算目前 \(>d\) 的位的贡献系数。设这个位置 \(p\)，在 \(y\) 的位置第一次被钦定为必须选 \(1\)，在 \(x\) 的位置第一次大于目前的 \(d\)，那么在 \([x, y]\) 的范围内，\(x_p\) 可以选择在任意一个 \(\texttt{or}\) 操作时变为 \(0\)，或者在 \([x, y]\) 的范围内始终保持 \(1\)，那么贡献系数就是 \(cnt+1\)。
理论部分完毕，接下来考虑具体操作。
枚举每一个操作，维护一个状态 \(a_i\)。
- \(a_i=0\) 表示 \(x_i\) 还没有钦定成 \(1\) 过。
- \(a_i\ge 1\) 表示 \(x_i\) 已经被钦定为 \(1\) 了，且在 \(i\) 作为前缀最小值 \(d\) 时，进行了 \(a_i-1\) 次 \(\texttt{or}\) 操作。
我们发现对于一个状态其贡献系数一定时 \(2^{\sum ia_i}\) 的倍数，那么我们令 \(a_0\gets \min(a_0, 1)\)，有值的 \(a\) 就一定是 \(31\) 的一个拆分数了，状态数不会很多。
在转移时，如果是 \(\operatorname{or}\) 操作，将系数乘 \(2^d\) 并令 \(a_d\gets a_d+1\)；如果是 \(\operatorname{and}\) 操作，可以选择系数 \(2^k\)，或者选择钦定一个位置 \(p\) 并带有 \(-2^p\) 的系数。接下来分三类讨论：
- \(p\) 已经出现过，那么什么都不用管。
- \(p\) 没有出现过，并且 \(p：那么更新 \(d\) 即可，令 \(a_p\gets 1\)。
- \(p\) 没有出现过，\(p>d\)：先令 \(a_p\gets 1\) 并我们要计算 \(p\) 这个位置的贡献即 \(cnt+1\) 的值。
最后对于每个询问 \(m\)，对于一个钦定了 \(msk_i\) 内元素的状态 \(i\)，只要 \(msk_i \subseteq m\) 即可把状态 \(i\) 统计到答案里面。
这样这道题就做完了，复杂度 \(O(S(k)k(n+q))\)。
#9911. 路南柯
link
为了方便描述翻转题目中拓扑序列的定义。
先考虑这道题的 checker 该怎么写，给定 \(k\) 个拓扑序 \(a_0,\dots,a_{k-1}\)，如何确定只能生成唯一的树 \(G\)。
目前我们可以确定的边有 \(k\) 条边，\((a_{i, 0}, a_{i, 1})\)，我们发现对于这样的 \(a_{i, 0}\) 或者 \(a_{i, 1}\)，如果它出现在了任意一个序列的末尾，相当于它是一个叶子，而它唯一的一条连边已经确定了，那么我们就可以在 \(k\) 个序列中删掉这个点。如此操作，如果最后可以把序列给删空，那么树的个数唯一；否则不唯一。
接下来考虑构造方案。假如我们已经得到了一个删叶子的序列 \(p\)，那么我们首先在答案中加入 \(\operatorname{rev}(p)\)；接下来对于每一个叶子 \(u\)，我们都加入一条以 \(u\) 为根的拓扑序，每条拓扑序都至少可以删掉 \(u\) 到 \(u\) 的某个祖先 \(v\) 上的所有节点，满足 \((u, v)\) 链上没有其他儿子。
上面的做法直接暴力做序列个数是 \(leaf+1\)， 期望 \(\frac n e+O(1)\)，可以得到不少分。考虑正解，我们发现对于一个以 \(u\) 为根的拓扑序，如果我们选择在 \(u\) 的拓扑序内删掉 \(u\) 的祖先 \(x\)，我们发现只要 \(x\) 的子树内没删掉的点中只存在叶子就可以把 \(x\) 和这些叶子都删掉。这样最后序列个数就是，删掉树目前的叶子后，树存在的叶子个数。可以证明这样就是最优的，那么这个题就做完了。
CF1779G The Game of the Century
link
结论：记三个顶点为 A，B，C，如果这三个点能互相到达，那么图中每个点都可以到达其它点。
否则这三个点之间的路径类似 A->B，A->C，B->C，问题被等价于我们要反转尽可能少的边使得 C 可以到达 A，等价于每条有向边有一个权值 \(0\) 或 \(1\)，然后我们要找到 C 到 A 的最短路。手玩可以发现只有距离三个长度为 \(n\) 的边最近的、方向和他们相反的边是有用的，一共六条边，分类讨论答案即可。
P12478 [集训队互测 2024] Désive
link
一个区间的答案形式：选择一个点 \(u\)，删掉 \(u\) 到根的路径以后其它完整子树 siz 之和的最大值。
如果 \(a\) 是一个排列，那么每个子树只会被填满一次，当一个子树 \(u\) 内的数第一次完整后，我们去更新 \(u\) 的兄弟子树内每个点的答案，这样复杂度就是对的。
现在 \(a\) 不是排列，每个子树会被填满多次，设之前子树内能被填满的最大时刻是 \(t'\)，现在是 \(t\)，那么我们只关心其兄弟子树在 \((t', t]\) 内的所有贡献，拿个 trie 维护一下，每次删掉目前出现时间最小的点，复杂度 \(O(n^2 2^n+nq)\)。
P12488 [集训队互测 2024] 轮盘赌游戏
link
发现信息可以用半群维护。
当 \(d=1\) 时我们用类似线段树的结构表示出 \([1, m]\) 的半群信息；然后再类似倍增地把它复制出 \(n/m\) 份，再拼上末尾的 \(n \bmod m\) 个元素，那么我们就表示出了这个长度为 \(n\) 的序列。
如果 \(d=1\) 带修，我们用类似可持久数据结构的形式，记录合并出每个半群信息的左儿子和右儿子，修改时只需要修改 \(\log n\) 个节点即可。
如果 \(d\neq 1\)，考虑上万能欧几里德，维护直线 \(y=\frac {dx} n\) 在 \([0, n-1]\) 上的形状，同时维护一个变量 \(pos\)，相当于：
- 每次遇到一条竖线，将 \(p_{pos}\) 加入半群信息，同时 \(pos\gets (pos+d)\bmod m\)。
- 每次遇到一条横线，\(pos\gets (pos-n)\bmod m\)。
用万欧维护这个过程即可。
P8995 [北大集训 2021] 随机数据
link
在 \((i, i+d)\) 之间连边，把问题放在环上，我们发现 B 最后取的最大价值等价于，把边 \((u, v)\) 的权值看成 \(\min(a_u, a_v)\) 后的最大匹配。
接下来的做法与 P12488 [集训队互测 2024] 轮盘赌游戏 本质相同。
P17724 [SCP-S 2026] 路短最 / path
link
我们发现这个算法类似于用 dfs 去搜最短路的过程。
建出圆方树，我们发现在经过第一次 dfs(u) 之后，\(u\) 子树内所有点 \(v\) 的 \(d_v=d_u+\operatorname{dis(u, v)}\)；当下一次 dfs(u) 时，我们实际只需要知道距离上一次更新两个 \(d_u\) 的差值即可，由此设计出 dp 状态，用长链剖分优化转移，容易得到一个 \(O(n+m)\) 的做法。
P17725 [SCP-S 2026] 大雨 / rain
link
如果存在一次操作使得 \(p=n\)，问题相当于我们把原序列分成一些段，在给每个段独立异或一个值后，让整个序列递增。我们发现段与段直接是互相不干扰的，因为我们可以给第 \(i\) 个段异或 \(i\times 2^{32}\)，所以贪心地划分每个段即可。
如果不存在一次操作使得 \(p=n\)，相当于我们给一个前缀划分段并独立异或一个数 \(x\)，对于一个后缀我们不进行操作。此时每个段之间就有影响了，我们无法采用刚才的方法给每个段异或 \(i\times 2^{32}\)。
此时可以设计一个 dp，\(f_{i, j}\) 表示对前缀 \([1, i]\) 操作 \(j\) 次，操作完后的 \(a_i\) 至少是多少，复杂度 \(O(n^3\log V)\)。
不过注意到，如果不存在一次操作使得 \(p=n\)，其获得的答案至少为 \(g_n-1\)，其中 \(g_i\) 表示只考虑 \(a_{1\dots i}\)，操作 \(p=i\) 的最少段数，于是我们只需要保留 \(j=g_i\) 的 dp 状态就行了，时间复杂度变成 \(O(n^2\log V)\)。
用形式化语言刻画一下目前的转移状态：对于满足 \(g_j+1=g_i\) 的 \(j\) 和满足 \((j, i]\) 区间异或 \(x\) 后递增，且 \(a_{j+1} \operatorname{xor} x \ge f_j\) 的 \(x\)，有转移 \(f_i\gets \min(f_i, a_i\operatorname{xor} x)\)。
其中 \(g_j\) 单调不降，所以所有 \(g_j+1=g_i\) 的限制条件相当于分层转移。等价于我们要维护以下的操作：
- 在集合 \(S\) 中加入所有满足 \(a_{j+1}\operatorname{xor} x\ge f_j\) 的 \(x\)
- 删掉集合 \(S\) 中第 \(k\) 位为 \(v\) 的所有元素
- 查询 \(\min_{x\in S}({a_i\operatorname{xor}x})\)
用动态开点的 trie 维护。每个节点 \(u\) 维护 \(tag_u\)，表示当前节点为空/当前节点最大被时间戳为 \(tag_u\) 的标记覆盖。对于删除操作开一个全局变量维护，每次查询时，如果当前 \(u\) 节点最大的时间戳也小于覆盖了 \(u\) 的最晚的删除操作，那么 \(u\) 就是一个空节点，给它打一个标记。这样是势能均摊的，时间复杂度 \(O(n\log V)\)。
CF2262E Paired Bracket Sequences
link
二项式反演，转化为钦定 \(i\) 个括号位置相同的方案数。记 \(f_{i, j}\) 表示长度为 \(2i\)，有 \(j\) 对括号匹配的方案数，有一个非常厉害的转移方式：枚举插入任意一对匹配的括号，设其外面长度为 \(k\)，那么其有 \(2k+1\) 种插入方法，则贡献为 \(f_{i, x+y+1}\gets f_{k, x}\times f_{i-k-1, y}\times (2k+1)\)，但是这样一种方案会被 \(j\) 对括号都贡献一次，于是令 \(f_{i, j}\gets f_{i, j}\times \frac 1 j\)，拉插优化乘法，时间复杂度 \(O(n^3)\)。
CF2101F Shoo Shatters the Sunshine
link
考虑枚举有颜色的点的直径 \(2d\) 和中点 \(p\)。以 \(p\) 为根，如果此时深度为 \(d\) 的点两种颜色都存在那么答案就是 \(2d\)；否则答案是 \(d\) 加上另一种颜色的最大深度 \(s\)，容易前缀和优化做到 \(O(n^2)\)。
#21434. 信号网络
link
考虑子任务四，需要用到另一种求拓扑序的方法：我们任意取一个起点进行 dfs，每当一个点完成所有的后继的访问时将其加入序列，如果还有点没有被访问，那就再取一个点接着访问。最后将序列翻转就是一个合法的拓扑序。
于是我们可以通过这个做法获得一个任意的拓扑序：dfs 的时候对还没有访问过的点进行二分，得到第一个与当前有连边的点进行访问。由于子任务四保证拓扑序唯一，所以所求序列即为答案。
对于其它子任务，考虑增量构造。在求出任意一个拓扑序 \(p\) 的情况下，我们动态维护 \(p_0,p_1,\dots,p_i\) 形成的最小拓扑序。每次新插入一个点 \(x\) 时，我们二分找到原来拓扑序内连向 \(x\) 的最后一个点，在这个点之后，我们找到第一个 \(>x\) 的点，将 \(x\) 插入即可。由于每个前缀都是一个合法拓扑序，其后面的点不会造成干扰，于是我们可以证明这就是可以得到的最小的拓扑序。最后询问次数为 \(2\sum_{i=1}^{n-1} \lceil \log_2(i) \rceil+2n-2\)。
#21432. 经典题
考虑反悔贪心，先让所有任务都获得奖励，然后从左到右扫描以 \(i\) 为右端点的所有区间。如果有一个区间 \([l ,i]\) 满足这个区间内任务个数 \(>i-l+1\)，那么找到这样的最大的 \(l\)，并取出一个完全在 \([l, i]\) 区间内的任务 \(id\)，满足 \(r_{id}\) 最大，让任务 \(id\) 不再获得奖励。线段树维护之。
P9293 [ROI 2018] Addition without carry
link
首先我们容易给出一个判断 \(ans\) 是否合法的方法： 从高到低枚举每一个位 \(p\) 满足 \(ans_p=1\)，取出目前最大的 \(a_i\)。
- 如果 \(|a_i|>p\)，那么无解；
- 如果 \(|a_i|
，那么我们把 \(a_i\) 删掉继续做；
- 否则我们把 \(a_i\) 的最高位删掉，把新的 \(a_i\) 丢入数组中接着做。
考虑分析一下 \(ans\) 的最高位 \(p\) 应该满足什么条件。首先 \(p\ge \max_{i=1}^n {|a_i|+i-1}\)，否则就算是全 \(1\) 也删不干净；其次 \(p\le \max_{i=1}^n {|a_i|+i}\)，因为此时全 \(1\) 的 \(ans\) 可以保证每一位操作但是情况 2。
也就是说我们实际上只需要判断 \(p\) 能否是 \(h=\max_{i=1}^n |a_i|+i-1\) 即可。
定义一个函数 solve(a, p) 表示当前 \(a\) 数组，能否让 \(ans\) 的最高位 \(\le p\)，如果可以还要给出构造。如果 \(p 那么是无解的。我们先考虑能不能构造出 \(p=h\) 的解，取出满足 \(|a_k|+k-1=h\) 的最小的 \(k\)，我们发现 \(ans_{h-k+1}\dots ans_h\) 一定都是 \(1\)，那么我们把 \(a_1\dots a_{k-1}\) 都删掉，并删掉 \(a_k\) 最高位递归调用 solve(h-k)。如果不行，那么 \(ans_{h-k+2}\dots ans_{h+1}\) 必须全为 \(1\)，删掉 \(a_1\dots a_k\) 后继续调用 solve(h-k+1) 即可，此时必定有解。
用线段树维护之，可以证明这样子复杂度 \(O(\sum L \log \sum L)\)。
#20054. Don't Fight The Music
link
细节题，需要对这个题的条件有一个比较清晰的刻画。
先考虑 \(a,b\) 中所有值都确定了怎么做。
我们发现 \([i+1, n]\) 构成一段连续段等价于 \([1, i]\) 构成最多两个连续段，且每个连续段都 \(1\) 开头或者 \(n\) 结尾。
如果存在 \(a_i=b_{i+1}=1\)，说明 \(p_1\dots p_i\) 是 \(1\dots i\) 的排列，我们找到满足条件的最小和最大的 \(i\) 记做 \(x, y\)，我们发现对于 \(i 需要满足 \(b_{i+1}=0\)，对于 \(i>y\) 需要满足 \(a_i=0\)，而满足此条件的都是可以构造的。
否则不存在 \(a_i=b_{i+1}=0\)，此时有解必须要满足 \(a_i=1, b_{i+1}=0\) 的 \(i\) 都在 \(a_i=0, b_{i+1}=1\) 的 \(i\) 之前，且他们中间至少要隔一个 \(a_i=b_{i+1}=0\)，如果满足这个条件构造也是容易的。
我们已经刻画出了合法的充要条件，那么对于原问题，先 dp 出合法解再进行构造即可。\(O(n)\)。
#20061. Kikai No Tsubasa
link
将 \(p_i\le n/2\) 称为集合 \(A\)，\(p_i>n/2\) 的称为集合 \(B\)。\(A\) 内的元素任意连，\(B\) 内的元素无法相连，我们传入每个点 \(i\) 属于集合 \(A\) 还是 \(B\)，忽略 \(A\) 的内部连边，剩下的边构成一张二分图。
相当于我们要给每个 \(A\) 内的点分配一个权值 \(a_u\)，\(B\) 内的点分配一个权值 \(b_u\)，\(a, b\) 都是 \(1\dots n/2\) 的排列，需要满足对于每一条边 \((u, v)\in E\)，有 \(a_u\ge b_v\)。转化为我们要确定 \(A\) 集合的一个排列顺序，满足对于 \(A\) 集合的前 \(i\) 个元素，其邻边并集大小 \(\le i\)。
动态维护 \(A\) 排列后的前 \(i\) 个元素。删掉前 \(i\) 个元素在 \(B\) 中的邻边后，如果有一个点 \(u\) 满足 \(deg_u\le 1\)，那么直接把 \(u\) 作为 \(A\) 的第 \(i+1\) 个元素一定不劣；否则 \(deg_u\ge 2\)，我们发现这种情况出现次数不会超过 \(n/4\) 次，直接在第一次运行时，把此时 \(p_u\) 最大的 \(u\) 传入，在第二次运行时可以直接得到第 \(i+1\) 个元素是什么。
#20059. Incyde
link
记 \(E(k)\) 表示 \(k|gcd\) 的方案数，那么答案即为 \(\prod_{p\in\text{prime}} p^{\sum_{k\ge 1} E(p^k)}\)，记 \(q=p^k\)。
记 \(s_i=\frac{i(i-1)} 2, cnt_{p, r}=\sum_{i=0}^{n-1} [s_i=r]\)，那么 \(E(q)=\sum_r {cnt_{p, r}\choose m}\)，且只有 \(q|s_{n-1}\) 的才有值，这样的 \(q\) 只有 \(O(\log n)\) 个。
\(cnt_{p, r}\) 的计算等同于二次剩余，容易通过一些分析得到做法。
#21438. Another Story END
link
考虑 hash，给每条边随机分配一个 \([0, 2^{64})\) 的 hash 值，并保证每个颜色所有边的 hash 值异或起来为 \(0\)。记 \(h_u\) 表示根到 \(u\) 路径上所有边 hash 值的异或和，忽略 hash 碰撞，那么 \(h_u=h_v\) 当且仅当 \((u, v)\) 路径上没有坏颜色，由此得到一个 \(k=0\) 的做法。
对于 \(k=1\)，记录 \(s_i(u)\) 表示 \(u\) 到根路径上所有颜色为 \(i\) 的边的易或和，我们相当于要对这样的 \((u, v)\) 计算最大距离：对于 \(s(u),s(v)\)，他们最多只有一位不同。
先把所有 \(s(u)\) 完全相同的状态合并起来，维护这些状态的直径。考虑一个分治做法：solve(l, r, vec) 表示 vec 内的元素除了 \([l, r]\) 以外完全相同，对于树上的每一个节点用可持久化线段树维护 \(s(u)\)，在分治时，如果递归到左儿子，就按照 \([mid+1, r]\) 区间内的 hash 状态将 vec 内的元素分成若干类，对于每一类，如果这一类的元素个数 \(>1\)，那么就接着往左儿子递归。当递归到 \(l=r\) 时通过合并直径贡献到答案。
可以证明这样复杂度是 \(O(n \log n)\) 的。
#23679. Dyads of Hanoi
link
考虑已经确定了 \(A,B\) 如何判定方案数。
找到最大的 \(k\) 满足 \(A_k\neq B_k\)，记 \(A_k=x,B_k=y,z=6-x-y\)，有以下两种策略：
- \([1, k-1] \to z,k \to y\)
- \([1, k-1] \to y,k\to z,[1, k-1]\to x,k\to y\)
我们发现形如”让一些汉诺塔移到一个相同的柱子上”的最小步数方案数是唯一的，也就是说，想让最后的方案数为 \(2\)，我们必须要让上述两个方案步数相等。
记 \(f(C, x)\) 表示让序列 \(C\) 中的元素全都移动到 \(x\) 上面所需要的最小步数，那么判定条件即为：
数位 dp 即可，复杂度是一个大常数 \(O(n)\)。