题4

P2704 [NOI2001] 炮兵阵地

古早的题目。注意到$m$很小，并且只关心上面两层的状态，所以可以直接压入状态。$f_{i,S,S'}$表示考虑到第$i$行，前两行中的第一行为$S$,第二行是$S'$。然后枚举当前行转移就行了。会爆。剪枝，把不合法状态判掉。然后枚举第$i$行的时候使用枚举子集的方法，然后就行了。数组滚动一下。

$f_{i,S}$表示以$i$为根联通了关键点的集合为$S$的最小代价。枚举根节点$i$，然后分成两种情况转移。如果树上$i$的度数为$1$，那么就找与$i$相连的内阁点$j$，用$f_{j,S}+w_{i,j}$来更新$f_{i,S}$。度数大于$1$,用$f_{i,T}+f_{i,S/T}(T\subseteq S)$。对于第二种情况就按照$3^k$枚举，第一种情况跑最短路。具体的。先枚举$S$，得到所有$i$的度数大于$1$的值。然后通过最短路更新度数等于$1$的值。为什么对呢？首先对于第一种转移时$f_{i,T},f_{i,S/T}$一定是正确的，但此时发现一些实际度数为$1$的方案就被贡献了多次，那么，最短路就是用来处理这种情况的。那么就好了。

P4127 [AHOI2009] 同类分布

就是发现数位和总共只有$162$种，所以可以暴力枚举数位和，然后跑数位$dp$，然后数位$dp$适合用记忆化搜索写，这样应该会快一点。

s21461

首先一个比较重要的性质就是我们可以让豌豆都排满，然后再把剩下的空格插进去。那问题就是找把$n$个豌豆紧密排布最后长度为$x$的方案数。那其实就是一个连续段。对于连续段问题我们可以考虑使用连续段$dp$。就是先放一下连续段，然后对于一个数，把他合并到其他连续段或者单开一个连续段，又因为这个题放豌豆时有$r$的限制，所以我们可以想到可以将$r$排序，这样放$i$的时候就能保证贡献只和$i$有关了。具体的我们设$f_{i,j,k}$表示说放了前$i$个，一共有$j$个连续段，使用了$k$的长度的方案数。容易想到的转移是把$i$放到一个连续段的左右两边或新开一个连续段。但是这样发现少了情况，就是$i$操作完以后再某个连续段的中间的情况。这种情况我们让$i$放到一个连续段的左边和一个连续段的右边来解决。式子是好推的。

总结：连续段$dp$，除了放到连续段左右两边和新开连续段的操作，还要包括使用当前值合并两个连续段的操作。

分糖果

这个可以二分是不难发现的，那如何判断是否可行呢？假设$k$颗糖果，有$x$个箱子，那么一共所需要的糖果数就是$kx$，设每个人向前$x$个箱子里面放了$c_i$个糖果，那么如果$\sum{c_i}=kx$那么就可以，因为顺着填就行。然后考虑什么情况下能凑出来$kx$，然后就是$\sum{c_i}$是有范围的，最大时就是$\sum_{\min(a_{i},x)}$。最小的是$\sum{a_i-\min(m-x,a_i)}=\sum{\max(a_i-m+x,0)}$。那么到这里$O(n\log^2n)$的做法就已经有了。就是开权值线段树然后二分套二分。然后直接线段树二分就是$O(n\log n)$了。

qoj7236

这个题还挺有意思的。首先考虑为什么定理成立。假设每个数出现的次数为$c_i$，那么交集总数就是$\sum_{1}^{2n}\binom{c_i}{2}$。假设不存在，那么总数就$\le(\frac{n}{2}-1)\binom{n+1}{2}$。并且考虑，交集总数的下界是什么，额，感性理解就是$c_i$取得比较平均的时候，就是$n\binom{\frac{n}{2}}{2}+n\binom{\frac{n}{2}+1}{2}$。就有不等式了。但是这个等式恒不成立，所以也就说明定理成立。接着我们继续考虑，就是暴力肯定过不了。那根据不等式的思路，我们考虑先找到一个集合，然后通过这个集合找另一个集合。假设一个集合与另外集合的交集总数为$C$，若$C>(\frac{n}{2}-1)n$，根据抽屉原理，一定会存在另外一个集合和他交集总数大于等于$\frac{n}{2}$，剩下就好说了，与其他的集合交集总数就考虑每一个数的贡献就行了剩下的跑暴力就行了。

qoj7258

$trick$太nb了！！！

就是把二维随机游走转化一下。因为二维随机游走$x,y$不是很独立，总有一个变而另一个不变。这时神级转化来了，换系，令$u=x+y,v=x-y$，此时$u,v$互不干扰，就是说，$u+1$时$v$可$-1$可$+1$，同理$u-1$。这就很好，在解决一些问题有奇效。
接着我们继续考虑，找的是期望多少个格子$\times 4^N$，其实就是找所有路径中不同各自的数量，那么考虑每一个格子的贡献，就是找经过这个格子的路径数是多少，进一步的就是找这个格子被第一次遍历到的方案数，然后再乘上一个系数。我们令$g_i$表示第$i$步时碰到了一个没走到的各自的方案数，然后后面的任意走，那$ANS=\sum_{i=0}^{N}g_i\times 4^{N-i}$。考虑求$g_i$。发现很难求，考虑拆到每个点上去求，设$G_i(P)$表示第$i$步第一次走到$P$的方案数是多少，发现还是不是很好求，但是令$F_{i}(P)$表示第$i$步走到$P$的方案数很好求，同时我们设$H_i$表示$i$步走回原点的方案数,因为有了上面的转化，所以不难得到$H_{2i}=\binom{2i}{i}^2$，那$F_{i}(P)=\sum_{j=0}^{i}G_{j}(P)\times H_{i-j}$又因为$\sum_{P}F_{i}(P)=4^i$，所以$F_{i}=\sum_{j=0}^{i}G_j\times H_{i-j}=4^i$，$F_{i},G_i$表示所有$F_{i}(P),G_{i}(P)$的和。到了这步就要结束了，因为$H_0=1$，所以$G_i=\sum_{j=0}^{i-1}G_jH_{i-j}$。那就做完啦！！（虽然可以生成函数做到$O(N\log N)$但是我不会）

好题！！好题！！！

补充：因为模数不是质数，所以应当采用递推的方法；若模数太小，则还可能用到lucas定理。

qoj17158

朴素的暴力就是看到一个回文串，就把他需要保证相同的点之间连上边最后找连通块数量就行了。这样肯定炸。然后就考虑能不能优化一下。当只有两个回文前缀是$x>y$，当$2y\le x$时，发现只需要保证$y$是个回文串，然后将再$x$中前缀$y$和后缀$y$对称一下，最后保证前后缀夹得中间的位置保证是回文串就行，因为前缀$y$的方案数确定了，那后缀也就确定了，所以答案就是$y$的方案数乘上中间是回文串的方案数就行了。接着是$2y>x$,发现前后缀之间有交集，交集大小为$2y-x$，并且$y$一定是$x$的一个$border$，因为$x$是回文串，回文串反过来还是原来的字符串。又因为$2y-x$是交集，所以是$y$的一个$border$，结合$y$是回文串，能得到$2y-x$也是回文串，所以可以把$x$限制变成$2y-x$的限制。那具体的算法流程就是每次找出最大值和次大值，然后进行上面的操作，一直下去，但是有个问题，当最大值和次大值操作一次后，可能最大值和次大值还是这两个数。所以我们考虑加速一下。操作其实就是将最大值$-2(x-y)$，也就是最大值和次大值轮流减，所以注意好边界然后直接一次性减完就行。

AT_arc214_f [ARC214F] Unpredictable Moves

网络流的建模太吃操作了，不过这道题似乎是经典题。

就是说，找到四联通路径。如果没有不能连续走两次同样方向的限制的话，那就是直接判定不存在第一行和第一列障碍的八连通就行了，但是有这个限制。我们考虑，如果让$\to\to$这样的路径可以走，就是$\to\uparrow\downarrow\to$或$\to\downarrow\uparrow\to$，只有当上下都有障碍的时候才不能走，同理先走上下也是一样的，也就是说，出了八连通，类似#.#的也算是联通，这样也不能走，总结就是曼哈顿距离不超过$2$的都算联通，那建图就建好了。。。剩下跑网络流找最小割就好了。建图时注意，起点是第一行和最后一列，汇点是第一列最后一行，所以建图的时候要考虑把距离那些边曼哈顿距离不超过$2$的点连上，并且$(1,2),(2,1),(N-1,M),(N,M-1)$慎连。并且不能少建边，加限制条件的时候要考虑是否有特殊情况，要不然会调很长时间。最后这道题卡常！！！！！！

这个转化需要记住，感觉很有用。

CF1517G

这个，他说的条件看起来很难搞，但是和老C的方块挺像的，都是找到一个相似的结构，然后建出来图最后跑网络流最小割。这道题呢，就是一个相似的结构是$(1,0)\to(0,0)\to(0,1)\to(1,1)$，$(0,1)$表示奇偶。那么就做完了！！只需要把图建出来跑最小割就行了。

总结：遇到有多个不可以并且在网格里面时，考虑不可以的相似结构，可能是格子的奇偶，也可能是格子的形态，或者是与格子周围的形态有关的结构，如果有这些的话，那么可以根据问题要求什么来决定是否采用网络流

代码源

这个前面的还好，就是排名一定相同这个结论也猜到了，更新权值也想到了。就是把$c_{i,j}$赋值成$max(pre_{i,j},suf_{i,j}+k)$，$pre_{i,j}\text{表示}\max{k=11}^{j}c_{i,k}$，$suf$同理。最后的一步我的想法是每一行和每一列连边流量为权值，但是有两个问题。1.就是没有保证一个点只与另一个点匹配，2.边数太多的直接跑网络流会炸。解决方案呢？首先性质是$c_i$ 是单调不增的并且最大值与最小值差值不超过$k$这个通过更新权值的方案就能得出。那么我们考虑一开始就把所有最大值都加到答案里，把其他数都减去最大值。此时边权一定都小于等于$k$。那么我们考虑怎么减少边，因为好多相同的边权连到了不同的点上，所以我们可以考虑把右部点连成一个链，就是让$i\to i-1$因为$c_i$是单调不增的。然后让$i$向边权相同的最大的$j$连一条费用为$v$流量为$1$的边$v$就是边权，这样保证了一个边只会匹配一次。,$s$向行连费用为$0$流量为$1$的边，这样保证了每一行只会匹配一次，每一列向$t$连一条费用为$0$，流量为$1$的边。然后跑费用流，这样能找到答案了，边数是$nk$，点数为$o(n)$。玄学网络流应该能过。

总结：遇到只能匹配几次的问题，可以让流量为几，然后贡献作为费用，最后跑费用流；如果一个点有好多个相同边权的出边，可以看这些出边的出点是否是连续的考虑是否能够优化建边。

代码源/qoj17177

这个有一个转化场上想到了。就是没有完全匹配上的$i$，他们的$b_i$一定会组成若干个连续段，并且每个连续段对应的$a_i$的最小值就是这个连续段的最小值。但是这个结论太丑了，根本没办法往下做。一个优美的转化是，每个$[a_i,b_i]$之间的数一定至少存在有一个。那么这个就等价于$\cup [a_i,b_i]\subseteq \left\{b_i\right\}$，但是又因为$[a_i,b_i]$中一定存在$b_i$，所以$\left\{b_i\right\}\subseteq \cup[a_i,b_i]$，所以$\cup [a_i,b_i]=\left\{b_i\right\}$。那我们就转化成了集合之间判相等。那又因为$b_i\in[a_i,b_i]$，所以只需要判断集合大小就行了。那把$a_i,b_i$看作先端短点，那就变成区间线段的并。这个用珂朵莉树维护。剩下的就简单了。

AT_arc156_f [ARC156F] Make Same Set

这个题暴力应该能用费用流，但是太暴力了，复杂度太高了，所以要写网络流。

首先这个题是可以转化成匹配问题的，就是第一种选法和第二种选法他们共有的权值进行匹配。费用流就是第一种方式的点在左部点，权值在中间，第二种方式在右部点，然后方式与能连的权值连一起。然后呢，网络流与他图练法一样。首先一个假做法是直接跑网络流，此时可能有的点对应的中间点的流量都为零，也就是没选，这是不合法的，称这些点为待选点。这种做法适用于选$a/b$或不选。我们希望最终的图是不存在待选点的，所以我们考虑一开始先通过某种方式流一下，使图上没有待选点，然后再多次增广，保证每次增广的时候不会出现待选点。如何保证。待选点出现的时候就
说明有中间点的流量变为了$0$，就说，有右部点通过中间点再走到了左部点，我们成新出现的待选点是$i$（假设在左部点），通过的中间点为$j$，因为$i$是待选点，所以$i$和谁都没有流量，所以我们就可以通过$i\to j\to\cdots$，进行增广，避免了出现待选点。这样的路径特征是什么呢？短，就是比出现待选点的路径要短。并且只要有待选点就能继续短下去，所以只需要找最短路增广就行了。那$dinic$本来就是找最短路进行增广，所以就直接做了。而一开始的时候怎么保证没有待选点呢？只需要让$a_i$这个中间点有流经过就行了，这样每个左右部点不是待选点了。那就好了

暴力好打；不同方式构造出相同的集合，可以通过匹配的思想转化题意；想要让一个状态避免出现，可以先构造没有这个状态的东西，然后保证在后面的操作中不出现新的这样的状态就好了。

写的时候真是糖丸了。1.修改中间点之间的路径时，下标应当用离散化后$a_i$，而不是$i$，2.输出是要输出离散化之前的东西。

F - Constant Sum Subsequence

这个暴力的想就是设$f_{i}$表示把所有$i$的数的划分都找出来最短需要$f_i$的长度，然后就枚举一个$x$将$nxt(f_i,x)$贡献到$f_{i+x}$上$f_{i,x}$取$\max$，因为要满足所有的。$nxt(f_i,x)$表示$f_i$后面第一个$x$的位置。直接做$O(S^2\log^2 S)$的。肯定过不了。这时我们向分治去$N$，$l,r$分成两半，左边自己贡献完后给右边贡献然后右边再自己贡献。但是复杂度没变啊。这时候就需要性质了，$f_i$一定是单调不降的很显然，那么如果$nxt(f_i,x)$还没有$f_mid$大，那他转移过去一定没有意义，因为不如用$f_mid$转移。因为不管怎么说$nxt(f_{mid},i+x-mid)$一定大于$nxt(f_i,x)$。所以我们只进行贡献$nxt(f_i,x)\ge mxt(f_mid,x)$这些值。但显然只能等于。所以就是找到$mid$前面第一个$x$的位置$pos$，然后找到第一个大于$pos$的$f_i$，将$nxt(f_{i\sim mid})=nxt(f_mid,x)$贡献到$i+x\sim mid+x$上，因为加的是一样的，所以可以直接用数据结构维护一下。这样复杂度就到了$O(S\log^2 S)$了，可过。

总结：遇到转移是单项的，我们可以考虑分治去做，一般需要再寻找一些性质，如单调性。

Spoonerisms

这个就是因为总长比较小，然后题目的意思就是，$A$的前缀加上$B$的后缀能得到一个串，$B$的前缀与$A$的后缀也能。那我们把所有串的前缀放左部点，后缀右部点，前后缀连边，如果出现了四元环就满足，所以问题转化成四元环计数。

怎么计：枚举四元环度数最大的点，找一条出边再找一条出边后标记节点，如果碰到已经标记的就是找到了。复杂度怎么分析。我们对第一次出边到达的节点进行统计、所有点都遍历他的出边的复杂度是$O(N)$，现在要找到第一次出边到达的点$u$被遍历的次数是多上就行了。发现一定$\le\min(\sum{i}[deg_i\ge deg_u],deg_u)$，如果$deg_u>\sqrt{n}$，那比他大的一定不超过$\sqrt{n}$个应为度数总共是$O(n)$，如果小，那$\min$就是 $\sqrt{n}$。所以最多遍历$\sqrt{n}$个，那复杂度就是$O(n\sqrt{n})$了。

qoj406

暴力就是对每个三明治钦定他先拿，然后建立出依赖关系，就是如果先拿他必须先拿谁，如果发现有环就不行，没环的化就找经过了多少个本质不同的三明治才停下。爆了。然后就是发现，处于上方的三明治一定依赖这个格子上方的三明治都拿走，也就是依靠上面格子中上方的三明治要先拿走，因为上方格子的下方不能先拿走，还有他自己再垫着。那么得到什么结论呢？如果钦定了是先拿这个格子上面的三明治，那么肯定要先拿左或右和上面的，然后上方的就和维护他自己时走的路径一样的，所以答案只需要加上左右走得到的本质不同的三明治就行了。那环呢？我们发现环最多再两种情况出现，在这样建图过程中，一个格子中的两个三明治都要先拿走，说白了就是自己依靠自己。第二种是向左右拓展的时候发现碰到了自己的来时路，也是自己指向自己，但是两次所指向的三明治是相同的。这两个都能维护，用两个bool数组维护。AT-hoc题我没招了。。。。

注意：在维护第二种环的时候，部分写法（我的）需要先把起点加入bool数组里，否则要调半天。

qoj8800

这个题用到了竞赛图的知识，具体来说就是兰道定理。
首先这道题建出来边就是一个竞赛图，因为是竞赛图，所以有一个优美的性质，就是缩完点后，强连通分量组成了一条链，并且拓扑序小的强连通分量的出边一定指向拓扑序更大的强连通分俩姑娘。所以判断是否支配就是说判断是否在同一个强连通分量里，或者谁的拓扑序更小。根据兰道定理我们能知道将出度$p$从小到大排序,满足$\sum_{j=1}^{i}p_j=\binom{i}{2}$的个数是强连通分量数，并且满足这样的$j$和上一个满足这个式子的$j'$中$p[j'\sim j]$所对应的原图的点构成了一个强连通分量，并且，满足按照这样找出来的强连通分量在原图的拓扑序递减。很优美的性质！！那么我们只需要找每个点的出度就行了。这个就是做四个三维偏序就行了，比较简单。

总结：像这样$1\sim n$之间每个点都会有唯一一条有向边的图也就是竞赛图，有很多好的性质，方便解题，所以要辨认出来。性质：缩点后成一条链，拓扑序小的向拓扑序大的分量连边；拓扑序小的强连通分量中点的出度严格大于拓扑序大的强连通分量中点的出度；兰道定理。

AT_agc035_d

最后的数一定是$a_1,a_n$为基础，将其他数加到这上面就是了。所以我们转向考虑求其他的数一共贡献了多少次。我们考虑，一个数累加到答案的次数与其旁边的两个数累加到答案的次数有关，所以我们统计的时候肯定就只能找连续的三个数了。不知道怎么想到的，就是倒着考虑，最后一个删的数$x$相当于与$1,n$连着，所以贡献次数就是$1+1$，倒数第二个可能再$1,x$之间，也可能是$x,n$之间，贡献就是$1+2$或$2+1$。这个启发我们找一个区间内最后一个被删的数是什么，这样他对答案贡献的次数就是左端点和右端点贡献次数的总和。然后再去找下两个区间，那么就是设$f_{l,r,xl,xr}$表示左端点是$l$，次数是$xl$,右端点是$r$，次数是$xr$他们对答案的最小贡献是多少。$f_{l,r,xl,xr}=\min(f_{l,k,xl,xl+xr},f_{k,r,xl+xr,xr})$。但是数组开不下，因为次数最大值应该是斐波那契数列。所以使用记忆化，那复杂度呢？我们设$T(n)$为区间长度为$n$所需的时间是多少，$T(n)=\sum_{T(i)+T(n-i)}=2\sum_{T(i)}$。然后我不会算了。但是结论是$T(n)$应当是$3^n$次方级别。但是$n$是$18$，不过因为$a_1,a_n$一定不删，所以实际上长度是$16$，所以$3^n$就过了。

总结：正难则反，正着想不太好想的时候应该反过来想，尤其是这种一步一步操作的。还有例如Kocke也是反过来想回简单很多。

qoj7348

这个是拓扑序，还有dfs序版本，原理相同。
其实就是疯狂求组合数。首先计算一个$g_{i,k}$表示把$i$的子树删完后$i$的拓扑序是$k$的方案数，这个可做，但我做的时候有点晕。。思想就是用父亲的答案贡献给儿子，并且需要一个类似前缀和优化的东西。求出来这个后，再乘以写系数就是$f_{i,k}$表示$i$的拓扑序是$k$的方案数了。

总结：经典题目了，应该算是基础了。

AT_agc066_d

这个题的思路就是对着答案找性质，然后根据性质进行dp,答案有什么性质呢？性质是，在答案中，一段极长的$ABABABABAB$，他们中的$A$一开始也在这个区间内。证明，因为是极长，并且满足$A$不相邻，所以这个段周围一定还有$B$，形如，$BBABABABB$这样，如果$A$是从左边来的，那他会先遇到左边的$B$，变成$BABA\dots$，这样，其实就不需要再动了，再动就不优了，同理右边也是。那我们就证完了。所以我们在这样的极长的连续段后面进行$dp$，就是设$f_i$表示让前面都是$ABABABB\cdots BABABAB$这样需要的最小贡献。如果$i+1$是$B$的话，那$f_i\to f_{i+1}$。然后我们找一段极长的$ABAB$。但是贡献呢？我们发现这样好像没有办法统计贡献，因为$A$可能向右走可能向左走。暴力做复杂度就炸了。怎么办呢？我们考虑，根据高维前缀和的思想，转移几段短的和转移一段长的其实贡献是一样的。那我们就尝试贡献最短的$ABAB$，这样有什么好处呢？就是最短的里面$A$走的方向是相同的。把$A$当作$1$，$B$当作$-1$，因为是极短的，所以所有前缀和符号相同，所以$A$走的方向就是相同的。那么贡献就$O(1)$统计了。那就做完了。

注意：最后一个连续段可能是$ABABA$这样的形式，因为后面没$A$了，所以不需要保证有$B$隔开了，这样$dp$最后的时候就有点问题，不过没关系，我们在原字符串后面加上一个$B$就行了。相当于强制变成$ABABAB$了，这样就对了。

总结：性质！性质！性质可从答案中找到。如果碰到要转移很长一段而不好做时，考虑把这么一长段拆成等价的几个小段是否能做。

P11830 [省选联考 2025] 幸运数字

分讨就完了，就是枚举一个数或一个区间中的数是否可能成为中位数。

P11833 [省选联考 2025] 推箱子

使用数据结构维护模拟的过程就行了，就是加速模拟，把几步合起来做。

CF1404C

如果只有一个询问，那就设$f_i$表示从起点到$i$的权值是多少，$f_{i}=f_{i-1}+[f_{i-1}\ge a_i]$其中$a_i=i-a_i$。但是有多组询问。我的一开始做法是离线，然后考虑向做出来的区间前面加一个数。然后考虑答案是怎么变得。但是这样会炸，因为维护的复杂度能达到$n\log n$。炸了。被卡了好长时间。因为我们发现$dp$是从前向后进行更新的，所以向后加点维护起来就变得好多了。但是我们当前状态设的是起点到$i$的权值，所以我们需要改变一下状态。那显然起点就变成可变的了，终点要变成固定的。所以我们令$f_i$表示从$i$为起点到现在钦定的终点的权值是多少。那先后加一个点只需要将$f_i\ge a_i$的值都加一就行了。然后单调性是显然的，就是$f_i$肯定是单减的。那就没了。

P15649 [省选联考 2026] 找寻者 / recollector

场上想到$n^3$但是没调出来，痛失40分，警示，考场心态一定要好。
考虑拆贡献，这个比较简单了，最终的答案就是每个点为轻儿子的概率乘上$siz$，然后考虑如何求概率。我们想要知道概率，我们就要知道$u$这个儿子的重链长度，还要知道他外面的重链长度之和，所以两个$dp$数组就有了，$f_{u,j}$表示$u$所在子树重链长度为$j$的概率为多少，$g_{u,j}$表示与$u$同级的儿子重链长度总和为$j$的概率是多少。$f_{u,j}$由$f_{v,j-1}$和$g_{v, k}$推出。$g_{v,j}$本质是一个可撤销背包。详见写的另外一篇笔记。所以我们就再设一个$h_{u,j}$表示$u$的所有直接儿子重链总和为$j$的概率是多少。然后这个是树上背包。这部分需要注意一下，就是如果直接写循环的话，那复杂度会变成$\sum_{v}siz_v\times pre S,pre S$表示在$v$前面的儿子的$siz$和。这样会被卡。解决办法是什么呢，考虑每个子树的贡献，每个子树的贡献是$siz_v\times suf S$，$suf S$表示从$v$开始，他后面的(包括他自己)的$siz$和，但是这个是没有保证的，只有$siz_v\times(siz_u-siz_v)$是有保证的。那么我们直接取出最大的儿子，把他的信息直接付给$h$，然后其他的正常做，这样，每个子树的贡献就$\le siz_v\times(siz_u-siz_v)$了。这样就能过了。

这个不撤销背包的写法有点太唐了，这个相当于是填表法，复杂度可能到达$O(n^3)$，我们只需要使用刷表法，然后滚动一下数组就可以了。

总结：可撤销背包，树上背包，$siz_v\times(siz_u-siz_v)$是有复杂度保证的。刷表法和填表法变化一下。

P5904 [POI 2014] HOT-Hotels 加强版

简单版，$n^2$是容易做的。不说。这里是加强版。这个我不会设啊。设$f_{i,j}$表示$i$子树里到$i$的边数为$j$的点个数，$g_{i,j}$表示$i$子树里面满足$d(lca(x,y),x)=d(lca(x,y),y)=d(lca(x,y),i)+j$的$(x,y)$个数。然后考虑转移，对于一个$u$来转移$ans+=\sum{g_{u,0}},ans+=\sum_{x,y\in son(u),x\ne y}{g_{x,j}\times f_{y,j-2}}$。$g_{i,j}+=\sum_v{g_{v,j+1}},g_{i,j}+=\sum_{x,y\in son(u),x\ne y}{f_{x,j-1}\times f_{y,j-1}}$。$f_{i,j}+=\sum_{v,j-1}$。发下这个过程可以优化，就是类似于前缀和的内阁样子，那就做到$O(n^2)$了，然后呢，接下来就是长链剖分就优化到$O(n)$了。然后就没了。

注意：因为$g_{j}\leftarrow g_{j+1}$，所以指针要指向前面，也就是$g_{hson_u}=g_{u}-1$，所以要保证$g_u$前面有$dep[u]$个内存，但是又因为我们还要访问$g_{dep_u}$，所以还要保证后面又$dep_u$的内存，所以就需要开两倍内存。

总结：遇到三个点两两路径之间的交点，然后对这三个点统计答案的话，不一定只能在交点处进行统计，也可以在中间点枚举。在交点处统计可能需要写换根$dp$，并且可能没法优化，但是在中间点统计，记录一些辅助数组，然后进行统计，可能会好一些。

P14363 [CSP-S 2025] 谐音替换

这个转化有点太天才了。就是考虑$s1,s2$，他们前缀最长相同是$a$，后缀最长是$b$，不同的是$x,y$。对于一个$t1,t2$，类似的，有$at,bt,xt,yt$，能替换是什么，$xt=x,yt=y$，并且$at$是$a$的后缀，$bt$是$b$的前缀，所以其实就是找到xt,yt$和$x,y$位置，然后如果相同，就暴力向外匹配，能匹配成功就行。这时场上的思路，不会做了。那么怎么办呢？发现一个必要条件为$at+xt+yt+bt\in a+x+y+b$。但是这样是不充分的，因为即使匹配的时候，$xt+yt$和$x,y$可能是不对齐的，那么为了使他对齐，我们就引入特殊字符，即变成$at+?+xt+yt+?+bt\in a+?+x+y+?+b$，那这样就是充要了，然后就可以用AC自动机了。但是还有一个问题，匹配后要找到根链上的权值之和，但是不能直接维护到根链的权值和，因为这样计算的就是出现次数而不是出现的种类数的。但是呢，因为我们加入了特殊字符，所以这个题比较特殊，所以这个个数就是种类了，所以复杂度就对了。

总结：匹配时可以添加特殊字符使得匹配的位置限制在某个特殊的位置。

P15650 [省选联考 2026] 摩卡串 / string

这个是一个增量构造的过程。首先考虑一个怎么样的串严格比$S$小，可以分为两种1. 是$S$的真前缀2. 是$S$的一个真前缀+0+任意，并且$0$这个位置在$S$应当是$1$。那么我们从一个空字符串$t$开始向后加字符，第一种字符是好统计的，我们只需要记录没加这个字符的时候最长的$t$与$S$的一段前缀的相同的后缀是什么，也就是相当于在做$kmp$匹配。然后就跳$nxt$树判断有多少个能够匹配。第二种情况呢？直接统计是不太好的，但是我们其实可以钦定加的这个字符就是第二种情况的$0$的位置，也就是加的一定是$0$，这样，再向后加的时候这个位置就一定会产生贡献，所以我们只需要记录在加这个字符之前，$t$中有多少个第二种情况的字符串，然后累加就行了。然后我们要求的是最短的，然后就用最短路（这太神仙了。也就是用$BFS$就行。注意，还有$S$必须是$t$的子集的限制，这个我们需要在转移也就是$dp$过程中再加一个状态表示当前$t$是否已经包含了$S$，当最长的后缀长度到达了$n$就说明有$S$了。
详细的:$BFS(len,c,g,f)$代表最长的匹配长度，第二种情况的个数，严格小于$S$的个数，是否包含了$S$，从$(0,0,0,0)BFS$到$(\sim,\sim,k,1)$。但是这样是$n\times k\times k$的。好像会爆。不过我们考虑，如果现在有$c$个第二种情况的，那么必定会有$\frac{c(c+1)}{2}$个小于$S$的字符串。所以$c\le\sqrt{k}$，所以就能过了。

注意：因为是真前缀，所以如果$t$有与$S$相等的一个后缀，那么就要减去他的贡献。

总结：1.关于数量限制的可以采用增量构造的方法；2.$dp$也是一种图把，所以要找最小的答案是可以往最短路的方向去想；3.严格小于一个字符串有两种情况:1. 一个真前缀,2.真前缀后接一个比原来位置小的然后随意。

P15653

这个是个构造题，有点复杂了，前置知识是欧拉路径。具体在$oiwiki$或写的笔记；
他都写了$p\ge \frac{n(n-1)}{2}$。所以大概率次数就是$\frac{n(n-1)}{2}$。先不管这个。首先转化一下题意，这个题的操作相当于是$\oplus 1$，把输入的边不存，存下没输入的边，这样问题就转化成了剩下的边最少。首先我们可以通过操作异或出来一个偶数元元环，具体的，如果我们想异或出来一个四元环$a-b-c-d-a$，那么可以进行四次操作：

\[\begin{aligned}\newline (a,b,x_1,x_2,\dots,x_{k-1})\newline (b,c,x_1,x_2,\dots,x_{k-1})\newline (c,d,x_1,x_2,\dots,x_{k-1})\newline (d,a,x_1,x_2,\dots,x_{k-1}) \end{aligned} \]

这样就能在不影响其他边的情况下构造出四元环了。有了四元环，我们可以做什么，定理是，如果一个图是欧拉图并且边数为偶数，那么就可以通过四元环的方法把这个图都消去，具体的，$a-b-c-d-e-f$，那么就可以消去$1-a-b-c-1$，这样就变成了$1-c-d-e-f$，相当于消去了两条边，所以就结束了。那么第一个问题其实就是求，至少修改几条边的状态也就是保留几条边，然后才能使得当前状态变得能够达到最终状态。我们令$A=\oplus_{x\in E}x_i$，$x_i$表示每个边的状态$0/1$,那么一次操作就相当于异或$\binom{k}{2}$个$1$，也就是与$\binom{k}{2}$的奇偶性相关。令$A'$表示最终答案的值，那么如果$\binom{k}{2}\equiv 0$，那么$A$和$A'$的奇偶性就要求相同。那么我们把最终剩下来的边在$A$和$A'$中都异或掉，那么$A'=0$，$A$就相当于修改一些边的状态后的$A$，那么$A$就要保证是$0$，也就是说边数要是偶数。同理对于每个点$u$来说，我们定义$U=\oplus_{x\in to(u)}x_i,x_i$就是$u$出边的状态。如果一次操作中，操作到了$u$，那么相当于异或$k-1$个$1$，也就是$U$的变化与$k-1$的奇偶性有关。同理，我们能得到，当$k-1\equiv 0$时，$U=0$。所以，当$\binom{k}{2}$和${k-1}$的奇偶性不同时，我们需要修改的边的就不同，一下进行分讨：

\[\binom{k}{2}\equiv 0，\text{那么必须要修改边使得边数最终变成偶数,否则就不管边数} \]

具体的，我们只需要选择一条边修改状态就行了，然后把答案--。不管是原来是$0/1$都可以。因为最终都变成$0$，所以实际上，他的状态和它本来的状态就是不同的，也就是被保留下来了。

\[(k-1)\equiv 0,\text{那么必须修改点使得点度数都变成偶数，否则就不管点度数} \]

具体的，因为图的总度数一定是偶数，所以我们只需要找奇度的点两两配对就行了。
更精简的，我们可以按照$k%4$进行分类，在不同的数下面有不同的修改边的方式，特别说一下$k%4=1$的情况，这个把点改成偶数点后，边如果还是奇数，就不能随便改了，这时只能改一个奇数环，才能不影响点的奇偶性，所以我们尽量少的改就是三元环。然后如果有奇数点，那么可以和奇数点一起改三元环。
这样，我们就得到了理论上第一问的最大值，也就是满足上面的条件只是必要条件，而不是充分条件，我们要在构造过程中证明充分性。
现在我们先考虑当$\binom{k}{2}\equiv 1$时，怎么通过操作把边数改成偶数。那其实操作一次就行了，因为操作一次会改变边的奇偶性
$(k-1)\equiv 1$时，我们考虑怎么把奇度点改为偶度点，因为要保证其他点和与他无关边状态都不改变，所以我们需要异或两次，所以我们找一对点，那么就是$(u,x_1,\dots,x_{k-1}),(v,x_1,\dots,x_{k-1})$这样就行了。

现在继续考虑，当$n>k+2$时，我们考虑将$n-1$变成子问题，（至于为什么是$k+2$，下面解释）那么就是考虑把$n$的连边都删掉，根据刚才把奇数点改成偶数点，我们可以这样，选两个有连边的点$u,v$,$(n,u,x_1,\dots,x_{k-2}),(n,v,x_1,\dots,x_{k-2})$但是如果有奇数个连边的点呢？这种情况只会在$k-1\equiv 1$的情况出现，所以我们直接选择一个有连边的点，然后其他的随便找一些点，然后把这个边消了。会影响已经满足的性质吗？实际上是不会的，这个比较简单不说。这样就保证了在$n-1$次内删掉$n$了，这样我们就能够放心的做子问题了。
那么就到了$n=k+2$的情况了，现在我们就要操作把点度数都变成偶数，边数变成偶数，然后找欧拉回路通过四元环删边了。但是现在问题是操作数呢？我们注意到同一个操作进行两次是没必要的，然后当$n=k+2$是，又只会有$\binom{n}{2}$个操作，所以操作数就对了。那么这道题就没了；

总结：欧拉图的性质和欧拉回路的构造需要掌握；构造题找不变性来证明正确性或必要性或充分性，具体的是构造一个函数，然后观察这个函数在操作前后的变化来找到性质，例如这道题就是找所有的异或和。 $k-1$和$\binom{k}{2}$的奇偶性通过$k%4$分类。

P4768 [NOI2018] 归程

这个要说的只有，离散化的时候要判断好要排序的区间是啥，不要习惯性的写上了$n$，很sb。

CF888G Xor-MST

这个题的思路比较好，但是我没想到。就是回忆写最小生成树的过程，找出最短的边来，然后判断联不联通，加不加边。考虑现在呢？因为要异或，所以我们考虑建出来一个$01tire$，然后考虑，如果一个点$u$，其$ls_u,rs_u$中的点已经联通了，那么考虑如何把$ls_u$和$rs_u$这两个连通块连起来。两种方式：1. 选择两个$ls_u,rs_u$内部点联通。2. 选择一个外部点，分别联通$ls_u,rs_u$。第二种情况一定比第一种情况劣，因为相当于他们的$LCA$在更高的地方，异或出来的值就会更大。所以我们就说明了一个点其子树之中的点是通过自身内部进行联通的，那么就可以写了。具体的，对于一个点，如果有左右儿子的话，选择一个较小的子树，然后暴力取出里面的数，在另一个子树里找异或最小，然后就行了。复杂度应该是$O(n\log^2 n)$的

CF986F Oppa Funcan Style Remastered

这个前面都能转化，就是转换成$k$的质因子之和能不能表示出来$n$。然后首先质因子个数不超过$\log n$个，这个是显然的（但是我没注意到）。然后我们可以这样，在$mod k$意义下求同余最短路，但是这样点数太多了。那到底怎么做呢？用最小的质因子做模数就可以了。如果一个数有大于两个质因数的话，那么小的内阁就一定小于$\sqrt[3]{n}$，对于这道题就是$1e5$个，所有点数和边数就对了。那么就能做了。其他的情况特判就可以。

总结：这道题卡住我的地方1. 小的质因数要小于$\sqrt[3]{n}$,2. 同余最短路可以用较小的模数来缩减点数

P10779 BZOJ4316 小 C 的独立集

不要把小于等于写成小于。

然后就是说，这个就是建出圆方树来然后跑$dp$就行了。然后设$f_{u,0/1}$表示这个点的父亲节点选不选，这个是比较套路的设法，所以就不说了。不过这个复杂度是$O(n)$的，但是给$5e4$就很奇怪。

静态仙人掌，P4244 [SHOI2008] 仙人掌图 II

这两个和上面的内道题其实是一个题。都是建出来圆方树然后做一些东西。

P9869 [NOIP2023] 三值逻辑

这个有点困难。就是首先我们能找到直接支配的东西，例如，$1$必须和$2$不同什么的。这种情况我们给$1,2$连$1$的边，否则连$0$的边。所以我们相当于找到了一张图。我们要求什么呢？我们要求不能有一个环上每一条边异或起来是$1$。这个好判断，我们 $dfs$一下就行了。
总结：像这样，有不断地连着的限制关系的，那么我们可以通过找到最后的直接联系来建边找限制。

机器人

这个看着还挺吓人的，但其实不困难。我们发现，其实本质不同的状态数一共只有边数种，所以我们可以直接把一个点拆成若干个状态，然后再原图上跑最短路就行了。正确性分析和原来的是一样的。所以就行了。

AT_abc450_f [ABC450F] Strongly Connected 2

这个使用到了P10790 [NOI2024] 树形图里学到的性质，就是建出$dfs$树后，点$u$的子树里必定有一条返祖边指向$u$的祖先(不包括$u$)。那么对于这道题来说，就是说以$n$为根建，那么对于每个点$u$，必须有一条$X_i\le u,Y_i>u$的边，所以题目就转化成了区间覆盖问题。就是每个点都要有一个合法的区间覆盖他。我们设合法的点为，点$i$被一条$X\le i,Y>i$的区间覆盖了。那我们设$f_{i}$表示只使用包含于$1\sim i$中的区间，将$1\sim i-1$变成合法的点。然后$i$被至少一条$Y=i$的边覆盖的方案数。答案就是$f_n$。考虑转移。那么我们枚举以$i$的线段，$l\sim i$，然后将$f_{l\sim i-1}$加到$f_{i}$上。注意判断两个区间相等时的方案。但是发现这样假了，考虑少情况了，为什么呢？我们考虑，当我们选了一个区间$l\sim i-1$，然后将$x\in [l,i-1]$贡献给答案，那么只有$1\sim x$中的区间和$l\sim i$的区间选了，其他都没选，但是考虑$x+1\sim i-1$中的区间，因为如果不选$l\sim i$这个区间，那么就不能再$f_{x}$的基础上选这些区间，因为一定不合法，所以$f_{x+1\sim i-1}$中的方案就不会包含选这个的方案。但是我们选了$l\sim i$，所以我们就可以算这些方案，所以我们转移的时候需要把这部分答案贡献进去。

总结：考虑方案数的时候，要把所有可能合法的情况都贡献到，也就是，写转移之前先考虑一下这样转移是否可以不重不漏的转移完。注意选择一个东西使得原来不合法的状态变得合法的方案数。

P10790 [NOI2024] 树形图

额，因为要找到$1,2$类点。由于$1,2$类点的定义，我们能知道，他们一定只存在于缩点后入度为$0$的强连通分量里，并且如果有两个及以上入度为$0$的强连通分量，那么就都是$3$。这时特判一下就行了。然后我们考虑，如果第一个强连通分量里面没有$1$类点，那么所有还在强连通分量里面的点都是$2$类点吗？答案是可以的。我们考虑，没有$1$类点的限制其实就是相当于没有必须不能删掉的边，又因为$2$类点是由两条路径，那么我们把两条路径分岔开的路径部分删去最后一条边，这样每个点的可达性没有变，但是路径条数减少，所以一定能够变成$1$类点。
那么我们接下来考虑有至少一个$1$类点的情况。那么我们考虑，因为有一类点，所以入度为$0$的强连通分量里的点到其他强连通分量里的点方案数只有$1$。所以只需要再入度为$0$的强连通分量里考虑。那么我们就把其他所有点都删掉。我们以一个一类点为根，然后建出$dfs$树。这样，如果一个点$u$被两个及以上的返祖边覆盖了(设其为$X\to Y$，被覆盖说的是$X\in son(u), Y\in \text{祖先}(u)$)。那么就一定存在两条路径到达$fa_u$，所以他不是$1$类点。如果恰好有一条$X\to Y$。那么考虑若$Y$是$1$类点，那么$X$也是$1$类点，也为他子树里的点只能通过树边到达，因为是简单路径。然后其他的点只能通过$Y$到达，因为$Y$是$1$类点，所以$X$到其他点也只有一条路径，所以$X$就是$1$类点。反之，如果$Y$不是一类点，那么$X$也不是。那么一类点就处理完了。

二类点：依旧顺着这个思路。首先我们确定了$1$类点，那么覆盖这些一类点的返祖边是一定不能删除的。那么考虑判断一个不是$1$类点的点是否是$2$类点。首先如果有两条及以上不能删除的覆盖他的返祖边，那么他一定不是。其次，如果只有一条$X\to Y$，那么就删掉其他的，判断$Y$是否是$1/2$类点，因为首先如果$Y$是$1$，那么根据$1$类点的求法，我们知道删除了这些边以后$u$也是$1$类点。如果$Y$是$2$，那么我们可以先删一些边，把$Y$变成$1$类点，并且这些边里面一定没有$X\to Y$，因为不覆盖$Y$。所以这时也就和刚刚一样了。最后，如果一个不可删除的边也没有，那么我们就查看是否有一条覆盖$u$的返祖边指向的点是$1/2$类点。证法和刚刚一样。那么二类点也没有了。

最后，因为我们这个是以$1$类点为根的基础上。所以我们还要求出来一个一类点。求法。我们考虑在$1$类点为根的$dfs$树上，叶子节点的度数一定为$1$，我们从这里出发，如果有一个点入度为$1$，那么我们就把这个点和指向它的点合并，就是把他的出边给指向它的点。然后删去自环。我们考虑这个操作到底在做什么。找到一个入度为$1$的点，然后把他和指向它的点合并说明，如果想经过这个点，那么一定要先经过指向它的点。然后删去自环呢？实际上是在满足简单路径的限制，因为不能走重复的，所以从指向它的点走到他然后再走回来是不合法的，所以就删掉。最后，如果因为没有度数为$1$的点但点数大于$1$。那么一个点到另一个点，至少有两条路径，因为本身强连通，所以一个点能到达指向另一个点的两个入点。所以就没有一类点。如果最后只剩下一个点，那么这个点就是$1$类点了。

那么这道题就完了。思维量和代码难度都挺大的。我还没写出来。

posted @ 2026-02-12 15:13 lghjl 阅读(3) 评论(0) 收藏举报

刷新页面返回顶部

lghjl

题4