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

给定三种记号：

• $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，似乎我目前还没有想出高维空间中的解决方案（假设一个描述是一个高位立方体？），欢迎大家思考一下。

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

考虑自然的图论模型，$n$ 个点，$i$ 连向 $a_i$。如果没有 $(j-i) > 1$，显然只需要 $n$ 减环长次操作就可以排序。注意到这个排序策略必须要每一次都环数 $+1$ 才行，也就是每一次操作都在环内。

当我们不能用环长 -1 次环内的不相邻交换操作排序，我们就称这个环是难的。认为自环不是难的，这样最终状态没有难的环。显然编号相邻的二元环是难的，所以有难的环。考察什么样的环是难的。

如果一个环在编号上占据的不是一段区间，那么它不是难的：假设存在一个 $l$ 不在环上且有 $>l$ 和 $<l$ 的点在环上，那么必然存在一条 $<l$ 到 $>l$ 的边，也存在一条 $>l$ 到 $<l$ 的边。任选其中一条边交换，可以让 $<l$ 或者 $>l$ 的点的个数减 1 并获得一个自环。一直做直到两边都剩一个点，这个时候交换它们俩就行了。

考虑值域连续的环，设其长度为 $l$。注意到若存在一个 $i \in [2,l-1]$ 它的位置不是 $i-1$ 或者 $i+1$，就可以通过把 $i$ 归位创造一个长度为 $(l-1)$ 的值域不连续的环。因此这样的环不是难的。

所以难的环一定有 $i \in [2,l-1]$ 的位置要么是 $i-1$ 要么是 $i+1$，即可以选左右。注意到若 $p$ 选右 $p+1$ 选左就会有二元环不符合这个环长条件，所以一定是一段前缀选左一段后缀选右，所以环长成 2 3 4 5 ... k n 1 (k+1) (k+2) ... (n-2) (n-1) 这个样子。

当这个环不是 2 3 4 5 ... (n-1) n 1 的时候，你总是可以通过归位最小或最大元素，把这个环归位成 2413，此时存在一个三步的做法：交换 23 之后交换 24 和 13。

而当这个环是 2 3 4 5 ... (n-1) n 1 的时候，我们归纳证明其是难的。$n=2$ 显然是难的，因为交换不了。对于更大的 $n$，任意交换环上的两个元素会得到两个环，而之后必须要两个环都不是难的才能在 $n-1$ 次操作内排好序。但注意到交换了 $a_i=(i+1)$ 和 $a_j$ 之后，$a_{i+1} \sim a_j$ 就是 $i+2\ i+3\ \cdots\ j\ i+1$ 恰好构成一个长度为 $j-i \ge 2$ 的由归纳假设是难的环。所以第一步怎么做最后都会有一个难的环，所以这个环也是难的。

对于不难的环我们直接排到对应位置，对于难的环我们不能直接排好，需要用一些额外的操作来搞定。因为一次把两个环合并成一个，会导致总步数+2，同时最多删掉两个难环，因此答案下界是 $n$ 减环数加上（难环数量除 2 上取整乘二）。

这个下界是容易达到的：先把所有难环都弄成二元环，简单环排好，然后对于 2143，先交换 23 得到 3142，这个环不是难的，直接弄就行了。单独剩下一个 12 的情况，$n \ge 5$ 的时候总可以找到一个不相邻的位置，用三步操作归位。$n \le 4$ 的情况需要特判，小点全都暴力就行了。