（Ⅴ）Our Notes! The Die is Cast

· · 个人记录

12.12 组合 DP

DP 专练。组合专练。vjudge.net/contest/774431

G。

排列计数，在相邻的数上要求有某种大小关系，感觉就非常可以插入 DP。按值域从小到大插入每个数，就知道现在的每个数和之前插入的任意数以及之后插入的任意数之间的大小关系，同一种数的去重也比较好讨论。然后对 W 从下往上扫描线切出来的 9 个形状暴力推转移。

H。

这个样例也太好了。不妨设 x < y，p_x < p_y，t 为 y 上一个 p_t > p_y，猜充要条件是 \forall x < i < y, p_i < p_y，\forall t < i < x, p_i < p_x。也就是说 x 前一个比它大的和 y 前一个比它大的是同一个数。

能做。 考虑 $\displaystyle \sum_{i = 1}^n \binom{i}{k}$ 是怎么算的。 考虑 $\displaystyle \sum_{i = 1}^n i \binom{i}{k} + \sum_{i = 1}^n \binom{i}{k + 1}$，发现它等于 $n \dbinom{n + 1}{k + 1}$。 所以 $\displaystyle \sum_{i = 1}^n i \binom{i}{k} = n \dbinom{n + 1}{k + 1} - \dbinom{n + 1}{k + 2}$。 或者你按照 $\displaystyle \sum_{i = 1}^n i \binom{i}{k} = \sum_{i = 1}^n \sum_{j = i}^n \binom{j}{k}$ 推，答案也是一样的。 或者 nodgd 说这个是 $$\sum_{i = 1}^n i \binom{i}{k} = \sum_{i = 1}^n \binom{i + 1}{i} \binom{i}{k} - \sum_{i = 1}^n \binom{i}{k} = \sum_{i = 1}^n \binom{i + 1}{k + 1} (k + 1) - \binom{n + 1}{k + 1} = \binom{n + 2}{k + 2}(k + 1) - \binom{n + 1}{k + 1}$$ 反正最后推出来的式子大概是 $$\sum_{t = 1}^{x - 1} \frac{1}{(y - t) (y - t + 1) (x - t)} = \sum_{t = 1}^{x - 1} \left( \frac{1}{y - t} - \frac{1}{y - t + 1} \right) \frac{1}{x - t} = \left( \sum_{t = 1}^{x - 1} \frac{1}{y - t} \cdot \frac{1}{x - t} \right) - \left( \sum_{t = 1}^{x - 1} \frac{1}{y - t + 1} \cdot \frac{1}{x - t} \right)$$ 这个求和两项都是变量，不好预处理，但是两项的差是个定量。 但是我们知道 $\frac{1}{ab} = (\frac{1}{a} - \frac{1}{b}) \cdot \frac{1}{b - a}$。 所以 $$ \sum_{t = 1}^{x - 1} \frac{1}{y - t} \cdot \frac{1}{x - t} = \sum_{t = 1}^{x - 1} \left(\frac{1}{x - t} - \frac{1}{y - t}\right) \frac{1}{y - x} = \frac{1}{y - x} \left( \sum_{t = 1}^{x - 1} \frac{1}{t} \right) - \frac{1}{y - x} \left( \sum_{t = y - x + 1}^{y - 1} \frac{1}{t} \right)$$ 就可以预处理了。 --- A。 求 $\sum\limits_a \min\limits_{i < j} a_i \oplus a_j$。因为 $\min$ 是契合 $\ge$ 的，考虑算 $\sum\limits_{lim} \sum\limits_{a} \left[ (\min\limits_{i < j} a_i \oplus a_j ) \ge lim \right]$，就是枚举 $lim$ 求多少个排列使得任意两个数异或都不小于 $lim$。 然后呢，你在字典树上考虑，如果某一层上的节点 $[l, l + 2^t)$ 满足 $2^{t - 1} < lim$，那么这个节点的子树中的数最多就只能在两个子节点中分别选一个。 然后就对每一个这样的极大节点的序列 DP，因为这个的数量大概是 $\dfrac{n}{lim}$，反正就是可以做的。 C。 注意到有解当且仅当一三行没有连续两个 x 且四个角不是 x。 把无解判掉后就可以在第二行上 DP，一三行的 x 因为不连续就互不影响。 F。 要求相当于在操作序列上要求 $a_{2k - 1} < a_{2k}$ 且 $i$ 的出现次数为 $b_i$，所以也可以从小往大考虑 $i$ 要填的 $b_i$ 次填到哪里，然后设状态 $f_{i, j}$ 表示填了前 $i$ 个数，操作序列中还有 $j$ 个两个都没填的。发现可以求出只填了左端点和两个都填了的，很好。 --- E。 $$ \begin{aligned} & \sum_\text{DAG k染色} \sum_\text{颜色} \left( \sum_\text{长度为 l 的链}1 \right) ^2 \\ = & \sum_\text{DAG k染色} \sum_\text{颜色} \sum_\text{长度为 l 的链对} 1 \\ = & \sum_\text{长度为 l 的链对} k^{n - 2l + \text{重叠点个数} + 1} \\ = & k^{n - 2l + 1} \sum_{i} k^i \sum_{\text{恰好重叠 }i\text{ 个点的链对}} 1 \\ = & k^{n - 2l + 1} \sum_{i} k^i \sum_{j \ge i} \binom{j}{i} (-1)^{j - i} \sum_{\text{钦定重叠 }j\text{ 个点的链对}} 1 \\ = & k^{n - 2l + 1} \sum_{j} \sum_{\text{钦定重叠 }j\text{ 个点的链对}} \sum_{i \le j} k^i \binom{j}{i} (-1)^{j - i} \\ = & k^{n - 2l + 1} \sum_{j} \sum_{\text{钦定重叠 }j\text{ 个点的链对}} (k - 1)^j \\ \end{aligned} $$ 设 $f_{u, t_1, t_2}$ 表示当前钦定点为 $u$，一条链长度为 $t_1$，另一条长度为 $t_2$，转移时枚举下一个钦定点 $v$，先枚举一条链增量算贡献，再算另一条链增量算贡献，因为两个贡献相当于分别卷积是独立的，最后乘上容斥系数 $k - 1$。 复杂度 $n^2 l^3 + n^3 l = 1.26 \times 10^9$ 不卡常一秒能过。 B。$\color{39C5BB}\textrm{初音未来}$。热量是过程量。不用管。 考虑热量的传递，要求每个热量在每个时刻只能下放一次，然后时刻 $i$ 时根节点热量小于 $s_i$ 的子树会被删掉。 如果不考虑时间限制，那么有用的限制只有最大的 $s_i$ 要求保留点的热量大于等于它，显然这样的点最多有 $\left\lfloor \dfrac{k}{\max s_i} \right\rfloor$ 个。 然后再考虑时间限制，如果 $s_i$ 为正数，那么深度大于 $i + 1$ 的点肯定会被删掉。显然只有首个正数的位置有用。然后就没了，因为时刻 $i$ 时深度小于等于 $i + 1$ 的点的热量肯定大于等于其最终热量。 判掉所有都是负数，我们就只关心第一个正数和最大的前缀和。因为数据范围很小，前缀和可以直接记到状态里。 前缀和的最大值，这个东西，如果从后往前 DP，就是 $f_i = \max(0, f_{i + 1} + a_i)$，只用记一个东西。然后枚举第一个正数再把前后拼起来算贡献。 这两道题数据范围都比较诡异，要敢于设状态，先写一个暴力再优化。 ## 12.16 状压 DP、DAG 计数 主旋律专练。状压专练。vjudge.net/contest/775208 --- P6846。 因为对称性，一定有成对出现的和为边数的方案。 对称性在数学（文化课）中可能比较常用，在计数题里，有用。 给定无向图，求有多少种定向方式可以得到一个 DAG。 考虑状压。 对于某个定向出的 DAG，一定对应唯一的方案每次删掉所有零入度点。把一个静态问题转为动态问题，就可以动态规划。 然后你就设 $f(S)$ 表示点集 $S$ 的定向方案数，枚举其零入度点集 $T$。 容易发现容斥系数为 $(-1)^{|T| + 1}$。 好像不是很容易。 对于一个零度点集 $T$，枚举到它的一个大小为 $j$ 的子集的次数为 $\binom{|T|}{j}$，而我们希望 $\sum_{i = 1}^{|T|} \binom{|T|}{j} g(j) = 1$。发现 $g(j) = (-1)^{j + 1}$ 是对的。 感觉不是很严谨。 <https://www.luogu.com.cn/article/ux19voa8>。 $\displaystyle F(S) = \sum_{S \subseteq T} G(T) \displaystyle G(S) = \sum_{S \subseteq T} F(T) \cdot (-1)^{|T| - |S|}

P11714。

主旋律。

mian 速通主旋律。

设↘→，F(S) 为点集 S 的导出子图的子边集构成 SCC 方案数，E(S, T) 为 S 指到 T 的边数，G(T, j) 为点集 T 的导出子图的子边集构成 j 个互不连边的 SCC 的方案数。

\displaystyle \underset{j \ge 2}{G(S, j)} = \sum_{\substack{T \subset S \\ \min S \in T}} F(T) \cdot G(S \setminus T, j - 1) \displaystyle F(S) = 2^{E(S, S)} - \sum_{\substack{T \subseteq S \\ T \neq \varnothing}} 2^{E(S \setminus T, S \setminus T)} \cdot 2^{E(T, S \setminus T)} \cdot \sum_{\substack{j \ge 1 \\ \lnot (S = T \land j = 1)}} G(T, j) \cdot (-1)^{j + 1} G(S, 1) = F(S)

对吗。

好像是对的，就做到了 \mathcal O(3^n n)。

然后显然可以把容斥系数乘进去，就做到了 \mathcal O(3^n)。

P11834。

要 来 力。

我们发现特殊性质 C 足足有 40pts 的部分分！！！令人心驰神往。

但是，我还是不会做。

P11665。

长度为 n 的序列，删掉若干不相邻的数，使得最长严格递减子序列最短。

其实这个最少非严格递增子序列覆盖是不用变的。这个题也太好了。 如果贪心求非严格递增子序列覆盖，就是说当前有一些子序列的结尾集合，然后把当前这个加到小于等于它的最大数上面。这个集合不会有重复数，状态是 $2^V$ 的。 然后就可以 DP，设 $F(i, S)$ 表示考虑前 $i$ 个数，集合 $S$ 是否可行。 这个状态显然不好。改成 $G(S) = \max\limits_{F(i, S) = 1} i$。 很有道理。因为我们只关心到达 $n$ 的最优状态，而一个状态如果在前后两个位置出现了，那么在后一个位置使用前一个位置后来加进去的数肯定不劣。 而不能在一个位置上保留最优的状态，因为比如 $\{3\}$ 比 $\{2, 1\}$ 更优，但加一个 ${1}$ 之后，$\{3, 1\}$ 比 $\{2, 1\}$ 更劣。 --- $2^{28} = 4^{14} \approx 2 \times 10^8$，$3^{18} \approx 3 \times 10^8$。 --- P11427。 答案的上界显然是 $2^n$，所以可以考虑直接判定每个集合是否可能合法。 放一个东西进去，就会把区间分为比较独立的两段，所以设状态大概是某个集合放在长度为某个数的区间是否可行。 显然这个有单调性，相当于设使得某个集合合法的区间长度右端点。虽然这个是实数，但是不难发现合法区间长度一定是左闭右开的。 具体地，如果要求 $S$ 集合要放，$\complement S$ 不放，当前这个数 $i$ 要放进去，就划分为两边，再枚举左右分别放 $T$ 和 $S \setminus \{i\} \setminus T$，但是两边不能放的依然是 $\complement S$，所以要放的和不放的都要设到状态里。状态 $\mathcal O(n 3^n)$，复杂度 $\mathcal O(4^n)$。 ## 12.18 三角函数 https://www.cnblogs.com/CDOI-24374/p/13942460.html 背三角恒等变换存在一些前人的智慧。 至于题目怎么做，你可以问一下 deepseek。 deepseek 说可以考虑统一角、函数名、次数。 $ \sin \alpha \pm \sin \beta $，$ \cos \alpha \pm \cos \beta $ 可以用和差化积，$a \sin \theta + b \cos \theta$ 可以用辅助角，$\tan \alpha + \tan \beta$ 可以用 tan 的和角公式。 ## 12.19 猫猫队互测 #5 T1 $\Large{😻🐱😺😸}

T2 \Large{😹😼😽🙀}

T3 \Large{😿😾🐼🐧}

小猫们都非常聪明，不过这样的问题对小猫来说还是太难了。

我错了，我不配当猫猫。

橘猫，花猫，黑猫，白猫，捉到老鼠就是豪猫。

T1 对每个点集的导出子图暴力并查集维护连通块信息可以做到 \mathcal O(2^n n \log n)，但是我们只关心一个子图中树形连通块的贡献，而每个子图中最多有 n 个极大树形连通块，所以可以直接暴力枚举每个树形连通块作为极大树形连通块出现的子图。

T3

P9338。

博弈的前提是每个人都是绝顶聪明的，但如果每个人都绝顶聪明就不会有人参加会使得自己输的博弈了。而任何一个博弈都有人输，所以就不存在博弈了。

这个 CF 有点神秘，主要是 C 题把猜结论的干掉了，然后 D 题，就是你直接贪心，从左到右能切就切，维护当前点的可行半径，是一个左开右开的实数区间。证明可以群里问一下面。

E 题感觉比较简单，就是一个区间会拆成 \mathcal O(\log) 个子树，然后同一个大小的子树最多有两个，所以就有若干限制要求 x 的高若干位只能为 0 或只能为 0 和某个数，用最紧的限制判一下就行了。但是官方题解一句话就讲完了，不是很看得懂。

Will be published later.

官方题解又更新了。

...

12.22 树形 DP

树形 DP。776517

E。根据部分分，考虑一条链的情况。没什么用。但是你考虑费用提前计算，就做完了。

芝士雪豹。雪豹闭嘴。

动态 DP 是什么。

设 f(u) 表示 u 子树中合并所有子节点的信息。

然后设 g(u) 表示仅合并 u 的轻儿子的信息。这样单点修改的时候就只有 \log 个 g 会被修改。

然后 f(son_u) \otimes g(u) = f(u)，就可以树剖维护 f ，单点查就从其所在重链的叶节点往上推到这个节点。

应该是要求任意节点对其父节点的贡献可以撤销。

然后你就会做 F 了。

D。答案要么是原图中的直径，要么修改后经过根节点。然后怎么做。是不是只会操作常数次。有用的只有接到根上的两个连通块的直径，发现只要选两条不相交的链，就一定能取到。

0x0d000721 = 218105633。遗憾的是，这不是一个质数，等于 193*1130081。

H。P9983。

考虑 Q = 1。

有一棵树和一个 k，还有一些关键点，有一些和关键点距离小于等于 k - 1 的不能选，但和每个点距离小于等于 k 的节点中必须选至少一个，求选的点最少。

有点眼熟。

先判无解。

考虑部分分的做法，我们知道一个经典的贪心，每次从最深的未覆盖点选其 k 级祖先。这个做法可以扩展吗，如果不可以扩展有其它做法吗。

我们看一下题解，发现把这个策略改为每次选与最深点距离小于等于 k 的能选的最浅点就是对的。但是好像没有题解给出比较有道理的证明。

考虑原来那个为什么是对的呢，就是说你选 k 级祖先肯定能把这个子树覆盖完，而其它可以选的一定在这个子树内，如果选了在子树内或在子树外覆盖的点都不会更优。

现在这个，对于当前 dep 最大的点 u，选了其 k 级邻域中的点 v。

因为 u 是最深点，所以对于任意一条 u 向上走到 p 再从 p 向下走到 v 的路径，且路径总长不超过 k，v 的 k 级邻域都能覆盖 p 的整个子树，也就是要求 dep_u + dep_v - 2 dep_p \le k。

化简得到点 v 能覆盖的就是 u 的 \left \lfloor \dfrac{dep_u - dep_v + k}{2} \right \rfloor 级祖先的 \left \lceil \dfrac{dep_u - dep_v + k}{2} \right \rceil 级邻域（它的邻域会完整包含它的子树，因为 u 已经是最深的点）。

这样我们就有多项式做法了。 一个瓶颈在于覆盖一个点的 k 级邻域，查询一个点有没有被覆盖。 考虑覆盖时就给这个点的 k 级祖先打一个标记，然后查的时候再查一下 k 级祖先，树剖维护。 其实观察发现，每次选的 $u$ 到其 $\left \lfloor \dfrac{dep_u - dep_v + k}{2} \right \rfloor$ 级祖先的路径是不交的，而 $\left \lfloor \dfrac{dep_u - dep_v + k}{2} \right \rfloor \ge \left \lfloor \dfrac{k}{2} \right \rfloor$，所以最多选 $\dfrac{n - 1}{\left \lfloor \frac{k}{2} \right \rfloor} = \mathcal O(\frac{n}{k})$ 次。 所以可以暴力做。k 级邻域覆盖单点查，每个点维护向下最多覆盖的距离。 和 DP 有什么关系。 P9527。k 级邻域修改单点查。修改。注意到如果 $dis(u, v) \le k$，那么就存在恰好一个 $u$ 和 $v$ 的公共祖先 $p$ 使得 $dis(u, p) + dis(p, v) \in \{ k - 1, k \}$（不妨在根节点往上接 k 级虚点作为祖先）。把 $\le$ 转为 $=$，单次修改和查询都是 $\mathcal O(k)$ 的。 刻画两点树上距离不超过 k 时不一定要考虑恰好经过 LCA 的简单路径。 P3942。 P3523。<http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2868&tid=S>。之前一直不是很懂这道题，现在看的话，如果在不给出贪心结论的情况下，直接用 DP，正确性确实是没有道理的。这个东西的本质还是维护那个贪心而不是树形 DP。。。。 --- nodgd 讲 K-D Tree。 因为有 $\log n + \mathcal O(1)$ 层，期望有一半的层会直接递归到一个儿子，就是 $2^{\frac{\log n + \mathcal O(1)}{2}} = \mathcal O(\sqrt{n})$ 的。但如果动态替罪羊，层数 $\mathcal O(\log n)$，就是错的。 --- P14637 [NOIP2025] 树的价值。 赛时在没有得到多项式做法的情况下写了一个无法通过大样例的假做法获得 24 分。 题解可以看 <https://www.luogu.com/article/4l9eruyp>。写得很好。 思路主要是发现 mex 的贡献可以用一个树剖分的形态刻画。 题出得好，就是有点难。 --- nodgd 总结： 1. 优化高维状态。 2. 优化低维状态。 3. 数据结构。 2.24~3.3 郑州外国语学校 代码源省选集训 ## 12.27 集训队互测 #6 前言· 猫的黎明 在时间尚未被计数、世界尚未分裂的年代， 一切都沉睡于名为 **「猫猫」** 的原始洪流之中。 传说，那是一种不依赖物质而存在的能量。 它能孕育秩序，也能制造混沌； 能赐予智慧，也能带来毁灭。 当人类首次窥见这股力量，他们称之为——**哈基米（Hachimi）**。 自此，王国的历史被分为三个纪元： **橘猫的森林、花猫的游戏、与猫猫的合照。** 这三次巨变，被记录在古老的《猫猫史诗》中， 成为王国永恒的信条。 > ——以下三章，正取自《史诗》之卷。 > > 题目不保证按难度排序，请勇敢地踏入猫猫洪流。 --- 尾声 · 猫之轮回 战火熄灭，猫猫归寂。 王国不复存在，只余一片无垠的猫猫。 然而，在这片寂静之中， 依然可以听见三条古老法则的低语—— 橘猫孕育花猫， 花猫引发白猫， 白猫终将归于新的黑猫。 当下一个文明诞生之时， 他们将再次在猫猫中醒来， 再次橘猫森林， 再次花猫游戏， 再次猫猫合照。 —— 因为 **猫**，从未停止 --- T1 🐱 T2 🐱 T3 🐱 --- T1 发现每对数值相邻的点可以作为这个的支配对，就可以做到 $\mathcal O(q n^2 \log n)$ 了。🤡 T2 发现所有数都是 2 的幂次时划到一起最优。🤡 T3 发现 $l_a = r_a = l_b = r_b$ 时是公平博弈，可以用 SG 函数解决。🤡 ## 12.30 无作业日所以没有作业题，大家读一读：别人的DP小作文 https://www.luogu.com.cn/article/ki71nw88 --- https://vjudge.net/problem/BZOJ-5111 树上权值第 k 小的连通块。 点分治后然后要求连通块必须包含根。这样连通块就相当于删掉若干（不交）子树。 在 DFS 序上刻画，可以跳过子树就连边，然后有连通块和路径就是双射的。求 DAG k 短路。 但是我们不会做 DAG k 短路，所以这个问题对我们就没什么意义。 --- 给定大小为 $n$ 的两棵树 $T_1$、$T_2$，求 $\max\limits_{1 \le i, j \le n} dis_{T_1}(i, j) + dis_{T_2}(i, j)$，边权有负数。 问了一下 deepseek 树上的一条路径是 in the tree 还是 on the tree，它说是 in。 这个问题，我们可以对 $T_1$（三度化后）边分治，每次就给出了 $T_2$ 上的两个点集，点有点权，求加端点点权的最远距离，建出虚树 DP 即可。 如果用点分治，每次点集不止两个，复杂度就不对。但是你可以每次选最小的两个点集，算这个点集内和点集外产生的贡献，然后将其合并，这样每个集合只会被算 log 次。 > 凭什么点分治要平白无故地比边分治多一个 log？ > > 你可以拿起笔，在草稿纸上涂涂画画，写下一堆形如“logn - logs ”的东西，然后拍案而起：“这样做复杂度是nlogn的！” > > 你也可以平心静气，突然发现，点分的时候每次选最小的两个集合合并，其本质就是边分治。 --- 树上一个点集的点数减去其导出子图边数等于其构成的连通块数量。 ## 12.30 元旦晚会 https://www.cnblogs.com/mian28/p/19247560 https://www.bilibili.com/video/BV1EgmYBrEDR https://www.bilibili.com/video/BV14H4y167QM https://www.bilibili.com/video/BV1Yj41187gS https://www.bilibili.com/video/BV1ur421n77B https://www.luogu.com/article/pakg26s6 https://www.bilibili.com/video/BV1UC411B7Co https://www.cnblogs.com/mian28/p/19400962 --- 这里本来有一个很好笑而且内涵深刻的相声剧本，但由于篇幅原因就不展示了。你可以通过问 deepseek“以老资历二次元、小资历二次元、现充的差异为背景，创作一部相声剧本”查看。 ## 1.2 欢乐赛。 --- 没有欢乐赛，更欢乐了。 --- 魔裁打完了。 ## 1.4 二分图 匈牙利算法求二分图最大匹配，每次从一个未匹配的左部点出发找一条增广路并反转，原来匹配的左部点现在还是匹配的，并新匹配了一个左部点。贪心地做就可以把能被匹配的尽量匹配上。 ![](https://cdn.luogu.com.cn/upload/image_hosting/wg6i3fx5.png) 如图，2010331myq 的 NKOJ 背景。 --- 卡常。bfs 匈牙利。bitset 优化匈牙利。shuffle 优化匈牙利。Dinic 优化匈牙利。 --- 字典序最小的最大匹配。 P1963。 二选一，考虑建图，得到一个基环树。 https://www.luogu.com.cn/article/3zsrgpd3 --- 最大匹配等于最小点覆盖。可以用最大流最小割定理证。 最大独立集是最小点覆盖的补集。 最小边覆盖。感觉一下，就是你选一个不重复覆盖的最大匹配，然后把没覆盖的点的选上，$p + n - 2p = n - p$。 --- P6220。网格图可以考虑给行建点，给列建点，得到一个二分图。 最小点覆盖输出方案。 因为我们知道怎么做最小割输出方案，所以就做完了。 --- DAG 最少不交路径覆盖。把每个点拆成入点和出点，原图中的边由对应出点连到对应入点。因为路径不交，所以入度和出度都最多为 1。 最开始每个点自己是一条路径，选一条边就是把一个点结尾的路径和一个点开头的路径连起来，就少了一条路径。 DAG 最少可交路径覆盖。在传递闭包上求最少不交路径覆盖。 最大链等于最少反链覆盖，最大反链等于最少链覆盖。 链是互相有偏序关系的点集，反链是互相没有偏序关系的点集。 P4298。 构造方案就删掉这个点再求一遍判可不可行。复杂度 $\mathcal O(n ^ 4)$，不用管，反正这个本来就不是最优解。 --- dilworth 怎么证。 你可以去问 lwc。 --- 最大反链还可以用最大权闭合子图做。把每个点拆成 $u_1$、$u_2$，点权分别为 $-1$、$+1$，连边 $u_1 \to u_2$。然后对于原图（原图。）中的边 $(u, v)$，连边 $u_2 \to v_1

这个做法同样可以构造方案，而且因为不用传递闭包理论复杂度更优。

二分图博弈。

无向图上有一个棋子，每次将棋子移到相邻点并将其原来所在点及其邻边删掉（或者说每个点只能经过一次），不能移动判负。

如果当前点是当前图的任意最大匹配的匹配点，那么将其沿任意最大匹配的匹配边移动，把原来所在点删掉，这个最大匹配删掉一条边是新图的最大匹配且到达点不是匹配点。

如果当前点不是当前图的任意最大匹配的匹配点，那么当前点不是匹配点的任意最大匹配中，其相邻点都是新图的任意最大匹配的匹配点。

P1971。

网格图是二分图。反正你观察一下这个不会经过重复点。

因为不会经过重复点，所以到达一个点时这个点的颜色一定是确定的。

所以题意就是网格图上有黑白点，当前这个人要走到与当前所在颜色不同的相邻点，且不能经过重复点，判断是否先手必胜，然后删掉这个点。

A。

考虑结果的形态，发现产生贡献的可以看成最后没有被覆盖显示出来的端点。

端点没有显示出来就是被别的区间覆盖掉了。

如果被一个包含它的区间覆盖。发现改上去不劣，一定有最优方案中没有这种情况。

如果被相交不包含的区间覆盖。改上去就会有另一个区间显示不出来。所以两个端点无法同时显示

如果已经有了一种选点的方案，当且仅当钦定一个选一个不选时，会限制两个区间的顺序，发现不会有环。

所以要求就只有有的点对不能同时选，而且一定是一个左端点和一个右端点，就是一个二分图求最大独立集。

卡常。但是有人说直接写 isap 就能过。

卡空间。所以要用 bitset 存边。

我错了，把边 shuffle 一遍要增广 5000 多轮，把边 sort 一遍增广 5 轮就出了。

F。

如果有一个环，反转环上每条边的匹配状态，每个点的度数奇偶性不变。然后怎么做啊。

这个题和二分图有什么关系？？？

一般图完美匹配，当且仅当，Tutte 矩阵行列式不为 0。

最大权完美匹配。

J。

把一个矩形的四个角位置上的数值异或 1，每一行和每一列的奇偶性不变。把这个建出来二分图，就是说一个环可以直接删掉不影响奇偶性。然后怎么做啊。

这个题和二分图好像也没什么关系。。。

给定一个连通图，每个点有 01 点权，要给边赋 01 边权，使得每个点点权都等于邻边边权异或和。

每条边给两个点点权异或 1，所有点的异或和不变。所以异或和不为 0 一定无解。

异或和为 0 一定有解。建出一个生成树，然后从叶子往上递推边权，所有的边权都是确定的。然后非根节点都为 0，根节点也一定为 0。方案数就是可以先任选非树边权值再递推树边。

所以每个连通块的答案就是 0 或 2^{m - n + 1}。

现在相当于是每个左部点要连到右部的若干个区间里的点，维护连通性。线段树优化建图。太垃圾了。维护连通性，所以其实是把右部的一个区间缩成一个点，然后左部的这个点连上去。

CF901D。

无向图，每个点有正负点权，给每条边赋边权，使得点权等于相邻边权和。

考虑一棵树，画一下，发现有解当且仅当 \sum C_u \cdot (-1)^{depth_u} = 0，也就是奇数层和偶数层点权和相等。

所以对于非树边，如果两点层数奇偶性不同，就没有用，否则，就可以改掉。

那么这个点权与度数奇偶性相等的性质，意义是什么呢，就是啊，sodayo，sodesune，soyorin，sosoyorinrin。

总之就是，这种题，可以先在生成树上考虑，因为生成树可以剥叶子。

I。

首先的问题就是给一个二分图，求至少删掉几个点可以使得最大匹配不超过 k。

我们知道删掉一个点最大匹配最多减一。我们还知道一定存在至少一个点在任意最大匹配中被匹配，将其删掉最大匹配一定减一。我们是怎么知道的。jr 说的。但是他说他不会证。

通过询问 deepseek 得到证明。

你考虑任意最小点覆盖，其大小为 k，如果其中的某个点，在某一个最大匹配中没有被匹配，就说明，剩下的 k - 1 个点就已经能够覆盖这个最大匹配中的 k 条边，这是不可能的，就矛盾了。

https://oi-wiki.org/graph/graph-matching/bigraph-match/#最大匹配关键点

所以我们就每次找一个最大匹配关键点，将其删掉，使得最大匹配数量恰好减少一。 或者你换一种理解方式，要删掉一个点后最大匹配变小，就相当于删掉这个点后最大独立集不变，所以每次把不在最大独立集，也就是在最小点覆盖，中的点删掉就可以了。 然后就做完了。吗。 现在的问题是，给定非负权值数组 $x$、$y$，你需要构造非负数组 $a$，使得 $\sum \max(0, x_i - a_i \cdot y_i)$ 最大。且有一些限制要求 $\sum_{j = 1}^{i} a_j \ge b_i$。能做吗。观察到如果有一个取完了那就一定是它出现后就一直取把它的 $x$ 取完，它出现前就取最小的 $y$，枚举把哪一个被取完了，就可以算了。 --- H。 考虑把每条边向左走和向右走建成两个点，然后就有 $5000$ 个点。用 bitset 优化匈牙利可以过。 我在乱说。 因为 B 在没有边权限制时必胜，不妨猜测他真的必胜。 稳定婚姻问题。惊奇地发现是等价的，就做完了。 --- 既然这道题名字包含 Zigzag，我们就想起来一个东西叫 zig-zag 构造（zig-zag pattern）。 在无向完全图上构造尽量少的简单路径使得每条边恰好经过一次。 P9837。 相当于有一个 $n$ 个点的完全图。需要构造 $n$ 个起点不同的简单路径，第 $i$ 个路径长度为 $i - 1$，每条边恰好经过一次。 设 $n$ 为偶数，考虑构造 $\frac{n}{2}$ 个长度为 $n - 1$ 的简单路径。然后把每个路径拆成两个。 ![](https://cdn.luogu.com.cn/upload/image_hosting/23ww94bn.png) 这也太帅了。 zig-zag 的每条路径上的边两端点距离依次为 $1$ 到 $\frac{n}{2}$ 再到 $1$，也就是对于端点距离为某个数的边会均匀分配到每个路径。 如果 $n$ 为奇数，加一个虚点，再删掉。 CF1290D。 要求不同元素数量，考虑直接对于每个数判定它前面有没有和它相同的数。 把 $n$ 个元素划分为 $\frac{2n}{k}$ 个长度 $\frac{k}{2}$ 的块，每次把两个块加到队列里，再清空，询问次数 $\frac{2n}{k} \cdot \frac{2n}{k} \cdot \frac{1}{2} \cdot k = 2 \cdot \frac{n^2}{k}$。 数量级是对的，但是还要卡常。 感觉到每次直接清空是不优的，考虑每次判完两块后不进行清空，直接加入下一个块。直接枚举块的间隔并枚举初始块，精细分析得到询问次数 $\frac{3}{2} \cdot \frac{n^2}{k}$。 发现这个就相当于完全图不交路径覆盖，使用 zig-zag pattern 做到 $\frac{n^2}{k}$。 > 解空间太大且整体研究太困难，从问题中取出特殊的一类模式只考虑该模式上的解 --- AT_agc037_d。 有一个二分图，左右各 $n$ 个点且每个点的度数都为 $m$，一共 $nm$ 条边。找出 $m$ 个不交的完美匹配。 题目指出一定有解。 所以不妨猜想直接找 $m$ 次完美匹配并删边就是对的。然后就过了。 这是 Hall 定理的推论，所有顶点的度数都相同的二分图一定有完美匹配。 --- running -> Loading presents for flight x... AC -> Happy New Year! WA -> Delivered to wrong address on flight x TLE -> Stuck in sleigh traffic on flight x MLE -> Delivery list too long for flight x RE -> Sleigh broke on flight x 这也太有意思了。 ## 1.8 夏老网吧 严格按照，nodgd 做梦梦到的单子，进行记录。 > 世界，讨厌我 > > 我，则无法停止憎恶、仇恨我自己 > > 渴望着能将自身改变 > > 如同一个受虐狂 > > 从不想活成自己想活成的样子 > > 我，想与我，决裂 > > 我，不喜欢现在这个我 > > 可她与已我融作一体 > 两只刺猬 > > 在寒冬里取暖 > > 需要隔得不近也不远 > > 而一只冻成了冰的刺猬 > > 又该如何…… ## 1.10 T1，如果是询问所有子区间最值的和，就是历史和线段树板子，乘了区间长度，好像还是历史和线段树板子。但是我们不想写历史和线段树，所以就可以使用二次离线莫队做到单根号，然后被卡常。 T2 是什么。 T3 可以打表。 --- 题出得也太好了，我要去给三国杀刷好评。 --- ，，， 写莫队没过的都是小丑。 --- 直接写的话，莫队会把 $n$ 个询问变成 $2n\sqrt{q}$ 个询问，把这些询问的答案存下来就已经爆空间了。 那么，二次离线怎么做到线性空间呢。 每次移动右端点，都是一段区间，所以存到一起就可以了，，，我是小丑。。。 --- 考虑每次询问时直接把这个区间放到线段树上，分治。其实是把所有区间离线下来分治，反正是双 log 的。 --- 把这个图建出来，惊奇地发现操作就是交换两个点的编号，所以是无标号内向基环树计数。 ## 1.12 网络流 笑点解析： （Ⅱ）12.10，12.18，12.25，12.26，1.8 （Ⅳ）7.22，10.17 https://oj.hjjoi.com/TeacherCourse/1753095151063364212 https://vjudge.net/contest/757202 https://vjudge.net/contest/780784 --- 最大流等于最小割怎么证。 网络流怎么写。 --- 很多最大流或费用流算法都要先对残量网络进行分层，然后规定当前增广只能由这一层流到下一层。 --- 由于不明原因，有些题目写 ISAP 过不去但是 Dinic 随便过，所以你应当放弃 ISAP，使用 Dinic 这个更权威的算法。 --- 费用流是有当前弧优化的，但是之前一直没写。都怪 helang。 --- P3980。 --- 21 年集训队论文《再探线性规划对偶在信息学竞赛中的应用》。 $x$，$y$，$b$，$c$ 是列向量。 - 求 $\max \{ c^T x : Ax \le b,\ x \ge 0\}

这两个问题是等价的，\max c^T x = \min y^T b

论文中对这个的证明：

强对偶定理的证明较为困难，可参考Gärtner,Bernd;Matoušek,Jiří(2006). Understanding and Using Linear Programming. 在此略去。

但是我们声称这个结论能用马克思主义哲学解释（具体的你可以问 deepseek），就可以将 P3337 改成 P3358。

P3337：

设 b_{1, i} = C_i，y_{1, i} 表示第 i 号位置上建塔的数量，c_{1, i} = D_i，A_{i, j} = [L_i \le j \le R_i]。

问题就是求 \min y^T b，其中 A y \ge c \land y \ge 0。

对偶一下，就是求 \max c^T x，其中 A^T x \le b \land x \ge 0。

意义就是给每个区间赋次数，使得区间权值乘次数之和最大，且每个位置覆盖它的区间数量不超过它的权值。

这个问题呢，就可以用无源汇费用流解决。

先正着建一条链，然后对于每个区间反着连回去，区间次数多一就是多走了一遍这个负环。你可能觉得走的不一定是这个环，但是不重要，反正数量是对的。

如果有负环或者下界，就可以做无源汇费用流，每次增广一个环而不是一条路径。

P3980 同理。

但是如果你真的想用线性规划对偶解决一些问题，可能需要把 https://oi-wiki.org/math/linear-programming/#对偶问题 中的这个表背下来。但是我既背不下来，背下来了也用不出来，不如背元素周期表。

AT_wtf22_day1_d

最小割树。保序回归。线性规划对偶费用流。

不会啊，nodgd 救一下。

nodgd。

https://www.luogu.com.cn/article/wa23azdu

Dinic v.s. ISAP 谁能赢。

ISAP 必须加 GAP，Dinic 必须加当前弧。

HLPP。感性理解一下。MPM。都没有实用价值。

跑出 \mathcal O(1) 的流量，EK 线性，Dinic 线性，ISAP 炸飞了，因为 dis 的修改是 n^2 的。这也太垃圾了。

Dinic WIN。

费用流，伪多项式的。大家都不会，将就用吧。

原始对偶费用流，在 (hyw+hyy)/2=hyx 的论文中有详细记载。

zkw。有点扯淡。do do t++; while (dfs()); while (upd());。大多数时候比 SPFA 快，有的时候不快。

上下界。可以是负的。

对于一个预分配之后有剩余流量的点，它的普通边还要额外流出去这么多，就从超级源连过来。

最小费用可行流，跑一个满流，就合法了。有源汇，源和汇可以不守恒。最小费用最大流，跑出可行流后，删掉 S->T 和 T->S，再从原来的源汇跑一个最小费用最大流。有源汇最小费用最小流，反着跑。

费用流先随便流再跑最小费用不对的原因是，可能会跑出来从源点出发增广不到的负权回路。但是跑完可行流不会出现负权回路，再接着跑最大流还是对的，需要反悔的也能反悔掉。

笑点解析：https://luogu.store/d/1114542。

为什么没有无源汇最大流？

为什么没有无源汇最大流？

首先，我们发现我们还没有定义无源汇网络的最大流/最小流是什么，然后再想一想，发现它们没有什么意义。所以我们就做完了。——Just_int_mian

负权边，改了，负权回路，消掉了。

考虑一条费用为负的边，先将其强制流满，就变成了反悔这条边需要费用。

实际上，把负权边干掉之后，最后会用到的，一般也就是无源汇上下界最小费用可行流。

https://www.luogu.com.cn/record/258644620，https://www.luogu.com.cn/paste/zbgcvxo6

上下界不算科技，只是一种建图方法，如果已经要用费用流了不妨直接用上下界。

最小割重构树。

合理的说法。全局最小割。每次找最小割，两边分治。全局最小割分治。全局最小割。理想最小割树。是等价的，因为总有一次是全局最小割。

全局最小割。

最小割建图。https://www.luogu.com/article/51f2i30j。

最大权闭合子图。

切糕。非常地切糕。四边形不等式，AT_abc347_g。

志愿者招募。很典。而且我不会。

天数建一条链，如果人在链上算贡献，就炸了，人在支路上算贡献，每个人只算一次。支路等于干活，主路等于睡觉。睡觉的人数小于等于总人数（设为 inf）减 a_i。

本质是上下界。

保序回归。记住结论。例题 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3426&tid=l。有一堆变量，变化 1 有代价 1，使得满足一些大小关系。保证偏序回归代价最小。保序规划。

https://www.luogu.com.cn/article/ul0uw9qz

如果有一些改到一起，中位数。L1 保序回归，一定在取到原来的某个值最优。

假设只能取 m 和 m+1。最小割算一下，然后左右两个是被挤过来的，两边分治，本质是一个整体二分。复杂度最大流乘一个 log。

x_i 加一的代价是 a_i，减一的代价是 b_i，这个做法对吗，感觉没问题。

L2 保序回归。求偏导。用导数做保序回归。L2 怎么做啊 L2，不是 L2 怎么做的啊，我记得论文里面有一个结论但是我忘了。缩成一坨的情况下，最优的等于平均值，所以分母不超过 n。感觉在随机说话。那别玩了我不会。我说了我不会。

然后是线性规划对偶，唉，对偶就是对偶，模拟费用流就是模拟费用流，今天就讲到这里吧。

凸性可以参考 gjy 论文。

好了好了睡觉睡觉。

Dijkstra 费用流，即原始对偶费用流。

怎么做。

Johnson 的精神是给每个点赋势能 h，然后把每条边 u \xrightarrow{w} v 的边权改为 w + h_u - h_v \ge 0。容易发现 h 取 dis 即可。

跑费用流的时候如果增广了 u \xrightarrow{w} v，就可能会多一条边 v \xrightarrow{-w} u，需要重新赋势能 w + h_u - h_v \ge 0 \land -w + h_v - h_u \ge 0，即使得 h_v - h_u = w。

因为增广一定沿最短路增广，所以增广前的 dis 就恰好满足 dis_v - dis_u = w，所以把 h 赋为 dis 即可。

如果初始图有负权，先跑 SPFA，复杂度 \mathcal O(n \cdot m + f \cdot m \cdot \log m)。但如果你认为费用流有负权边都应该先干掉，那么第一次也可以跑 Dijkstra，复杂度 \mathcal O(f \cdot m \cdot \log m)。或者 \mathcal O(f \cdot n^2)

还是跑不过去，太垃圾了。

zkw 费用流。

怎么做。

nodgd。

拉格朗日乘数。求导。做不动。

不要用数学方法思考。

新 x 流 (c_i + x)^2 w_i - c_i^2 w_i = 2c_iw_i \cdot x，流最短路。

退 x 流 ，退最长路。

每个 S \to T 的路径长度相等，不然就可以调整。

所以 S \to u 的路径长度相等。

每 u：d_u = s \to u。

s \to u \to v \to t，d_v - d_u = 2c_i w_i

所有入要等于所有出。\sum_{v \to u} \frac{d_v - d_u}{2w_i} = \sum_{v \to v} \frac{d_u - d_v}{2w}，线性方程，d_s = 0，d_t = 1，扩大若干倍到 F，高斯消元。

什么什么就线性相关，干掉就好了。

电流，功率最小。d 是电视。电势。基尔霍夫矩阵。

它不是费用流，但是很有意思。？？？

🤡恩偶滴基地。

♿我喜欢你，你喜欢我。♿

尽量建单位容量的图，用 Dinic 就有根号复杂度的保证。

nodgd。线性规划对偶。把这个背下来。

费用流的变量是边的流量，约束条件是每个点的收支平衡。

组合意味。？？？

每个变量出现在两个限制，系数一正一负。

注意到，每个变量出现的是区间，（上下各添一行 0）差分一下就是一个 +1 一个 -1 了。不等式不能差分，但是等式可以。

A^T y \le c A^T y + l = c$，$l \ge 0

行 i 减行 i-1

\sum \pm y_i + l_i - l_{i - 1} = c_i - c_{i - 1}

每个变量一条边，正的是入边，负的是出边，每个等式一个点。

1 2 3 ... n n+1

l 边 i \to i-1 (inf, 0)

y 行 l_i - 行 l_i - 1 正，行 r_i + 1 - 行 r_i 负

r_i + 1 \to l_i (inf, d_i)

ci - c{i - 1} 正的流向 T，负的由 S 流过来

全都等价，就可以跑最大费用最大流。就行了。

组合意义，志愿者招募。

单纯刑法。单纯形法。

前天讲保序回归，例题，如果只有一棵最小生成树。

T 里面的边只会减小，外面的只会增大。

对偶一下，然后尝试转费用流。两个 +1，怎么办呢。

等下这题要转置吗，对啊就是要转置啊。

树边的方程和非树边的方程，树边加一个负号，就是一个 +1 一个 -1。

帽帽猫猫帽，猫猫帽帽猫。🎩🎩🐱🐱🎩，🐱🐱🎩🎩🐱。猫猫倒过来读也是猫猫哈哈哈哈。

用两个例子证明了其实既不会证明公式也不会做题。对偶完了发现建不出图，建出图发现样例过不去，就爆了！！！！！！111111111。单纯形板子背下来。

模拟最大流，模拟最小割，模拟费用流。

AT_arc107_f

我们知道经典结论 |a + b| \le |a| + |b|。需要我说吗。

考虑

然后就做完了，非常神秘。

这都推荐的什么题目，，，

号家军，代码源。

不如板刷 https://codeforces.com/problemset?tags=flows,2500-3500。

最大权闭合子图。

http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3426&tid=j

用汉字输入数字的题是何意味？？？

CF802C

这个题，看作 DAG 路径覆盖。然后代价是一个路径上相邻两个点在贡献，就可以在合并两条路径的时候算。

CF132E 输出方案。

你再联想一下，发现 P1251 的建图思想和这道题实际上是差不多的，详见（Ⅱ），而且我也没有理解到本质。24 题选得也太好了。或者是 P4553。

这启发我们，如果一个流量算贡献会算多次，但是流动的方向构成一个 DAG，就可以拆成入点和出点，按拓扑序每次假定前面的点的已经流完了，可以直接从出点连过来用。

at_arc142_e。

at_agc031_e。

每个维度上的限制形如 \sum [x \le a_i] \le b_i 或 \sum [x \ge a_i] \le b_i，这个是不好用网络流处理的。

考虑枚举选的点数 k，然后把所有选的点按 x 坐标排序，限制就是 x_{b_i + 1} > a_i 或 x_{k - b_i} < a_i。如果实际上没有排序，就是 \forall j > b_i, x_{j} > a_i 或 \forall j < k - b_i + 1, x_{j} < a_i。这样我们就得出了一个维度上 x 坐标排名为某个数可以选的区间。也就是可以得出在所有选的 k 个点中，横坐标第 i 大的可以匹配哪些点，以及纵坐标第 i 大的可以匹配哪些点。

然后就是一个匹配问题，用 P2891 的方法就能做两个维度，一个流的意义就是选了一个物品且它的 x 坐标排名和 y 坐标排名是多少。可能并不是真正的排名，但是并不重要。三维好像就做不了了，令人感慨。

但是。

你可能觉得这个题解做法没什么道理也很难想到，所以我们还有更轮椅的无源汇上下界最小费用可行流做法。

还是考虑枚举选的点数 k，就能把，两个方向上的 \le 限制，转为一个方向上的 \le 和 \ge 限制。

非常酷炫，而且点数和边数都是线性的。

反正还是每次增广一个环，环上有限制。

P6621。

线性基有什么用。

对于 c_i \not\in A，它可以被恰好一种方法异或出来，额，啊，对，不然它就不是线性基了，所以说，所以说呢，比如说，什么东西，直接保序回归就可以了。

感觉线性基和生成树确实是有共同点的。就像一个非树边加上去会恰好形成一个环。

CF1383F。

Dinic 过不去，Dinic+FF，EK 能过。

三句话讲题

题意题解复杂度

nodgd

CF884F。

合法当且仅当每个数出现次数不超过一半。

考虑对于一个方案判合法。考虑对每一种数判合法。

对于每一种数，\frac n 2 个数对可以划为出现它零/一/二次的，所有出现两次的都要选，出现零次的也要选这么多个。

也就是说，对于出现两个相同数的数对，可以钦定选其中较小的一个删掉，然后这些之间可以互相换不会更劣，除非有一个超过了一半就要和别的换。

这不是直接贪完了吗，为什么是 flows。

CF708D。

如果容量不用改，就按上下界的那个做法做。

然后感觉一下，可能如果原来的流量都不超过容量，容量就真的不用改。真的吗。好像是假的，但是可以把流量超过容量之后增长的代价设为 2，原来的设为 1。而且费用流一定会优先流费用小的，还不会流出来正环，反正这样就是对的。

CF1288F。

一条边有三种状态可能会有点鬼扯，但是仔细想一下，发现流可以设为 +1，-1，0 三种状态，刚好又能表示出一个点上两种颜色边数差这个信息。实际上两种颜色的代价又不一样，还是要建两条边，但是一条边上同时有红色和蓝色一定不优。

这些题是怎么评出来黑的。。。

CF1766F。

乍一看好像预分配然后做一下就可以了，仔细想一下发现不好算，但是预分配完了每条边只能流偶数流量也不可能把剩余的奇数流量流出去，所以有解的时候每个点的剩余流量也需要是偶数，所以真的就直接做一下就可以了。

写的时候因为 \inf - \epsilon < \inf 没判出无解 WA on 117 了。

用一个晚自习做了若干道没有意义的题，令人感慨。

P10383。

取模还原。可能有用但是好像也没什么用。不想写了，可以看官方题解 https://www.luogu.com.cn/article/tn27td0x。

你可能会想知道这个和网络流有什么关系，但是这并不重要，因为我也不知道。

1.12 冬季环校跑

♿！♿！♿！！！

1.17

打表观察，发现 m = 0 时答案为 0，m = 1 时答案为 2^n - 2。 m = 2 观察不出来，就不知道了。🤡。

T1。

\begin{cases} a_1x_1+a_2x_2+\dots+a_nx_n \le p\\ b_1x_1+b_2x_2+\dots+b_nx_n \ge p\\ x_i\in\{0,1\}\\ \end{cases} \\ \min\{c_1x_1+c_2x_2+\cdots+c_nx_n\} \\

其中 a_i \le b_i

因为觉得 duang 不会线性规划就没有被诈骗。x \in \{0, 1\}，显然很可能取实数更优。但是怎么做呢。

直接背包 DP 记当前的 \sum a，\sum b 状态和转移是 \mathcal O(n p^2) 的。

可以把每个物品看成体积为 a_i \sim b_i，代价 c_i 的一组物品，每组物品选至多一个使得体积和恰好为 p，代价最小。单调队列优化。

如果是要求 \sum a \le L \land \sum b \ge R 且 R - L = \mathcal O(1) 能不能这么做。

T2。无源汇费用流，每次增广一个环。或者这个 https://www.cnblogs.com/jr-zch/p/19496729。总之钦定每个点的入度出度之后每条边经过了多少次也是确定的，不用管实际上是怎么流的。

T3。

异或。现在连了所有 < 2^i 的边，前 m - i 位相同，形成一些连通块。然后合并起来。这样的话一定是最优的。

这个东西我们就很好 DP。

这不是我们 P13833 吗。

今天有体育活动吗。

还有批斗大会。

从头再来。

没有从头再来。

Ucup。

https://qoj.ac/contest/2921

通信题。

CSP 的初赛题。扔鸡蛋。

1.24

这个 T1 感觉像组合计数题。考虑刻画轮换的形态。

发现如果把一个轮换看成一个整体，它是可以直接跨过其它字符的。

所以我们从串中不断删去轮换，答案就只和轮换数量和剩余的不能组成轮换的字符的数量相关。

然后尝试打表？？？然后发现这个是一个关于？的？次多项式？？？然后？？？

T2 好像可以费用流，所以正解可能是模拟费用流。

T3 这种一看就是 NP 的。看一下数据范围发现真是 NP 的。

这周打了 O(???) 场比赛，令人感慨。

这个 T1 看着像多项式题，但是我们不会打任何多项式板子，怎么办呢。

这？打了 O(???) 场？？，令人感慨。

这套题的标题是省选模拟赛，所以我们考虑更稳健的打法。

这周打了 O(1/n) 场比赛，非常酷炫。

怎么会是 DP 呢，DP 这个感觉非常会算重，而且这个形式看上去非常组合。

怎么真的是多项式？？？f = 1 + x^4 f^4。啥啊。多项式快速幂可以先 ln 再 exp。

需要精通群论和多项式。。。还是考虑 DP 吧。

为了不算重，钦定每次插入最前面的。

有人说这道题是原题，因为 http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3011&tid=Q。在一年半之前，比当时的我们大一个年级的学长给我们讲了这道题。但是我当时在睡觉并没有听懂。现在讲这道题的时候我还是在睡觉，令人感慨。

与此同时的，在一年之前

我之前也不太喜欢补题，总觉得 T3，T4 讲了听了就行了，补题没啥用处。但是在CSP，NOIP的备战阶段让我不再相信这种想法。只有真真正正地上手补了题，才能知道一些实现的细节，这些实现细节可能就是题目的关键，补题对实力提升还是很有帮助的。

但是

我觉得这就是很垃圾。你们都给我滚吧。

令人感慨。

1.27 夏老网吧

都是我自己的问题.

胆小无能如果我自己好好复习了.

不会有这事的. 如果我把生

物书的每个角落都看得滚瓜烂

熟. 任凭怎么对答案. 伤心的也只

会是别人。

我为什么要这么脆弱.

我这么脆弱是为了什么？

我就是个傻子.

我就是个神经病.

我不能存活下去.

1.30

期末？？？

whk 期末年级排名四位数，令人感慨。

你会卡 Dinic 吗。

这个大样例也太垃圾了。

差分约束。

最短路是保证 f_v \le f_u + w 的情况下使得 f 尽可能大；最长路是保证 f_v \ge f_u + w 的情况下使得 f 尽可能小。

而且这道题也不用线段树分治啊，因为限制所在的时间区间只会互相包含，直接撤销就行了。

2.1

AT_arc191_d。

AT_abc288_h。qoj6184。

AT_arc168_f。

div2 蓝黑黑，吓哭了。

这道题 myfjchx 都不会做。不用管。

猜测其中一个人一定走最短路从 T 走到 S，所以另一个一定是先从 S 出发不经过 T 走到一个不在最短路上的点，再从这个点出发不经过 S 走到 T。写了过不去最后一个大样例的最后一个点，交上去 70 分。

为什么呢，猜测我们猜错了，不一定其中一个人走最短路。但是为什么呢。应该是 S 到 T 的最短路唯一而且是一条链。

构造出一个 \underset{\normalsize\text{\ \ \ \ \ \ \ \ \ }\bigcirc}{\underset{\tiny\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |}}{\overset{\normalsize\text{\ \ \ \ \ \ \ \ \ }\bigcirc}{\overset{\tiny\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |}}{\normalsize\text{S--T--}\bigcirc}}}} 状物。这个 \LaTeX 打得也太好了。也就是一个度数至少为 3 的点。判掉就过了。

FWT 是什么。

nodgd。

为什么是提交答案题。

这道题 tourist 加一个 zhoukangyang 都不会做。不用管。

这个东西看上去就是没法直接维护的。

首先不难想到转成差分，就是首个非零位置减 1，指定位置加 2。

虽然这个并没有什么本质区别，但是，你考虑，要求的是 \sum a_i = \sum \sum d_i = \sum d_i \cdot (n - i + 1)。

所以把每个 d_i 看成 d_i 个 i，每次就是从多重集里面删掉最小的数，插入某个数，答案就是最后剩下的所有元素的和。

然后考虑把每次删掉的数求出来，就是之前未被删除的数中的最小值。

虽然可能还是没有本质区别，但是我们非常突兀地考虑费用流。

每一个流的意义就是在某时刻加入的一个数在之后的某时刻被删掉，每个代表删的要尽可能满流，流量最大，删的数尽可能小，费用最小。

也就是说，我们把一个数据结构题模拟成了费用流，再用数据结构模拟这个费用流。

总之就是考虑改了边权之后可能出现负环，就要反悔。对应原问题就是这个加的数更小导致另一个数没有被删掉。

反悔就有两种情况

线段树维护一下就可以了。

值得注意的是，n 个点 n 条边的图不一定是基环树森林。小丑恩偶滴基地。

2.2

9:30-9:40，11:10-11:20，16:00-16:15，19:50-20:00。

2.12-2.25。

🐕🐋，抽象代数，组合数学，容斥原理，生成函数，Burnside。

2.3 图上数据结构

图上有啥数据结构啊，不都是树吗。

我常常追忆过去。

P7737。

这个条件说的是图的连通性，但是有向图的连通性我们只会强连通分量缩点，所以从这个方向考虑，发现这个图缩点之后是一个叶向树。更准确地说，直接缩点后是一棵叶向树加一些前向边，因为根据这个条件任意两个点的可达点集相交一定包含。

然后这个问题问的是加两条边后 S 可达点集与可达 T 点集的交的大小。追忆过去。

加边可以先分讨一下。如果是前向边，就没什么用。如果是返祖边，就可以把一些缩点。如果是横叉边，就不是树了，令人感慨。

但是要加两条边，所以考虑不分讨了。仔细考虑一下，S 可达点集一定是 \mathcal O(1) 个子树的并，可达 T 点集一定是 \mathcal O(1) 个祖先链的并。然后这两个的交就是什么呢。然后在 dfs 序上把子树拆成 \mathcal O(1) 个区间，把链拆成 \mathcal O(\log n) 个区间，互相求交再求并，就做完了。

实现得一坨，复杂度好像是 \mathcal O(n + m + q (k ^3 \log k + k^2 \log n \log k + k^2 \log n \log \log n))。

AT_joi2025ho_e。

内向基环树。森林。每个路径是唯一的。不妨先放到树上考虑。放到链上考虑。这可做吗。

会不会有若干人在同一个位置时，让终点更远的人先走一定不劣。对吗。感觉很有道理。

怎么维护呢。

而且给的还是一个基环树森林。

因为互测赛 T1，如果所有人一起走不好维护，考虑看成一个人走完下一个再走。一个人所有时间的移动比一个时间所有人的移动好处理。

所以如果我们有一个类似深度的东西，然后两个人在同一个位置时终点深度小的先走，就可以让终点深度小的先走完。虽然我不知道在基环树上怎么定义深度，而且这个还是不好维护。

看一下题解。

这个思路可能是做不了的。。。

我们对于每一条边，只考虑经过它的路径，计算最后一次被经过的时间的最小值。这些路径的起点到它的距离按经过顺序依次为 d_1, d_2 \dots d_n，就有 t_i = \max(t_{i - 1} + 1, d_i)。你可能感觉这个不对但这个其实是对的，是你感觉的问题。然后 t_n = \max\{ d_i + n - i \}，显然 d 从小到大排序时取最小值。

然后把每一条边的这个算出来之后，每条边是互不影响的，直接取所有边的最大值就是答案。为什么呢，因为如果有一个不经过当前边的路径和一个经过当前边的路径同时到达了同一个点，根据最开始的那个贪心策略，一定可以让经过当前边的路径先走。

bzoj5218

bitset 优化 Kosaraju。

我们来做 CF 吧。

CF2187A。

考虑什么情况下可以交换两个数 x, y。如果 |x - y| \ge k 肯定可以，而且如果存在 z 使得 |x - z| \ge k \land |y - z| \ge k 也是可以的。也就是说 f(x, y) = |x - y| \ge k \lor ((\exist z) f(x, z) \land f(y, z))，是一个类似连通性的东西。

然后把原来这个序列转成一个新的序列，就会形成若干置换环，要求每个置换环里的点连通。但是一个数可能出现多次。显然不影响，因为连通性只和它的数值有关，具体哪一个不用管。

所以我们先二分一下，然后并查集求一下连通性，再判一下，就过了。

仔细考虑一下，连通性就是把 \ge min + k 和 \le max - k 的都缩成一个点，剩下的是孤立点。然后也不用二分和并查集了。

B。

如果 $\max\{x + y - p - q, x - y - p + q, -x + y + p - q, - x - y + p + q\} \le t$，那么 $x + y - t \le p + q \le x + y + t$，$x - y - t\le p - q \le x - y + t$。 然后 $x - t \le p \le x + t$，$y - t \le q \le y + t$？ 或者我们直接分讨把绝对值拆开。 分讨不动，所以猜测一定是 $p \le x \land q \le y$ 时最优。对吗。我错了。 如果说一个数变大了，那么就应该是把第一个都是一的位置向上进位，搞到上一个都是零的位置。感觉很对。 ## 2.3 数理逻辑与图灵机。 公理证勾股定理。 自然演绎法。 希尔伯特。一致性，判定性，完备性。 哥德尔不完备定理。 康托尔对角线。 <https://matrix67.com/blog/archives/4812> <https://matrix67.com/blog/archives/4930> <https://matrix67.com/blog/archives/901> 图灵是给。 这很让人难过，但我们不得不正视这个问题。 图灵机映射到整数，是可数的，但定理不可数。 停机问题。 神谕。 图灵测试。 ## 2.5 qoj9449。 如果不要求两组人数相等，就贪心地放，判断是否有解，是容易的。 然后现在，就是有若干二分图（孤立点就是一侧一个点一侧零个点的二分图），问是否能给每个二分图选一个方向使得一侧大小为 $n$。 其实就是说有一些物品，体积为 $a_i$ 或 $b_i$，问是否能拼出一个 $n$，需要动态加删。 所以就做一个背包记一下方案数，直接做是 $\mathcal O(nm)$ 的。但是我们发现如果在某次合并时这个不合法不妨就反向合并上去，次数就是对的，复杂度 $\mathcal O(n^2)$ 的。 qoj8839。 qoj10109。 非常爽的构造题，虽然我不会。 ## NOIWC ### Day 0 第一次参加 WC，第一次写 WC 游记，可能有点差。嗯嗯。 好像还有点魔怔。 而且是第一次写游记。 坐飞机来到山东省青岛市城阳区流亭街道重庆北路 398 号。老早就听说山东的特产是淄博烧烤了。可惜我不是很能吃辣的，没能亲自品尝淄博烧烤的美味。让 mian 帮我代吃了。 作为 CCPC 银牌大佬，我对拿下这场 WC 志在必得。还记得上次和上上次 WC 时，我还没有打，令人感慨万千。 反正就是开打了，那个荔枝味的水挺好喝的，让我想起了葡萄。葡萄汁也很好喝，但是那个发的笔里面的墨水不太好喝，因为是黑色的，和石油一样。 ### Day 1 乘着校车，我来到了某某中学。踏进了我一点也不熟悉的学校，找到了我一点也不熟悉的教学楼，来到了我一点也不熟悉的教室，看着上面的标牌——11班，我回来了！ 可能读者还没有意识到，这个故事和大石头到底有什么关系。大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大古明地恋大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头大石头。 哇，好大的石头啊！咕咕嘎嘎！Tomorin 说：“咕咕嘎嘎。"练习时间到！Tomorin 拿起吉他和话筒（实际上是 Bocchi 拿起了吉他，Anon 拿起了话筒，Tomorin 是企鹅黑客。咕咕嘎嘎。），Rana 拿起了吉他，東京都拿起了其他乐队成员。结果 Rana 吃了太多抹茶芭菲，非常冷，就把東京都变成了北极。于是東京都因为自身原因退出了乐队，而且它从来就没有觉得组乐队开心过！ 然后ink三上、就进入了二阶段，他会画催更，epic，整齐sans，欺骗传说sans，还有炒鸡sans，还有病毒sans，还有oceansans，还有极端san.s.。1980生气了，召唤了360sans，傻掉了病毒sans。 这令我非常愤怒，我可是高层叙事者啊，怎么能让让怎怎么能让么怎怎让能怎能让么怎让让能能怎么能让怎能让么么让怎么让能能么能让怎 ### Day -97 CSP-S 还并没有发生过。 ## 2.6 T1 是二次剩余。 T2 是插头 DP，斯坦纳树。 T3 是分数规划。 --- $p$ 不是质数？？？ 我们发现 $x = \dfrac{b + \sqrt{d}}{2}$ 是 $x(x - b) = \dfrac{d - b^2}{4} \le 5e8$ 的一个解。所以 $x^n$ 就是一个？？？$b = \lfloor \sqrt{d} \rfloor$ 说明？？？ $x^n$ 也很诡异，因为 $n$ 可以等于 1。 二次剩余？？？ciallo 二次剩余。ciallociallociallo。 --- 牢板选题的品味还是太独特了。。。 --- WC 开幕式。dzd 讲话。dzddzddzddzddzddzddzddzddzddzddzd。dzd 发表反动言论。pzppzppzppzppzppzppzppzppzppzppzp。 https://www.luogu.com.cn/article/yj0gp7iz --- P3263。 四个小时没看到取整符号。 数学还是太难了。你期末考试数学上三位数了吗？？？ --- P7450。 容易联想到斯坦纳树。 但是斯坦纳树怎么做？ duang 三句话讲完的，我也不知道听了什么。 无根树不好算不妨考虑有根树。 首先显然要状压。但是又不能存图的形态只能记包含的关键点点集。 然后现在对于一个点集求出了生成树，剩下的就是从生成树上某个点再接出去一棵树，需要把这个状态记到所有可能作为连接的点上面。 如果边集重合转移出来是不优的。 $\mathcal O(3^k n + 2^k m \log m)$。 这道题，如果 $c_{i, j} \le k$，直接斯坦纳树就做完了。 然后随机分 $k$ 组跑斯坦纳树，每次正确率 $\dfrac{k!}{k^k}$。 https://oi-wiki.org/misc/rand-technique/ 一次的正确率是 $p = \dfrac{1}{\lambda}$，$T$ 次的错误率就是 $\left(1 - \dfrac{1}{\lambda}\right)^T = \left(\left(1 - \dfrac{1}{\lambda}\right)^\lambda\right)^{\frac{T}{\lambda}} < \left(\dfrac{1}{\mathrm{e}}\right)^{\frac{T}{\lambda}}$。 也就是说每 $\lambda$ 次可以使得错误率至少变为原来的 $\dfrac{1}{\mathrm{e}}$。 那么比如我们要求错误率不超过 $\dfrac{1}{10000}$，最多需要 $\lambda \cdot \ln 10000 \approx \dfrac{10}{p}$ 次。 这道题正确率为 $p = \dfrac{5!}{5^5} = 0.0384$，然后就要跑 $\dfrac{10}{p} \approx 260$ 次。 其实我想说的是，复杂度和 $\lambda = \dfrac{1}{p}$ 成正比。就像 MikeZ 说过，一个概率为 $p$ 发生的事件发生需要的期望次数为 $\dfrac{1}{p}$。 那为什么不直接把 $\lambda$ 种情况遍历一遍找到可行的那一个，复杂度也是和 $\lambda$ 成正比的。 比如说这道题，求出答案的正确性就只和答案中的 $k$ 个颜色是否分配正确有关，而对于整个随机时每个子集也是随机的。 --- bzoj3232。 首先分数规划，但是贡献分别在格子和边上，就不好。 酷炫手法。 每一行的格子做一个前缀和，然后经过一条边的时候就加上或减去这个前缀，把格内的贡献放到边上。 但是。 这个做法太垃圾了。我们考虑更有道理的东西。 边不好考虑，我们考虑格子。 选一些格子，要求实心四连通。 发现实心不用管，因为空心的一定不优。 发现连通不用管，因为分别走两个相当于取平均一定不优。 然后还是分数规划。 就是直接每个格子选了有贡献，相邻的不同有代价。 这个问题可以用最小割解决。 。。。 过于有道理了。 边权是实数。好像不用管。 复杂度也不用管。$\mathcal O(n^3 \cdot m^3 \cdot \log(10^3 \cdot n \cdot m \cdot V))$。 ## 2.8 CFdiv2。FWT。FWHT。 --- ARC214。上次 ABC 掉了 98 分现在不能 rated 了，，， B。这道题比整个 div2 加起来还好。 有一个无向连通图，选一个边集，使得每个点度数都为奇数。 点数为奇数时显然无解，否则给出构造，每次把 $2k - 1$ 和 $2k$ 间的一条路径取反，就是对的。直接选生成树上的路径。也就是说，有一个生成树后，如果一条边向下的子树大小为奇数就选，归纳出来也是对的。 C。这道题比整个 div2 加 B 题还好。 很智慧，但是比较典。 把这个看成初始在原点位置，然后第 $i$ 次可以在四个方向选一个并走 $p_i$ 的长度，最后回到原点。 ![](https://cdn.luogu.com.cn/upload/image_hosting/wekmoz3c.png) 然后就是分别找两个大小为总和一半的点集，再判一下空集。 D。 $n \le 13$。可以打表。 啥啊。 我们考虑直接让 $\dbinom{2n - 2}{n - 1}$ 条路径按字典序从小到大对应 $\left[0, \dbinom{2n - 2}{n - 1}\right)$。 然后就每次找这条路径，它最多只会有一个位置还没有填，根据它是第几条把这个没填的填上就可以了。 为什么最多只会有一个位置而且这样填出来非负而且不需要填的时候恰好是对的，反正题解没说，我也不知道。 ## 2.9 T1。 计数的是结果，但这个结果显然是不好直接统计的，考虑把每个结果双射到过程上，要求步数最小，所以每条边只会往某个方向走，枚举步数以及正向边、反向边、零边的数量。零边必须是中位数，不然绕一圈整体加一或减一绝对值之和会更小。 然后呢，我们要求步数最小，但是求的是恰好 m 步，我们就可以走一些没有用的。比如说来回走，就会加 2 步。绕一圈就会加 n 步。n 是偶数只用加 2 步。n 是奇数的时候你就可以转一圈。而且转一圈以上不优。 甚至不用推式子，预处理一下卡卡常就过了。 T2。 模拟最大流。模拟最小割。然后直接树形 DP，$\mathcal O(n^2)$，就能过了。好像比 T1 简单？？？ ## 2.10 在 212 和初三打模拟赛，在 212 评讲，在 212 上晚自习。 会赢吗。 --- 。。。 ![](https://cdn.luogu.com.cn/upload/image_hosting/0bw4ridc.png) T1。 求这个东西，如果不要求极小，就 DP，然后极小，就考虑容斥，每个正交集的超集都是正交集，发现容斥不出来。 极小，就是说每一个都不能删。所以就钦定出来哪些位置超过 1 个 0，然后选的就不能被这个包含。精细实现可以做到 $\mathcal O(T \cdot n \cdot 5^{\log V})$，80 分。$\mathcal O(T \cdot n \cdot V^{\log 5})$。 $a^{\ln b} = b^{\ln a}$。怎么我之前不知道。 T2 意味。两个路径相交就会有一个的 LCA 在另一个路径上。 然后，静态，树上，点加链查（就是子树加点查）、链加点查，差分一下都是 $\mathcal O(1)$ 的，瓶颈在求 LCA。 T3。 --- bzoj4762。 就是说啊， $[\bigwedge x_i] = \sum\limits_{S \neq \varnothing} [\bigvee\limits_{i \in S} x_i] \cdot (-1)^{|S| - 1}

为什么这个是对的呢。因为这个是一个 min-max 容斥。哈哈哈。

我们要求的东西是

\begin{aligned} & \sum_{S} \left( \text{bitand}(S) = 0 \right) \land \left( \bigwedge_{x \in S} \text{bitand}(S \setminus x) \neq 0 \right) \\ = & \sum_{S} \left( \text{bitand}(S) = 0 \right) \land \sum_{\varnothing \neq T \subseteq S} \left( \bigvee_{x \in T} \text{bitand}(S \setminus x) \neq 0 \right) \cdot (-1)^{|T| - 1} \\ = & \sum_{S} \left( \text{bitand}(S) = 0 \right) \land \sum_{\varnothing \neq T \subseteq S} \left( \underset{x \in T}{\text{bitor}}(\text{bitand}(S \setminus x)) \neq 0 \right) \cdot (-1)^{|T| - 1} \\ = & \sum_{S} \sum_{\varnothing \neq T \subseteq S} \left( \text{bitand}(S) = 0 \land \underset{x \in T}{\text{bitor}}(\text{bitand}(S \setminus x)) \neq 0 \right) \cdot (-1)^{|T| - 1} \\ \end{aligned}

然后你记一个状态 f_{i, j, k} 表示当前所有满足 \text{bitand}(S) = j，\underset{x \in T}{\text{bitor}}(\text{bitand}(S \setminus x)) = k 的集合对 T \subseteq S 的权值和。容易发现 j \subseteq k，所以状态数是 3^{\log V} = V^{\log 3} 的。

j k
\{x\} = T j \& x j
x \to T j \& x (k \& x) \| j
x \to S \setminus T j \& x k \& x
x \to \complement S j k

。。。

为什么啊。你不觉得这很诡异吗。

bzoj4644。

动态全局最大割。

很酷炫的题目。题目名字也很酷炫。

对于一个带权无向图，定义一个点集对应的割为恰好有一个端点在这个点集中的边集，动态加边，求边权异或最大的割。

注意到，我们将一个点的点权设为其邻边边权异或值，一个点集对应的割就是点权的异或值。

然后就是动态加删求一个最大异或点集，是线性基经典问题。

2.11

T1 0.2s，T2 0.1s。sans 出的题。

T1 如果一个连通块的边数大于等于点数，就全赋为 1，否则是一棵树。

如果是一棵树。真的有解吗。

如果有解，把点权为零的删掉，就得到了点权全部不为零的解。

是有解的，比如一个 2 连出去四个 1。

然后，每个点的度数都不超过 3。

然后怎么做啊。

如果把点 u 权值设为 0 并删掉，就会减去 x_u (\sum x_v - x_u) 的贡献。

不妨设这是一个有根树且每个父节点点权大于等于子节点点权。要求 \sum x_u (x_{fa} - x_u) \ge x_{root}^2。

。。。

我觉得这就是垃圾。你们都给我滚吧。

https://vjudge.net/contest/789492

2.11 https://codeforces.com/contest/2196

2.15 https://uoj.ac/contest/105

2.22 https://atcoder.jp/contests/arc215

2.22 https://codeforces.com/contests

A。

首先把包含的删掉。

然后考虑钦定。

\displaystyle \frac{1}{10^n} \sum_{i = 0}^m (-1)^i \sum_{|S| = i} \prod_{i \in S} (10 - a_i) \prod_{i \not\in S} 10

2.15

A。

惊奇地发现价格可以是一个实数，，，