2024 年 12 月做题记录

stardust_Ray · 2025-01-02 15:28:55 · 个人记录

12月1日

CF1188D - Make Equal

令所有数最后变成 (\max a_i)+x，然后考虑如何 dp。令 b_i\gets \max(a)-a_i，然后就是找到一个数 x 使得 \sum\mathrm{popcount}(x+b_i) 尽可能小。如果对每个 b 记录是否进位是不好做的，但是发现如果按照 \bmod 2^k 排序，那么只有可能是一段后缀进位，记录进位的后缀长度即可，时间复杂度 O(n\log V)​。

CF375E - Red and Black Tree

考虑令 f_{u,c,i} 表示 u 子树内有 c 个必须是黑点，其中控制 u 的是 i 的方案数，转移考虑枚举子树 v 中控制 v 的点 t，然后如果 i=t 有转移 f_{u,c+d,i}\gets f_{u,c,i}+f_{v,d,i}；如果 i\not = t 会发现只有 t 在 v 子树内同时 i 在 v 子树外才有用，所以求出 t 在子树内的最小值即可。其中第一维和第三维是 O(n) 的，第二维的合并是树形背包形式，所以是 O(n^3) 的。

12月2日

AGC009E - Eternal Average

和 To make 1 差不多的套路，把问题转化为求 x 的数量，使 x 可以被拆成 n 个 (\frac 1k)^a 的和，同时 1-x 可以被拆成 m 个 (\frac 1k)^a 的形式。对 x 在 k 进制下的每一位 dp，令 f_{i,j,0/1} 表示第 i 位时前 i 位的数位和是 j 同时最后一位是/不是 0 的方案数，然后能贡献的条件是 j\le n 同时 j\equiv n \pmod{k-1}，并且 ik-j+1\le m，然后暴力转移时间复杂度 O(nm)。

JOISC2020 - 治療計画

模拟赛搬过的题。考虑令 f_i 表示覆盖到 r_i 所需要的最小代价，转移考虑下一个点 j，那么转移条件就是 |t_i-t_j|\le r_i-l_j+1，容易证明正确性，显然有直接主席树优化建图的 2\log 做法，但是我们观察到权记在点上，所以可以用线段树找到可以转移的点直接赋值，时间复杂度 O(n\log n)。

12月3日

CF553E - Kyoya and Train

好题，令 f_{i,j} 表示第 i 个点到达的时间是 j 的期望花费，显然存在 O(mt^2) 的暴力转移。考虑优化，发现转移的过程是 f_{u,i} \gets c_e+\sum f_{v,j}p_{e,j-i}，是卷积形式，所以可以分治 FFT 在 O(mt\log^2t) 的时间复杂度内完成。

12月4日

CF1060F - Shrinking Tree

发现整个过程非常的不好维护。我们先一个暴力，枚举每一个边被删除的顺序，然后概率是容易求的。考虑如何用 dp 来优化这个过程，发现整个过程中需要继承的东西是对于最后若干次操作是否会更新根的 id，所以令 f_{u,i} 表示 u 子树内后 i 次操作不会改变根的 id 的概率，那么答案就是以每个点为根跑 dp 得到的 \dfrac{f_{u,n-1}}{(n-1)!}，考虑如何合并。

考虑求出由点 u 和 v 的子树构成的树的 dp 值 g_i。枚举合并 u,v 的时刻 j，对于 j\le i 有后 j-1 次不影响根，贡献就是 \frac{f_{v,j-1}}2，对于 j>i 依旧是相对独立的，贡献就是 f_{v,i}，这个东西可以用前缀和优化在 O(siz) 的时间内得到。然后合并就是直接用组合数做，时间复杂度是 O(n^3)。

CF566E - Restoring Map

首先我们发现对于两个点的集合，集合的交的大小和两个点的距离有关。当两个点距离是 3 的时候，集合的交的大小是 2 同时对应树上的一条边，以此我们可以找到树上的所有非叶子节点的连边，对于叶子节点，先找到它们对应的集合，然后删去叶子节点后就是它父亲的邻域集合，暴力匹配即可。用 bitset 优化，时间复杂度 O(\frac{n^3}w)。

qoj8049 - Equal Sums

令 f_{i,j,k} 表示 a 的前 i 项和 b 的前 j 项的差是 k 的方案数，直接暴力是 O(n^3V) 的。事实上，我们可以把 k 控制在 [-V,V] 的范围内，当 k<0 的时候只往 i+1 转移，否则只往 j+1 转移，用前缀和优化，时间复杂度 O(n^2V)。

12月5日

qoj8050 - Random Permutation

发现时限有 3s 同时有随机的性质，所以可以考虑设置一个阈值，把小于这个数设为 -1 大于的设为 1，对于每个数往两边找到和超过阈值的边界，然后由于随机的性质我们声称只有这段区间的子区间的中位数可能是这个数，暴力做即可。

CF1439D - INOI Final Contests

dp 状态是好想的。令 f_{i,j} 表示有 i 个位置，j 个人的答案，令 g_{i,j} 表示有 i 个位置和 j 个人的方案数。对于 i>j 的转移我们枚举最右段的连续的 1 的长度 k 那么有

这个是容易发现的。然后对于 i=j 的我们需要特殊的转移方法。我们枚举最后一个数最终到了哪个点，然后转移形如：

然后 O(n^3) 转移即可。

12月7日

P11288 - [COTS 2017] 模板 Z1

双倍经验：ABC262Ex。

考虑预处理出每个点能取到的最大值，然后对每个最大值分开做 dp 求出答案。令 f_{i,j} 表示前 i 个上一个取到最大值的位置是 j 的方案数，然后转移是全局乘，单点修改成全局和的形式。对于每个限制就是前缀赋值成 0，都可以记全局 tag 维护，时间复杂度 O(n\log n)。

qoj5434 - Binary Substrings

讲课题。首先本质不同子串数可以猜出上界，然后尝试构造。令 k 是最大的满足 2^k+k-1<n 的数，我们先要求出一段使得它包含所有长度为 k 的串，然后剩下的长度为 k+1 的不同。前半部分我们相当于要找到一个哈密顿回路，发现等价于 k-1 图上的欧拉回路，O(n) 找到即可。然后对于剩下的考虑剩下的图每个点入度和出度都是 1，也就是说是若干个环。然后一个个考虑，对于整个加入没有顶到上界的是容易处理的，顶到上界的取出一条链，然后把链的一个端点作为初始节点即可。时间复杂度 O(n)。

P6185 - [NOI Online #1 提高组] 序列

首先对于只有 2 操作，显然有缩掉每个连通块之后都有 a 的和和 b 的和相等，也就是一个连通块中可以保证和相等的情况下任意调整，也就是只用保留和的差。对于 1 操作，连边之后如果有奇环那么可以在保证奇偶性的情况下任意调整，否则奇层和偶层的差要保持相等，直接判断即可。时间复杂度 O(n)。

CF2026E - Best Subsequence

最大权闭合子图模板题。每个点往所有它包含的位连边即可。

CF1696F - Tree Recovery

发现我们只需要知道一条边就可以用类似 bfs 的方式得到整棵树，于是我们枚举 1 和哪个点有边，建出树后暴力判断每对点距离是否相同即可。时间复杂度上限是 O(n^4)。

CF1764F - Doremy's Experimental Tree

惊人的注意力。需要观察到对于 f_{i,i} 和 f_{j,j} 相比于 f_{i,j} 多算的只有中间一条链上的贡献，也就是对于 f_{i,i}+f_{j,j}-2f_{i,j} 这个东西实际上是路径长度除以 n，得到路径长度之后求出最小生成树就是答案。

12月8日

CF1444D - Rectangular Polyline

首先对于一种划分方案必须要满足水平的和竖直的都能分出一半。然后考虑分出一半后如何进行构造。我们令水平的把较大的集合中的边向右，较小的向左，竖直的边把较小的向上，这样就有 (X^+,Y^+),(X^+,Y^-),(X^-,Y^-) 三个部分。我们把它们排序，显然可以排序到整个图形是凸的，也就是不会有交。于是我们用 O(nV) 的 01 背包分出两个集合即可。

P5811 - [IOI2019] 景点划分

不妨设 A\le B\le C，然后显然满足 A 和 B 是最优的。首先考虑一棵树怎么做，也就是我们要断掉一条边使得两边分别 \ge A,\ge B，考虑找到树的重心，然后如果它存在一个儿子的子树大小 \ge A 就可行，否则不行。然后对于一个图，我们先找到 dfs 生成树，然后和树一样做。但是我们发现重心往上的这棵子树会有连向其它子树的边。那么我们可以一个个加入那些子树直到 \ge A，可以证明剩下的部分至少有一个 B 的连通块，输出即可。

ARC175E - Three View Drawing

首先考虑分组，发现可以把 (x,y,z),(y,z,x),(z,x,y) 分成一组，但是我们要保证没有遮挡，可以通过设置 x+y+z\equiv 0\pmod n 得到。对于 n\bmod 3=0 的情况我们有 3 个点可以调整，够用。但是对于 n\bmod 3\not=0 的情况我们只有 (0,0,0) 可以用来调整，对于 m\bmod 3=2 的情况就倒闭了。这个时候我们把 x=1,y=1 的组删掉，改成 (1,1,1) 即可。

P8866 - [NOIP2022] 喵了个喵

当 k=2n-2 的时候只用保留一个空栈就可以方便地做删除操作，每个栈内保留 2 个数字即可。对于 k=2n-1 只有在所有数字都存在的时候存在问题。我们找到下一个可能成为栈底的元素或它自己。如果是它自己那么就把它放进空栈中，然后中间正常操作，最后一步删去。否则如果中间出现的该栈的栈顶元素的数量是偶数，那么就把它放在该栈的栈顶，中间的栈顶元素会全部消掉，最后一步可以往空栈中放消掉，否则就放在空栈中，这样最后还会有一个空栈。

P7515 - [省选联考 2021 A 卷] 矩阵游戏

考虑如何从一个合法状态调整到每个数都在 [0,10^6] 之间。如果我们令每一行第一个数加了 a_i，每列第一个数加了 b_i，那么是 nm 个不等式的形式。如果我们把状态稍作修改可以转化成差分约束问题，用 bellman-ford 跑最短路即可，时间复杂度 O(nm(n+m))。

12月9日

P7115 [NOIP2020] 移球游戏

考虑当 n=2 的时候我们怎么做。首先我们有一种利用一个中间栈和一个空栈能对 01 栈排序的方法，就是我们从中间栈中取出 01 栈中 1 的数量个数放入空栈中，这样我们就有足够的计数排序，然后可以用简单的方法实现分离。当 n>2 的时候我们直接分治，每次把 \le mid 的记为 0，否则是 1，然后直接和上述过程一样做即可。

CF685B - Kay and Snowflake

有结论：一棵树的重心一定在根节点所在的重链上。一棵树的重心一定是以该树根节点重儿子为根的子树的重心的祖先。直接按照这个做就是均摊 O(n) 的。

P3345 - [ZJOI2015] 幻想乡战略游戏

发现这个位置就是全树的带权重心，然后我们的目标就是找到这个点。有性质：重心是满足 2s_x\ge s_1 的最深的节点，所以我们在线段树节点上维护子树大小就可以二分找到。因为每个点只有至多一个儿子可以成为这个点，所以本质是单侧的递归，所以是正确的。

对于答案的统计，我们发现答案就是 \sum dist(x,y)d_y=\sum dist(1,y)d_y+\sum dist(1,x)d_y-2\sum dist(1,lca)d_y，三个部分都是容易维护的，时间复杂度 O(n\log^2n)。

P5666 - [CSP-S2019] 树的重心

考虑每个点的贡献。我们将整棵树的重心提根，那么除了根以外每个点的子树大小都 \le \frac n2。对于一个非叶子节点，它能贡献的条件是另一个子树需要在一个范围内，这个东西会求错当且仅当这个子树是它的祖先或者在它子树内，这两个都可以在 dfs 的同时更新/容斥掉。然后考虑根的贡献量，显然也是子树大小在一个区间内的形式，这是容易计算的。

CF1842F - Tenzing and Tree

感觉是神仙题啊。拆贡献，发现是 \sum|k-2x| 的形式，x 表示一侧的点数。如果要拆绝对值，我们可以将重心提根。先枚举选的点的重心，那么我们发现可以去掉绝对值计算，那么就是 bfs 出的这些点最优。如果在 bfs 的过程中发现有出现负数，我们发现这并不影响答案。时间复杂度 O(n^2)。

12月10日

P9021 - [USACO23JAN] Subtree Activation P

最优 dsu on tree。首先我们考虑从一个子树到另一个子树所需要的代价，如果有包含关系那么就是 |siz_u-siz_v|，否则就是 siz_u+siz_v，如果我们把相邻点连上 |siz_u-siz_v| 的双向边，然后每个点和 0 连 siz_u 的双向边，那么问题就转化为求一个权最小的边集，使得这个边集经过所有点同时有欧拉回路。这个东西是可以 dp 的。我们设状态 f_{u,0/1,0/1} 表示 u 子树，是否和 0 连通，点 u 的度数的奇偶性，转移分讨 u\to v 边的选的数量即可，时间复杂度 O(n)。

P7782 - [MCOI-Zero / AC6-M03] Sipli Field

点分治模板题。每个点求出以它为端点的方案数后做子树求和即可。求方案数可以考虑容斥，可以做到 O(n\log n)。

P4886 - 快递员

神秘点分治应用。我们对于一个分治重心，处理出最大值，如果我们能知道往那边递归是最优的那么就做完了。如果我们处理出最大的路径，如果有两个分属不同子树那么这个就是最优解，如果横跨分治重心那么也是最优解，否则递归向那个有最大路径的子树，由于层数是 O(\log n) 的，时间复杂度 O(n\log n)。

12月11日

qoj7855 - 不跳棋

点分树模板题。直接建出点分树，然后记录最小次小指针，答案统计是简单的，因为 LCA 在子树内的贡献一直都会更劣，所以不需要去重。

loj160 - Knapsack Problem on Tree

我们考虑按 dfs 序倒序 dp。如果当前点不选，那么子树内的点都不能选，从 dp_{dfn_i+siz_i} 那里继承来，否则子树内的点可以选，那么就是从 dp_{i+1} 那里转移来，所以能做到时间复杂度 O(nW)。

12月12日

牛客186E - 旅行

直接用树剖+线段树维护背包的话显然会 T，考虑其它的做法。由于是路径查询，考虑点分治。我们先定位到点分树上的点，然后预处理出每个点到根的背包，然后查询只用查询两个背包合并后的 O(1) 个位置，所以时间复杂度可以做到 O(nk\log n+q\log n)。

CF917D - Stranger Trees

先用二项式反演把恰好 k 条改成至少 k 条，然后对于剩下的 n-k 个连通块，它们连成树的方案树是 n^{k-2}\prod siz_i，然后现在问题转化成贡献是每个连通块的大小的乘积的问题。如果暴力维护当前连通块的大小那么是 O(n^3) 的。我们把问题转化为每个连通块取出一个点的方案数，于是我们不用记录连通块大小只用记录是否选择，时间复杂度降到 O(n^3)。

P8935 - [JRKSJ R7] 茎

首先我们先用树上背包求出每个点子树内选择 k 个点删去的方案数，然后考虑统计答案的方法。我们从上往下遍历 1\sim x 的路径，令 g_{i} 表示当前点在操作前有多少个点已经操作过了。转移的时候先考虑当前点是否选择，然后这里的转移是后缀和形式。然后把其它子树合并进来，精细实现可以分析成小于树上背包，也就是 O(n^2)。

P8329 - [ZJOI2022] 树

感觉是神秘题啊。不知道为什么要容斥，但是容斥了好做 \inf 倍。我们先把问题容斥成令 f_{S} 表示第一棵树非叶子节点集合是 S 子集的方案数，g_T 表示第二棵树非叶子节点集合是 T 的子集的方案数，然后答案可以计算出是 (-2)^{n-|S|-|T|}f_Sg_T。然后令 f_{i,j,k} 表示当前前 i 个数有 j 个在第一个集合里，后 n-i 个数有 k 个在 T 里的方案数，转移考虑第 i 个点放在哪个集合内然后直接转移即可，时间复杂度 O(n^3)。

ARC087F - Squirrel Migration

发现每条边如果左右两边的大小分别是 s_1,s_2，那么这条边的最大贡献是 \min(s1,s2)。如果我们把重心提根，那么我们就是要让每个点指向不在这个子树内的点，重心可以任意匹配，然后容斥，转化成至少 x 个人匹配了同一个颜色的点。这个东西可以用背包合并，时间复杂度 O(n)。

CF724F - Uniformly Branched Trees

先取重心为根，然后令 f_{i,j,k} 表示当前加入了 i 个节点，根下面挂了 j 个儿子，然后最大的子树大小小于等于 k 的方案数，转移直接枚举当前大小的子树选了几个，输出的答案的时候还需要减掉存在两个重心且两部分不同的方案数。

12月13日

BZOJ4771 - 七彩树

考虑如果能离线怎么做。有一种扫描线做法。我们扫描深度加入，对于一个颜色我们要去除掉重复贡献，我们找到当前 dfn 在它附近的两个同色点，然后分别求出 LCA 在更深的那个 LCA 处单点减一，新加进去那个点单点加一。对于强制在线，我们用主席树维护即可。

Count Sequences

考虑对和是 n 的这个限制拆位，然后从小到大枚举每一位，状态里记录当前乘积和进位数量即可。转移是简单的。

12月14日

Make Grid Comparable

考虑如何求出一整个连续段全部被交换的最小次数。首先有区间 dp 的转移式，对于没有办法拆分的方式我们会有 r-l 次的可能性，也就是通过只交换行达成，对于这个我们记忆化搜索得出答案，统计是简单的。

P3749 - [六省联考 2017] 寿司餐厅

最大权闭合子图模板题，所有 d 的贡献连成一个三角形，每个寿司连向它的种类，然后直接跑最大权闭合子图即为答案。

12月15日

CF1110H - Modest Substrings

好题。如果我们尝试把 [l,r] 内的所有数字建成一个 ACAM 然后跑 dp 显然会 TLE，考虑如何压缩这个 AC 自动机。发现自动机上有大量的满 10 叉树，所以我们把每个满树只保留它的根，然后记录经过长度 len 以后会不会在 l\sim r 中，然后大力做 dp 即可。

ARC060F- 最良表現

首先我们大胆猜测结论对于不是由同一个字符组成的字符串第一问答案最多是 2，证明不会。然后接下来就是一车 KMP 板子判断原串是否是周期串以及用 exKMP 求出划分的两段是否是周期串。

12月16日

loj576 - [LibreOJ NOI Round #2]签到游戏

相当于 (i,j) 直接连接 \gcd(a_{i+1\sim j}) 的边权，然后求最小生成树。发现答案都呈现出一个前缀和 n 连接，一个后缀和 0 连接，然后就可以在线段树上二分出分界点然后分别求答案即可。

CF2034H - Rayan vs. Rayaneh

考虑如何判断解是否合法，也就是每个数必须为 \gcd 提供一个最小次数的质因子。也就是存在一个 G=p_1^{a_1}p_2^{a_2}...p_k^{a_k} 使得 \forall i \in [1,k],f(\frac{G}{p_i^{a_i}})>f(G) ，其中 f 表示 a 序列中该数倍数的出现次数（需要清晰的思考）。然后接下来我们发现令 p_1^{a_1}<p_2^{a_2}<\dots<p_k^{a_k}，有 p_1^{a_1}\le \sqrt V,\frac{G}{p_1^{a_1}}\le V，枚举两个部分求答案即可。

P4720 -【模板】扩展卢卡斯定理/exLucas

qoj5099 - 朝圣道

问题等价于可以走 2n 步，每一步随机往左右走 \frac 12 格，求期望。然后可以写出式子 2\sum\limits_{i=1}^ni\binom{2n}{n+i}，然后推式子

然后用 exLucas 解决即可。记得写成查询两 log 的，不然会 TLE。

12月17日

qoj2562 - Fake Plastic Trees 2

神秘题。有一个暴力，记录 f_{i,j,k} 表示以 i 为根，里面有 j 个连通块，当前连通块大小是 k 是否可行，然后我们考虑优化掉最后一维。我们将 f_{i,j} 作为一个集合，如果集合内有 a,b,c 三个元素满足 a<b<c，那么如果 c-a\le R-L 那么 b 是没有用的。而且最后一维的极差最多只有 j(R-L) 所以集合大小可以保留成 O(k)，这样我们就可以做到 O(nk^3)。

qoj6194 - Knapsack Problem

神秘 trick。对于小范围的问题，考虑数位 dp。令 f_{a,b,c,d} 表示四维上的进位量，然后 dp 的时候从高位往低位逐位 dp 每一位上的值，这样可以有一个 O(32^k\log V)。我们发现进位量并不会卡满到 15，事实上只用 7 就已经足够，所以时间复杂度降到 O(16^k\log V)。

qoj7301 - Even Three is Odd

较为简单的 dp 题。记 f_{i,j,k} 表示已经确定了前 i+j 项，\max(x_i,x_{i+1},x_{i+2})=x_{i+j}=k 的答案和。转移是简单的，在转移的时候同时把方案数乘上去即可。时间复杂度 O(n^2)。

AGC058F - Authentic Tree DP

神秘题，我们考虑对每个边建一个点，然后为了让 \frac 1n 有更好看的形式，我们在每个点下面挂 mod-1 个点，这样我们就使得总点数等于 n。然后问题转化成求每个点赋随机实数权值，最终每条边中间的点权 都大于所有邻点的概率，这个是有向树拓扑序计数，所以 O(n^2)。

ARC157F - XY Ladder LCS

通过枚举长度为 3 的串，我们可以得到答案 \ge \frac{2n}{3}，也就是说匹配的两个点之间的距离 \le \frac n3，我们直接对这个东西状压即可。时间复杂度 O(n2^{\frac n3})。

CF1434E - A Convex Game

直接考虑 SG 函数，显然有一种 O(n^2) 的暴力 dp 做法。然后考虑如何优化。我们发现选出的子序列长度最多只有 O(\sqrt n)，而 SG 函数是长度量级的，所以 SG 的值域不大，所以换维然后用并查集做区间取 max 即可，时间复杂度 O(n\sqrt n\log n)。

CF1519F - Chests and Keys

首先如果我们确认了一个上锁的状态，那么 Bob 就是跑出最大权闭合子图然后如果等于 0 Alice 胜，也就是说所有物品的流必须全部流完，然后我们直接把锁一边的流量压进状态里，暴力转移即可。时间复杂度 O(nma^2\prod b)。

qoj4811 - Be Careful

神秘复杂度平衡题。考虑容斥，计算出所有 \le i 的答案。我们设置一个阈值，对于儿子个数 \ge B 的对儿子跑容斥，然后对 <B 的答案对于值是否存在进行容斥，通过精细时限可以通过。

qoj7737 - Extending Distance

首先让最短路变化是不好做的，转化成对偶图上的最大流变化，然后直接建图在最大流的残余网络上跑费用流即可。

12月18日

P3679 - [CERC2016] 二分毯 Bipartite Blanket

有结论：一个匹配能覆盖 S 当且仅当有一个匹配能覆盖 S\cap L 且有一个匹配能覆盖 S\cap R，然后两个部分都可以用 Hall 定理和高维前缀和求出，然后用双指针合并即可。

P3899 - [湖南集训] 更为厉害

长链剖分模板题。当 b 是 a 的祖先的时候答案是容易的，当 b 是 a 的儿子的时候我们需要做的是一个类似于 dep 上前缀求和的东西，可以通过大力打 tag 做全局加，然而我们每次只有在开头的单点扩展，所以可以通过打 tag 的方式做。时间复杂度 O(1)。

CF704D - Captain America

假设 r>b，问题相当于限制了每行/每列的蓝点的数量求最多的蓝点数量，这个东西显然有上下界网络流的做法，暴力建图跑即可。

CF843E - Maximum Flow

首先考虑如何满足最小割最小这一限制。我们对于所有没有流量的边，说明 u 必然能到 v，所以从 u 往 v 连 inf 边，对于其它的边我们建边 (u,v,1),(v,u,\inf)，然后在这张图上跑最小割，容易证明跑出的一定是可以满足的最小割，然后方案的构造就是一个上下界网络流。

CF1416F - Showing Off

简单网络流。观察到整张图连成一个基环树森林，考虑哪些点在环上。发现在环上的点 s 都相同，同时四周没有比它小的点一定在环上，所以跑二分图匹配即可，因为长度大于 2 的环都可以被拆成若干个等于 2 的。

12月19日

qoj1454 - Um nik's Algorithm

我们有定理：做 k 次增广之后假设现在的匹配大小是 x，那么 x\ge \frac{k}{k+1}ans，所以我们跑 19 次增广即可。

CF1284G - Seollal

神秘题。如果我们往 (1,1) 旁边加两个白点 (0,1),(1,0)，那么就有每个黑点度数 \ge 2，我们将黑点和白点跑出一组匹配，然后从白点往附近的黑点连边，从黑点往它匹配的白点连边，然后从没有被匹配的白点开始 bfs，如果能生成一棵树就是有解，合法性显然。时间复杂度 O(nm\sqrt{nm})。

联考20230314T2 - 海蛎海螺海胆

首先考虑重心的性质，是满足 s_x>\frac{s_1}2 的深度最大的点。如果我们能找到一个点在重心的子树内那么就可以在链上二分得到答案，显然我们求出第一个 dfn 序上前缀和大于一半的点，这个点必然在重心子树内。

联考20230304T2 - 偷笑

点分树模板题。

AGC036D - Negative Cycle

考虑用差分约束来转化条件，假如我们得到的解是若干个连续段，那么需要砍掉一些连续段内部的边和连续段之间的边。然后直接用暴力 dp 来描述这个过程即可。时间复杂度 O(n^3)。

12月20日

联考20230515T1 - 颜色

考虑统计所有出现次数是奇数的数量，然后就是简单的树上撒点分块即可。

联考20230606T2 - 失眠

神秘题目。很显然有一种状压所有祖先的做法和一个暴力用卷积合并的做法。我们考虑扩展第一个做法，发现只有它往上的几个重链的结尾的状态是有用的，所以我们只用状压这些点即可，时间复杂度据说可以分析到 O(n^{\log_23}m)。

CF1446E - Long Recovery

比较神秘的图论题，看了 sol 也不是很懂。首先考虑如何判断无解，显然如果黑点经过扩展可以扩展出一个环那么必然无解，因为不存在一个扩展方式使得白点能侵入这个环。然后考虑每次操作会改变什么，发现异色点对的数量在过程中会减少，一次操作减少 1/3，最坏情况的意思也就是说我们要最小化减少 3 的数量。首先一个连通块被删空的时候必然会减少 3，然后我们证明只有一种特殊的情况是会减少三的，也就是 (0,0),(0,1),(2,0) 形式，同时如果附近有任何一个点都不会，所以我们统计上述东西的数量即可。

P7450 - [THUSCH2017] 巧克力

好题。我们考虑只有 k 种颜色的时候怎么做，先假设没有中位数的限制，那么我们可以暴力状压 dp（最短路形式）。有中位数限制之后就是多加一维然后外面套一个中位数有关的二分。对于有多种颜色的情况，我们进行随机映射即可。时间复杂度 O(Tnm3^{k}\log nm)。

P5180 -【模板】支配树

12月22日

qoj9844 - Marriage II

如果只删一个点，那么就是在残余网络上找到包含 S 到它这条边的一个环，我们在 S 和 i 之间建立虚点 i'，那么能删去的条件就是 S 在残余网络上能到点 i'。如果选取的点是异侧的，那么直接把两边可行的点数相乘即可。如果选取的点是同侧的，那么我们要保证选取的两个环不交。也就是我们把原来图中的每条边中间都建一个虚点，那么条件就是两个点不能同时都被同一个虚点支配。也就是在支配树上两个点的所有公共祖先都不是虚点，这个可以直接在支配树上统计。时间复杂度 O(m\sqrt n+(m+n)\log(m+n))。

qoj1878 - No Rest for the Wicked

令 f_{x,u} 表示 u 点带有 x 的危险度的时候的最大价值。那么我们发现边有可能是双向转移也有可能是单向转移。双向转移的条件是 \max(c_u,c_v)\le x \le \min(t_u,t_v)，这个可以线段树分治+并查集维护，然后单向转移的条件是 c_u\le x \le \max(t_u,c_v-1),c_u<c_v 反向同理，这个也可以在分治同时更新，时间复杂度 O(n\log^2n)。

hdu6691 - Minimum Spanning Trees

神仙题。先考虑如何计算整张图联通的概率。令 f_{i,j} 表示加入 \le i 的边以后联通块大小是 j 的概率，g_{i,j,k} 表示在加入 <i 的边的时候大小是 j ，在加入 =i 的边后大小变成 j+k 的概率，那么 f_{i,j}=\sum_{l}f_{i-1,l}g_{i,l,j-l}\binom{j-1}{l-1}，最后一项是为了避免算重，然后考虑 g 如何递推。我们枚举加入的连通块的大小和数量，然后有转移式

这里的 t_{0/1,i,j,k} 分别表示两个连通块分别大小为 j 和 k 之间连边都 >i 的概率和连边都 \ge i 且存在一条边 =i 的概率。这个是可以直接预处理的。所以转移的时间复杂度可以做到 O(kn^3\log n)。

但是我们如果把边权和也记在状态里复杂度就爆炸了。然而我们发现都是 i 和 j 合并贡献到 i+j 的形式，所以我们将每个边权和的答案看成一个多项式形式，然后维护点值。也就是在加入一条边 w 的时候答案乘上 x^{w-1} 然后用拉格朗日插值把最后的多项式解析出即可。这样只用乘上 O(nk)，最终复杂度是 O(Tk^2n^4\log n)。

qoj7748 - Karshilov's Matching Problem II

我们可以用 exKMP 预处理 T 的每个后缀和 S 之间的 LCP，但是我们发现有一部分可能会到 R 外面去，不好用数据结构维护。我们可以二分找到第一个 LCP 超过 R 的点，然后这个点以前的贡献是容易的，这个点后面的相当于 S 的一个前缀，可以直接用 KMP 预处理，时间复杂度 O(n+m\log n)。

12月23日

ARC141F - Well-defined Abbreviation

我们的目标就在于找到什么样的串是不合法的。我们有一种感觉，如果存在两个串分别是 A+B 和 B+C(A\not=C) 形式那么就不合法。然后直接在 AC 自动机上做匹配即可。时间复杂度 O(|\Sigma|\sum|s_i|)。

P5287 - [HNOI2019] JOJO

考虑维护跳 nxt 的过程中上一个能到达的在一个连续字符段末尾的位置，这个可以考虑 \log 个连续段的结论，然后只用跳 \log 次即可。对于答案的查询，我们直接在上跳过程中同时统计即可。对于版本问题，建出版本树即可。时间复杂度 O(n\log n)。

P4156 - [WC2016] 论战捆竹竿

我们发现就相当于每次长度可以加上 n-border 然后问最终能形成多少个 \le w 的值。我们考虑 border 可以划分成 \log 个等差数列的性质，对于每个等差数列 x,x+d,...x+ld 我们考虑用同余最短路解决，即我们考虑 \bmod x=i 的情况下能达到的最小的长度是多少，然后转移时就剖成 \gcd(x,d) 个环每个环上跑单调队列优化即可，时间复杂度 O(n\log n)。

12月24日

P1393 - Mivik 的标题

考虑维护 f_i 表示 S 第一次出现的右端点是 i 然后考虑如何把错误的容斥掉。首先对于 \le i-|S| 的是容易做的，问题在于 i-(|S|-border) 的情况。由于 border 形成 \log 个等差数列，所以我们可以直接对每个公差分开做前缀和。时间复杂度 O(n\log n)。

CF932G - Palindrome Partition

考虑如何刻画这个过程，我们发现如果我们把右半部分翻转一个个插入，形成 s_1s_ns_2s_{n-1}\dots 的串，那么答案就是把串划分成若干个回文串的方案数，然后由于回文后缀长度构成 \log 个等差数列，所以我们对于每个等差数列记录和即可，两个状态之间的变化量只有 O(1)，可以暴力维护，时间复杂度 O(n\log n)。

CF906E - Reverses

我们逐位插入，那么就变成划分成最少回文串（长度为 2 的不计入统计）的方案数，和上题一样做即可。

loj6070 - [2017 山东一轮集训 Day4] 基因

如果能离线，那么我们先扫描右端点，考虑如何统一加入一个等差数列。我们发现在原来状态的基础上每个等差数列加入区间拼在一起是连续的，也就是说我们可以直接计算区间的左右端点然后做区间加单点查询，然后强制在线我们就可持久化即可，时间复杂度 O(n\log^2n)。

12月25日

qoj5037 - 回文

全网三杀！考虑回文后缀只有 \log 个等差数列，如果我们要支持单点修改，我们就需要做快速合并。考虑合并 S 和 T 后新的回文后缀的回文中心的位置，有以下几种情况：

1. 回文中心在 T 内同时整个回文后缀都在 T 内，直接继承 T 的答案即可
2. 回文中心在 T 内同时整个回文后缀有一部分在 S 内，考虑通过 T 的前缀来更新。令 T 的前缀的等差数列呈现 A,AB,AB^2...AB^k 的形式，那么我们令 T=AB^kC，也就是说我们要在 S 的后缀内找到 C'B'^{k'}，由于 B 不是 C 的前缀，所以我们考虑两种情况：
3. 回文中心在 S 和 T 之间，只有 1 的贡献，判掉即可
4. 回文中心在 S 内，我们和第二种差不多的思路，考虑 S 的后缀的等差数列往左扩展出 T' 的贡献，令等差数列是 A,BA,B^2A,...,B^kA，那么我们还是一样的把 T 的前缀尽可能匹配出的 B'^{k'} 找到，然后考虑剩下部分是不是 B' 的前缀，和第二种差不多分讨即可。

然后每次合并后维护等差数列数量为 O(\log n)。发现还要动态维护哈希值，分块即可，时间复杂度 O(n\log n+q(\sqrt{n}+log^2n))。写了 5h。

12月27日

qoj9806 - Growing Tree

从下往上考虑每个子树内会冲突的点，然后割掉它向左右儿子中的一条边。由于最多决策树的深度只有 n，所以每次暴力决策，暴力查找的时间复杂度是 O(n4^n) 可以通过。

12月28日

qoj6102 - Query on a Tree

直接 dfs 时间复杂度是 O(\sum deg_i) 的，显然不对，但是我们可以对每个点记录 fa，然后只用判断 fa 是否在 S 集合内即可，这样就可以保证边数也是 O(\sum k) 的，时间复杂度线性。

qoj6110 - Squirrel Game

首先如果令 d_i=x_i-x_{i-1}-1，那么形式就是 d_i\gets d_i-x,d_{i+k} \gets d_{i+k}+x，于是我们只用考虑 k=1 的情况。我们发现其实就是从后往前取 d_n,d_{n-2},d_{n-4}\dots 跑 nim 游戏的答案。因为如果你当前处于 nim 的必胜态，那么不管对方怎么操作都会有对策。时间复杂度 O(n)。

12月30日

CF1608G - Alphabetic Tree

首先我们可以建出 SA，然后二分出哪一些后缀有路径 u\to v 作为前缀，如果直接暴力地写两个二分和树剖查询，时间复杂度是 O(n\log^3n) 的。但是我们可以直接遍历每一个剖出来的链然后在一个失配的链上二分，时间复杂度 O(n\log^2n)。

CF1801G - A task for substrings

考虑和 qoj7748 一样的想法，考虑线段树上二分找到靠右第一个可以拓展到左端点左侧的点，然后左半部分就是 s 的某个串的后缀，这个可以建出反串 AC 自动机线性预处理出。右半部分可以直接在 AC 自动机上扫 t，然后维护前缀和即可。时间复杂度 O(|t|+n|\Sigma|+q\log n)。

12月31日

P9482 - [NOI2023] 字符串

简单题。考虑限制的形式，要求 suf_{i}<pre_{i+2l-1} 同时 s_{[i,i+2l-1]} 不是回文串。如果没有回文串这一限制，那么我们可以建出 SA 然后直接扫描线。然后我们考虑减掉 suf_{i}<pre_{i+2l-1} 同时 s_{[i,i+2l-1]} 是回文串的数量，发现对于一个回文中心，它是否能对答案进行贡献是确定的。也就是说如果它在查询区间内，那么它是否贡献和查询的 i 无关，然后 manacher 预处理后跑二维数点即可。时间复杂度 O(n\log n)。后半部分也可以 PAM。