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

CRT或是简单枚举即可得到答案 $83$

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

题目很明显是一个最小割问题。对于题目描述中的“通知一个分部，在其所有下辖的铁路上设立检查站”操作，我们需要对如下问题进行网络流建模：给定网络流图以及对其边的划分，一次可以以 $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}$，所以应该是完全不卡常的。