常州集训做题记录总集

5.24 信友队模拟赛

T1

T2

5.28 信友队模拟赛

T1

T3

6.1 信友队模拟赛

T1

网络流

CF2046D For the Emperor!

QOJ9224 Express Eviction

P3227 [HNOI2013] 切糕 !!!!!

ABC397G Maximize Distance

ARC142E Pairing Wizards

CF1427G One Billion Shades of Grey

[AGC031E] Snuke the Phantom Thief

连通性问题

[AGC071C] Orientable as Desired

QOJ10272 majority graph

l \rightarrow j & sum_l < sum_j \\ i \rightarrow l & sum_l \le sum_j \end{cases}$$ 所以整个 $[i,j]$ 就是联通的。我们可以找到 $\max\limits_{sum_j > sum_i} j$ 并直接把 $[i,j]$ 合并到一起。转换一下就是求 $j$ 使得 $\max\limits_{l > j} sum_l \le sum_i$。注意并没有要求 $j$ 是关键点。实际上我们会先通过双指针找到只考虑关键点时 $j$ 的位置，再计算出实际的位置。 然后需要考虑 $sum_j = sum_i$，考虑直接和 $\max\limits_{sum_j = sum_i} j$ 连边，最后所有 $sum$ 相等的位置都会联通。 ### CF1062F Upgrading Cities **拓扑序在后的点无法到达拓扑序在前的点**，也就是对于一个点 $p$，（拓扑序在其之前的点是否能到达它）与（拓扑序在其之后的点是否能到达它）是独立的。 故对于一个关键点 $p$，找出拓扑序小于等于它的点在原图上的导出子图，则这个子图只能有一个0出度的点 $p$；找出拓扑序大于等于它的点在原图上的导出子图，则这个子图只能有一个0入度的点 $p$。 如果是半关键点，那两个子图中允许存在最多一个0度的点。并且删掉这个点不能产生新的0度点，及不能有1度点和它相连。记录一下即可。 ### P9829 Traveling Merchant 先转化一下题意。有无尽路径必然有环，且这个环必须是一圈异色边加一条同色边。所以就是要判断能否从起点走到这样的环上。 具体来说对于一对同色点 $(x,y)$，**我们要找一条从起点开始，只走异色边的点不相交路径，依次经过这两个点。** 先说结论：存在这样的路径 $\Leftrightarrow$ 对应的 $x,y$ 的方点父亲是祖先关系 先必要性。我们先走到 $x$，那么从 $x$ 走到 $y$ 所在子树里一定有至少两条点不相交路径（点双性质），于是一定可以选一条和从起点走到 $x$ 不相交的路径走到 $y$ 所在子树里。 然后充分性，证逆否。不是祖先关系证明他们在其lca的两个子树里。假设我们先走到 $x$，那我们走进 $x$ 所在的子树里就无法再回到lca，否则从 $x$ 到 lca 的路径就可以被合并成一个点双。也就是我们没法走出来到达 $y$ 了。 建出圆方树判祖先即可。 ### CF475E Strongly Connected City 2 可以先缩边双。边双树边定叶向，返祖边定根向，对于任意点对 $(a,b)$ 一定存在 $a\rightarrow lev \rightarrow rt \rightarrow b$ 的路径。 然后考虑给缩出来的树上的边定向。首先结论是，对于任意的根 $rt$，删掉以后会产生若干连通块。一个连通块中的边的方向一定一致。证明就是调整法。考虑反向连通块中的一个子树，子树内部贡献不变，但是可以和连通块中其它点产生贡献。 但是各个连通块到 $rt$ 的边方向不一定。于是我们做一个背包（对。）就可以求出连通块两两贡献的最大值。 枚举 $rt$，bitset优化背包，复杂度为 $O(\frac{n^2} w)$ ### CF1338E JYPnation 竞赛图的一些性质。 首先竞赛图每两个点之间都有连边。思考时请牢记。 大概画一下图，可以玩出来答案只有1，2，3和inf。 考虑如何统计inf。有一个重要性质就是，竞赛图一定是长成一堆单点scc最终连向一个大的scc。考虑先找出一条哈密顿路径，然后考察每个点，将其出边中dfn最小点及其所有后继加入点集，就能构造出这个scc。那么inf的点对就是单点scc中任意两个以及末端scc中的点和所有单点scc。 1就是直接连边的点。 然后考虑2。对于 $u\leftarrow v$ 的点对，若某个点 $t_0$ 使得 $u\rightarrow t_1 \rightarrow v$，则 $t$ 的任意后继 $t_1$ 一定满足连边方式为 $u \rightarrow t_1 \rightarrow v$，否则就会连出题目中禁止的形状。也就是说，$t_0$ 一直到最后的强连通分量都要满足连边方式为 $u \rightarrow t \rightarrow v$。**也就是限制最宽松的取法是取末端scc中的点** ## 背包问题 ### CF1290F Making Shapes 首先考虑**确定了每个向量的使用次数，凸包就是唯一的**。按斜率顺序加入即可。 假设第 $i$ 个向量使用了 $a_i$ 个，那么能成一个多边形的条件就是： $$| \sum\limits_{x_i < 0} a_ix_i | = \sum\limits_{x_i \ge 0} a_ix_i$$ $$| \sum\limits_{y_i < 0} a_iy_i | = \sum\limits_{y_i \ge 0} a_iy_i$$ 然后坐标的极差。考虑所有的 $x_i > 0$ 和 $y_i > 0$ 一定在凸包中是连续的。所以极差就是 $\sum\limits_{x_i \ge 0} a_ix_i$ 和 $\sum\limits_{y_i \ge 0} a_iy_i$ 然后问题就变成了求 ${a_i}$ 方案数满足上面两个限制。 这里考虑使用类似倍增的做法。枚举每个 $a_i$ 的第 $d$ 位是否填1，并考虑 $\sum a_ix_i$ 的向上进位。前两个限制要求每一位的数值都相等。极差的限制要求 $\sum a_ix_i$ 最终小于 $m$，可以额外记录一个变量表示前 $d$ 位是否小于 $m$ 每次 $\sum a_ix_i$ 的进位是 $O(nV)$ 的，其中$V = \max |x_i|$。于是可以采用记忆化搜索。将四个数的进位和与 $m$ 的大小关系全都写进状态里。 ### CF1856E2 Permutree easy ver的做法：考虑将点 $p$ 的子树分成两个集合，代表其中取值 $> p$ 或 $< p$。最大化 $(\sum\limits_{v \in S} siz_v)(\sum\limits_{v \notin S} siz_v)$。其实就是要用 $siz_v$ 拼出一个离 $\frac 1 2 (siz_p - 1)$ 最近的数。单次 $O(n)$ 跑01背包即可。 hard ver的做法：将单次背包的复杂度优化到 $O(\frac {\sqrt n} w)$ 考虑根号分治。对于 $siz_v > \sqrt {siz_p}$，由于 $siz_p = 1 + \sum siz_v$ 所以这样的 $siz_v$ 不超过 $\sqrt {siz_p}$ 个。而对于 $siz_v \le \sqrt{siz_p}$ 我们直接当作多重背包二进制捆绑处理。 考虑一个物品 $v$ 对于 $f$ 数组的影响是使它或上它自己平移 $v$。考虑使用bitset处理。 ### P9140 [THUPC 2023 初赛] 背包 奇妙的同余最短路问题。 先贪心地全部取性价比最高的物品 $k$。那我们可以先选出 $m = \lfloor \frac V {v_k} \rfloor w_k$ 以 $v_k$ 为模数。 然后我们需要求出达到余数 $r$ 最少需要做出多少牺牲 $f_r$。具体的说，按如下方式建边： $$i \stackrel{w_x - \lfloor \frac{i + v_x}{v_k}\rfloor w_k}{\longrightarrow} i + v_x \bmod v_k$$ 解释：加入物品 $x$ 后会加上 $w_x$ 的贡献。然后为了使得体积不超过 $V$，需要替换掉 $\lfloor \frac{i + v_x}{v_k}\rfloor$ 个 $k$ 物品。 求最长路即可。 然而我们不能直接跑SPFA。 再观察一下这个建边方式。发现物品 $x$ 的边构成了 $\gcd (v_x,v_k)$ 个环。**我们只需要遍历两遍这个环，就可以把所有可能的最短路松弛出来**。这部分是 $O(nv_k)$ 的。 那么正确性也就有保障了。由于我们选的是性价比最高的点作为基准建的图，所以必定不存在正环（不然你走一圈用别的物品替换掉性价比最高的物品结果还更优了就比较流汗）。所以最长路是 $O(v^2)$ 级别的。又保证了 $v^2 < V$，所以我们一定能用小于 $V$ 的代价拼出一个余数 $r$。 ### Gym101064L 完全背包，但背包容量 $m \le 10^9$ 记 $W = \max w_x$ 由于物品的选取完全没有限制，我们一定可以把选取集合 $S$ 划分成两个可相交的集合 $A$ 和 $B$，满足 $|\sum\limits_{x \in A} w_x - \sum\limits_{x \in B} w_x| \le W$。 可以用这样的两个集合拼出 $S$ 的状态 $f(S)$： $$f(S) = \max \{ f(A) + f(B) \}$$ 具体的来说，假如我们预处理出了 $[\frac {S - W} 2, \frac {S + W} 2]$ 中的所有状态，就可以 $O(W)$ 地拼出 $f(S)$。 所以对于一个区间 $[l,r]$，我们只需要知道 $[\frac {l - W} 2, \frac {r + W} 2]$，就可以拼出整个区间。那么区间长度 $L$ 每次会下降成 $\frac L 2 + W$，递推求和一下大概是一个 $O(W)$ 的东西。 递归出口是 $l = 1$，此时暴力地用完全背包求出答案即可。然后需要注意的是我们最后的区间 $[l,r]$ 可能比 $W$ 要大，也就是我们需要多预处理一些答案。 ### NAIPC2016H Jewel Thief 01背包，但是背包体积 $m \le 10^5$。 考虑体积 $\le 300$，可以将同一体积的物品打包。 对于第 $i$ 种体积的物品，假如将所有模 $i$ 同余的位置拿出来赋予连续的编号，那我们有如下方程： $$f_{i,j} = \max f_{i - 1, k} + val(k,j)$$ 其中 $val(k,j)$ 表示第 $i$ 种体积的物品中价值最大的 $j - k$ 个的价值和。 发现 $val(k,j)$ 满足四边形不等式（交叉大于包含），故具有决策单调性。 我们可以通过分治实现 $O(m \log m)$ 进行单次转移。 具体来说，假设我们现在要求所有 $j \in [l, r]$ 的最佳决策。考虑先暴力遍历区间求出 $j = mid$ 时的最佳决策 $p$，那么 $j \in [l, mid)$ 的最佳决策不大于 $p$；$j \in (mid, r]$ 的最佳决策不小于 $p$。在分治时同时记录**当前可能成为最佳决策的位置的上下界** $[x,y]$，递归处理即可。 ## 计数专题 ### CF1864H Asterism Stream 先转化题意一步。依题意，$\{x_1...x_k\}$ 是一个随机过程，我们要求达到 $x_k \ge n$，步数的期望就是 $\sum\limits_x \sum\limits_i P(x_i = x)$。记 $f_x$ 为 $\sum\limits_i P(x_i = x)$，即 $x$ 出现的概率，则我们要求的就是 $\sum\limits_{x = 1}^{n - 1} f_x$ 考虑转移。我们有： $$\begin{cases} \frac 1 2 (f_{i - 1} + f_{i/2}) & 2 \mid i \\ \frac 1 2 f_{i - 1} & 2\nmid i \end{cases}$$ 考虑若 $i/2$ 是偶数，则可以把 $f_{i/2}$ 继续展开，得到 $$f_i = \frac 1 2 f_{i - 1} + \frac 1 4 f_{i/2 - 1} + \frac 1 4 f_{i/4} \\ =\frac 1 2 f_{i - 1} + \frac 1 4 f_{\lfloor \frac {i - 1} 2 \rfloor} + \frac 1 4 f_{i / 4}$$ 假设 $low(i) = k$，则 $$f_i = \sum\limits_{j = 0} ^ k \frac 1 {2^{j + 1}} f_{\lfloor \frac {i - 1} {2^j} \rfloor}$$ 也就是我们保存向量 $[f_{i}, f_{i/2}...f_{i/\log i}]$，就可以用矩阵优化转移。 记 $F_{k}$ 为 $low(i) = k$ 时的转移矩阵，$G_{k} = \prod\limits_{i = 1}^{2^k} F_{low(i)}$，$H_{k} = \prod\limits_{i = 1}^{2^{k + 1}- 1} F_{low(i)}$。 因为我们有性质：$x < 2^k$ 则 $low(x) = low(x + 2^k)$，所以有转移 $G_{k} = G_{k-1}F_{k}$，$H_{k} = H_{k-1}G_k$。（注意左右乘！）同样因此，我们的答案可以对于ans拆位计算。 ### P12445 [COTS 2025] 数好图 / Promet 先分点为四类 1. 在 $1\rightarrow n$ 上的 2. 能从1到达但是到不了 $n$ 3. 能到 $n$ 但是不能从 $1$ 到达 合法的连边方式有 $1\rightarrow 1,1 \rightarrow 2, 2 \rightarrow 2, 3\rightarrow 1，3\rightarrow 3$。发现在考虑二、三类点时**不用考虑一类点内部连接方式**，考虑分着计算。 设 $f_{i,j}$ 为考虑前 $i$ 个点中有 $j$ 个二类点，剩下都是一类点，且不考虑一类点内部连接方式时的方案数。根据上面的连边方式可以给出如下转移： $$f_{i,j} = f_{i-1,j} + (2^{i-1} - 1)f_{i-1,j-1}$$ 同样设 $g_{i,j}$ 为考虑前 $i$ 个点中有 $j$ 个三类点，剩余都是一类点，且不考虑一类点连边情况的方案数。转移： $$g_{i,j} = g_{i-1,j} + 2^{j-1}g_{i-1,j-1}$$ 然后考虑一类点的情况。其实就是 $k=n$ 的情况。考虑设计 $h_{i,j}$ 为在前 $i$ 个点中**钦定** $j$ 个出度为0的点的连边情况。那么有转移： $$h_{i,j} = (2^{i-j-1} - 1)h_{i-1,j} + (2^{i-j} - 1)h_{i-1,j-1}$$ 然后我们容斥一下，就得到了**总共有i个点时恰好只有n为零出度点的方案数**： $$res_{i}=\sum (-1)^j (2^{i-j-1} - 1)h_{i,j}$$ 最后的答案如下计算： $$ans_i = \sum res_x \times f_{x,y} \times g_{x,i-x-y}$$ ### P9563 [SDCPC 2023] Be Careful 2 容斥原理。 枚举包含在正方形内部的禁止点集 $S$，求包含矩形$\{(\min x, \min y), (\max x, \max y)\}$ 的正方形的面积之和。可以做到 $O(2^k)$。 考虑减少冗余。观察加入一些在矩形内部的点并不会影响贡献。猜测矩形内部不能出现点。 证明：记 $S$ 包含在对应矩形内部的点集为 $T$，确定矩形边界的点集为 $S_0$。则对于所有的这样的矩形，贡献为 $$\sum\limits_{T_0 \in T} (-1)^{|S_0| + |T_0|} \\ = (-1)^{|S_0|} \sum\limits_{i = 1}^{|T|} \binom{|T|}{i}(-1)^i \\[5px] = (-1)^{|S_0|}(-1+1)^{|T|} \\[7px] = (-1)^{|S_0|}[T = \varnothing]

Gym102411D Double Parlindrome

P10013 Tree Topological Order Counting