官方题解。来源：清华大学学生算法协会仓库

题目很明显是一个最小割问题。对于题目描述中的“通知一个分部，在其所有下辖的铁路上设立检查站”操作，我们需要对如下问题进行网络流建模：给定网络流图以及对其边的划分，一次可以以 $1$ 的代价割掉一个划分集合中的所有边。特别地，在同一个划分集合中的所有边都与某个点相邻。

考虑某个形如 $A_i \to x_i \to B_i$ 的划分集合，其中 $A_i$ 和 $B_i$ 为任意点集。考虑如下建模：

• 建立虚点 $p_i, q_i$；
• 有边 $(p_i,q_i,1)$、$(A_i, p_i, 1)$、$(x_i, p_i, 1)$、$(q_i,x_i,1)$、$(q_i,B_i,1)$。

注意到在这个建模中，若所有边都不被割掉，其连通关系恰好为 $A_i \to x \to B_i$，而割掉 $p_i \to q_i$ 之后这个连通关系就消失了，符合我们的需求。

再注意到网络流图上的所有边边权均为 1，直接运行 dinic 算法求解最大流的复杂度为 $O(n \sqrt{m})$，足以通过本题。

官方题解。来源：清华大学学生算法协会仓库

给定三种记号：

• $s_i\text{#}s_{i+1}$ 表示读完 $s_i$ 后应紧跟 $s_{i+1}$，且优先级高于其它两种符号；
• $s_i\text{*}s_{i+1}$ 表示读完 $s_{i+1}$ 后再读 $s_i$；
• $s_i\text{p-q}$ 表示（在不考虑的情况下）（如果有则）先读对应的 $\text{p-(q-1)}$ 前的文字，读完 $s_i$，再读对应的 $\text{p-(q+1)}$ 前的文字。

给出一个排列 $p_i$，求一组记号使得阅读 $p_i$ 的顺序恰好将其还原为 $1 \sim K$ 的排列。

$1 \le K \le 10^6$

先考虑只有最复杂的 $\text{p-q}$ 时应该怎么处理。

可以想到用栈来保存当前的遥远跳转结构，如果碰到可以直接阅读的则将栈清空。

如果有多个遥远跳转结构怎么办？栈套栈！每弹出一个栈，更新新栈顶的栈的嵌套层数。

在此基础上可以实现另外两种符号，其中 $\text{*}$（及其连续段）需要根据头尾情况简单分类讨论一下。想清楚了实现起来并不复杂。

复杂度 $O(K)$

官方题解。来源：清华大学学生算法协会仓库

出题人：abruce

做法：考虑不能出现新的黑点，那么每个与黑点相邻的点要么它自己一开始染白，要么与其相邻的灰点，即其父亲或儿子一开始被染白。

考虑如下 dp：$f_{u,0},f_{u,1},f_{u,2},f_{u,3}$ 分别表示在 $u$ 染白点，$u$ 儿子染白点，$u$ 留给父亲染白点，$u$ 什么也没干。转移考虑 $u$ 的每种情况和 $u$ 的儿子的每种情况是否适配即可。

官方题解。来源：清华大学学生算法协会仓库

Sol1：直接分类讨论，如果 $n\leq 20$ 则最终比分一定是 $11:n-11$，如果 $>20$ 一定是 $n/2+1:n/2-1$，这也代表 $n>20$ 的时候一定是偶数。

令已知信息依次为 $(a_{i_1},b_{i_1})\dots (a_{i_k},b_{i,k})$，注意我们认为初始比分 $0:0$ 和上述的最终比分也是已知信息。那我们可以发现每一个 $(a_{i_j},b_{i_j})$ 变化到 $(a_{i_{j+1}},b_{i_{j+1}})$ 的过程是独立的，可以分别计算。

若 $n>20$，我们将 $10:10$ 也当成一条信息加入，那么 $10:10$ 之前相当于网格路径计数从，是一个组合数形式（注意有序对这里是否乘 $2$ 的细节），对于后序每一局的比分实际上都是确定的，在 $x:x$ 变成 $x+1:x$ 时乘 $2$ 即可。

Sol2：DP，注意到任意时刻比分差不超过 $11$，所以直接 $f_{i,j}$ 表示前 $i$ 局比分差为 $j$ 的方案数，然后写一个判定状态是否合法的函数即可，避免很多细节。

官方题解。来源：清华大学学生算法协会仓库

题目简述

给定正整数 $n$ 和长为 $n$ 的正整数序列 $a$。对于正整数 $x$，定义$\newcommand{dfrac}[2]{\displaystyle\frac{#1}{#2}}$

$$f(x)=\begin{cases}0&(x>n)\\f(x+\gcd(x,a_x))+a_x&(x\leq n)\end{cases}$$

现有 $q$ 次操作，分为两类：

• 1 l r c：将所有满足 $l\leq i\leq r$ 的 $a_i$ 的值乘以 $c$。
• 2 x：查询 $f(x)$ 对 $998244353$ 取模的值。

做法解析

做法的核心是分块。将序列分为长度为 $B$ 的一些块，并维护块内每个位置不断向后跳时第一次跳出块时对应的位置和这个过程中 $a_x$ 的总和，则可以 $O\left(\dfrac{n}{B}\right)$ 的处理一次查询。修改虽然是区间修改，但维护新的跳到的位置时，$\gcd(x,a_x)$ 的改变次数最多是 $x$ 质因子分解后对应幂次的总和，可以说明总的改变次数是 $O(n\log\log n)$ 的，因此可以用 set 对每个质数维护还可能被修改的位置，每次修改时暴力重构整个块；而对于维护一路上的权值和，可以对整块的修改打标记、散块的修改直接暴力，复杂度为 $O\left(B+\dfrac{n}{B}\right)$。因此总的复杂度大致为 $O\left(q\left(B+\dfrac{n}{B}\right)+n\log\log n\cdot (B+\log n)\right)$，综合分析常数和理论结果，大致取 $B=300$ （差不多是 $\dfrac{n}{\sqrt3}$）时最优。

时限给了 $4\text{s}$，实际上 std 取 $B=300$ 需要跑大约 $1.3\text{s}$，取 $B=500$ 也只需要大约 $2\text{s}$，所以应该是完全不卡常的。

官方题解。来源：清华大学学生算法协会仓库

首先，X 把整个序列分成了若干段，段与段之间是独立的。

考虑每一个不含 X 的连续段，若这个段为 MWMW，如果 W 老师操作这个段，那么他拿走 WMW 一定是不劣的，因为拿走这个之后剩下 M，M 必须花一次操作拿走，如果剩下其他的，Menji 也可以花一次拿走，相当于，我们只给 Menji 留严格更少的选择。

但考虑这样的区间 WMWMW，W 老师不可能拿的只剩一个 M。

我们可以发现，如果有这个贪心，那么一个连续段只与其两端点，以及中间是否有其他字符有关。

我们将段分为 $5$ 类，WW，WMW，MM，MWM，WM，分别表示两端为 W/M，且中间是否有另外一种，比如 WW 代表两边都是 W 且中间没有 M，WMW 表示两边都是 W 中间有 M，WM 表示一边是 W 一边是 M。

令 $w_0,w_1,m_0,m_1,c$ 分别表示这些段的数量。

$c$ 的存在是无意义的，当 W 老师操作一个 WM 段时，一定剩下一个 M，此时 Menji 直接拿走这个 M，游戏回合数不受影响，这样的操作也不会影响平局，若一方因此不能平局，其可以在游戏的最开始先操作这个 WM 段。

那此时的操作可以看成，W 老师可以一回合内让 $w_0-1$ 或 $w_1-1$ 或 $m_0-1,m_1+1$，Menji 一回合可以让 $m_0-1$ 或 $m_1-1$ 或 $w_0-1,w_1+1$。略微讨论一下，可以发现 W 老师胜利条件为 $w_0+w_1<m_0+m_1$ 或 $w_0+w_1=m_0+m_1,m_0=0$。Menji 获胜条件为 $m_0+m_1+1<w_0+w_1$ 或 $m_0+m_1+1=w_0+w_1,w_0=0$。其余都是平局。

本题的灵感来源是一个之前玩过的桌游，四人分成红蓝两队，有 $25$ 个隐藏中文词，一些属于红队一些属于蓝队一些没有归属还有一个特殊词。所有玩家能看到所有词，但两队分别有一个人能看到所有词的类型（属于哪一队或是特殊词），两队能看到词类型的玩家轮流操作，说一个简单的短语，另一名玩家可以猜任意数量的词，无论是否猜中将猜的词移除，当一个队的词全部被移除时该队获胜，特别的，如果一个队移除了特殊词，该队直接失败。

题目其实是将高维空间的词看成一维空间的点并将描述看成区间，特殊词即为 X，似乎我目前还没有想出高维空间中的解决方案（假设一个描述是一个高位立方体？），欢迎大家思考一下。