梦熊 CSP-S 模拟赛题解 最后更新于 2025-05-02 08:43:12

唉，tlyz 都在出公开赛了，我连一道题都没出过，太菜了。 ------- ## A 假设目前所有垃圾桶的总攻击力为 $S$。那么第一轮对 youyou 造成 $S$ 的攻击，第二轮 $2S$，第三轮 $4S$……以此类推。最多 $O(\log(V))$ 轮后，youyou 就只能被一段前缀攻击了，使用线段树上二分。 ## B 梦回 2024 数学高联 T3。虽然完全不同。 考虑 yy 什么时候会反转。必然是，有一列有黑且有白，youyou 目前选的格子是黑。我们设这样的列的数量为 $cnt$。 youyou 能反转 $\min\{m,cnt\}$ 列。因此设 youyou 目前选的黑比白多 $S$ 个，答案就是 $S - 2\min\{m,cnt\}$。 当 $cnt < m$ 的时候，显然我们可以把所有的这样的列对应的白格选上，$S$ 减少一，而 $2\min\{m,cnt\}$ 减少二，更优。当 $cnt>m$ 的时候，我们可以提前减去 $2m$，然后不管他就行了。 ## C 先让 $c_1$ 和 $c_2$ 对 $n$ 取 $\min$。 如果 $y-x+1 \le c_2$，yy 的策略显然是尽量取完整个区间。如果他能得逞，youyou 就必须一步解决问题；否则，youyou 可以一个一个的拿，只需要保证区间最大值 $\le w_1$。 否则，yy 能操作的也是询问区间的长度为 $c_2$ 的子区间。离线一下很容易求出，每个长度为 $c_2$ 在什么时刻之后能被 yy 操作，即区间和 $\ge w_2+1$。（离线 + 线段树二分） 结论是：youyou 能赢当且仅当存在一个 youyou 能操作的区间包含了所有 yy 能操作的区间，且区间最大值 $\le w_1$。 充分性：如果存在这样的区间，youyou 可以先把不能被 yy 操作的位置都填满，不管 yy 怎么兴风作浪，最后直接抹除他的所有痕迹。 必要性：证明逆否命题。如果不存在，假设 yy 能操作的区间最左端点为 $L$，最右端点为 $R$。使用归纳法证明，yy 可以适当操作使得 $L$ 和 $R$ 中永远有一个不是红色。 模拟上述过程即可。 ## D 原神。 首先，发现这个问题不能用三进制 trie 树或者分析数论性质啥的，那么直接转为图论问题。 也就是，对于每个 $z$，求有多少对 $(x,y)$，使得存在一条从 $z$ 出发的简单路径 $\mathcal Z$，使得 $x$ 和 $y$ 之间的每一条简单路径 $\mathcal F$ 都恰好和 $\mathcal Z$ 有一个公共点。 下文开始意识流，我也不知道为什么是对的，因为开这道题的时候只有 $40$ min 了。 先把圆方树画出来，考虑 $x$ 和 $y$ 之间的那条链。如果 $z$ 在这条链上，那么取 $\mathcal Z = \{z\}$ 即可。如果 $z$ 不在链上，且沿简单路径走到达路径上的第一个点为圆点（原图中的点），那么也是合法的，取这条圆方树上这条简单路径对应的任何一条原图上的简单路径即可。 我们证明这是充要的。如果到达的第一个点是方点，那么到达方点之前和到达方点之后是同一个点双里面的两点 $(u,v)$，其中有 $u \to v$ 的边。 如果这条路径到 $u$ 就停了，根据点双的性质，我们可以把 $u$ 删去，也就是存在一条从 $x$ 到 $y$、不经过 $u$ 的简单路径，不合法。 否则，考虑必然有一条路径同时经过 $u$ 和 $v$。 证明是显然的。考虑沿圆方树上 $x$ 到 $y$ 的路径走，第一次进这个点双和出这个点双分别是 $A$ 和 $B$。 根据点双的性质，存在 $A \to u \to B$ 和 $A \to v \to B$ 的两条简单路径。 如果 $A \to u$ 与 $v \to B$ 无交点，构造 $A \to u \to v \to B$ 即可。 否则，设交点离 $A$ 最近的为 $t$，构造 $A \to t \to v \to u \to B$ 即可。 然后就是简单的树上计数问题，随便换两次根应该就可以完成。 ------ 学 MO 真的可以提高 OI 水平啊。 这几天学了好几天 MO，发现证明结论的逻辑更加清晰了，尤其是通过构造来证伪的水平。 大家一起来学 MO！