- 搬题人：
- 一维围棋：Wu_Ren
- 斜二等轴测图：Wu_Ren
- 盒子里的糖果：hehezhou
- 冲塔：p_b_p_b
- 波特分组：feecle6418
- 别急：Y25t
- 组题人：p_b_p_b
- 验题人：syzf2222, Zeardoe, Dualqwq, yllcm
- 题解：hehezhou, Wu_Ren, p_b_p_b, Y25t
一维围棋 (Div. 2 Only)
来源：
- ACM-ICPC Japan Alumni Group Summer Camp 2019. Problem A, AiGo
- Petrozavodsk Summer 2020. Day 5: JAG Summer+ Opening Contest. Problem A, AiGo
QOJ 链接：https://qoj.ac/problem/1335
tutorial by Wu_Ren
枚举哪个位置去放棋子，首先如果上面已经有棋子就不能放，然后向左向右如果都是连续一段白再接一段黑，那么也不能放，否则一定能放。放了之后向左向右分别扫一遍即可知道占领了多少黑棋。
复杂度 $O(n)$ 或 $O(n^2)$。
斜二等轴测图 (Div. 1 + Div. 2)
来源：
- 2018 Multi-University Training Contest 3. Problem B, Visual Cube
- Petrozavodsk Summer 2020. Day 3: Songyang Chen Contest 3. Problem B, Visual Cube
QOJ 链接：https://qoj.ac/problem/1266
tutorial by Wu_Ren
按照题意模拟即可，复杂度 $O(T(a+b)(b+c))$。
盒子里的糖果 (Div. 2 Only)
来源：
- Petrozavodsk Summer 2021. Day 4: Shanghai ICPC Camp 2021 Onsite Day 1 by PKU. Problem F, Interval Shuffle
QOJ 链接：https://qoj.ac/problem/1848
tutorial by hehezhou
算法一
令 $dp_{i,j}$ 表示 $i$ 次操作后，$a_j$ 的最大值。
那么有： $$\begin{cases}dp_{i,j}=dp_{i-1,j}&j\in[1,l_i)\bigcup(r_i,n]\\ dp_{i,j}=\max(dp_{i-1,j}+1,\max_{k\in [l_i,r_i]}dp_{i-1,k})&j\in[l_i,r_i]\end{cases}$$
即只需考虑 $i-1$ 步时的最大值即可推出 $i$ 步后的最大值。构造某位的最大值只需按照 dp 转移式逆推即可。
时间复杂度 $O(n^2)$。
算法二
考虑用线段树优化上述过程：
- 计算 $\max_{k\in [l_i,r_i]}dp_{k}$ 即为一次查询区间最大值。
- 更新 $dp$ 值可以表示为一次区间加和一次区间取 $\max$。
这是一个经典线段树问题，可以在 $O(n\log n)$ 的时间复杂度内解决。
冲塔 (Div. 1 + Div. 2)
来源：
- National Olympiad in Informatics 2022. Problem 3, Towers
QOJ 链接：https://qoj.ac/problem/3873
tutorial by p_b_p_b
先不管“每列只能冲至多两个塔”的限制，直接先把每行最左和最右的塔都冲掉。
这时候当然可能会出现某一列超过两个塔了。但是往好处想：如果超过两个塔，是不是说明中间那个塔就不需要冲了呢？
因此可以每次找到最靠右的一列，使得这一列有超过两个塔，然后把中间的那些塔全都往左移动一位。
不难发现每次这样操作之后仍然满足每个塔都被覆盖，并且 $O(n)$ 次操作之后就不会存在冲了超过两个塔的列了。
用 set 维护，复杂度 $O(n\log n)$ 。
波特分组 (Div. 1 Only)
来源：
- Petrozavodsk Winter 2020. Day 7: Gennady Korotkevich Contest 5. Problem F, Flip
- XX Open Cup named after E.V. Pankratiev, Grand Prix of Gomel. Problem F, Flip
QOJ 链接：https://qoj.ac/problem/1427
tutorial by feecle6418
设 $S=\sum k$。
算法一
直接枚举每枚硬币哪面朝上，时间复杂度 $O(q2^{2n})$，可以通过第一个子任务，期望得分 $9$。
算法二
考虑先枚举每一种情况，用子集和变换预处理每种输入哪些会有贡献，时间复杂度 $O(2^{2n}n+S)$，可以通过前两个子任务，期望得分 $25$。
此外，可能存在一些高复杂度算法，可以通过前三个子任务。
算法三
首先，给定一种分组状态，它出现的概率是多少？设最后一个分到 A 组的人编号为 $i_A$，最后一个分到 B 组的人编号为 $i_B$，则概率为 $2^{-\min(i_A,i_B)}$。
对于每组询问，不妨假设全分在 A 组，枚举 $\min(i_A,i_B)=p$ 的值，计算分组方案数：
- $p=b_k$，此时分组方案数为 $\binom{b_k-k}{n-k}$。
- $p$ 位置分在 B 组，不妨设 $b_i < p < b_{i+1}$，则分组方案数为 $\binom{p-i-1}{n-1}$。对于固定的 $i$，$p-i-1$ 构成区间，恰当预处理前缀和可以 $O(1)$ 求出。
- $p>b_k$ 且 $p$ 位置在 A 组，则分组方案数为 $\binom{p-k-1}{n-k-1}$。对于每种出现的 $k$，分别 $O(n)$ 预处理该式与概率的乘积的后缀和即可。
因为不同的 $k$ 只有 $\sqrt S$ 个，所以时间复杂度 $O(n\sqrt S+S)$，期望得分 $100$。注意边界。
本题也存在线性做法。
别急 (Div. 1 Only)
来源：
- XXII Open All-Siberian Programming Contest named after I.V. Pottosin Final tour, II day. Problem 11: Captivating process
- XXII Open Cup named after E.V. Pankratiev, Grand Prix of Siberia. Problem 11: Captivating process
QOJ 链接：https://qoj.ac/problem/4758
tutorial by Y25t
建两张有向图 $F,G$，对所有 $1\le i\le n$ 在 $F$ 中连有向边 $(i,f_i)$，在 $G$ 中连边 $(i,g_i)$。那么它们分别形成基环内向森林。
对于一个点 $u$ ，若它能沿着 $F$（或 $G$）中唯一出边走若干步能回到 $u$，则称它为 $F$（或 $G$）中的环点，否则称它为 $F$（或 $G$）中的树点。定义 $dep^F_u$ 为在 $F$ 中 $u$ 第一次走到环点所需步数。若 $u$ 在 $F$ 中是环点，则 $dep^F_u=0$，同时定义 $l^F_u$ 为 $u$ 所在环的长度，$d^F_u$ 为 $u$ 在其所在环上的编号（满足 $0\le d^F_u< l^F_u$ 且 $d^F_{f_u}\equiv d^F_{u}+1\pmod{l^F_u}$）。类似地定义 $dep^G,l^G,d^G$。
对于一块石板 $(x,y)$，不妨设 $dep^F_x\le dep^G_y$。考虑将时间分为 $[0,dep^F_x),[dep^F_x,dep^G_y),[dep^G_y,+\infty)$ 三段，分别判断是否会裂开。
$[0,dep^F_x)$
在这段时间里，$x$ 为在 $F$ 中的树点，$y$ 为在 $G$ 中的树点。
该石板会在这段时间中裂开，当且仅当存在点 $u$ 使得以下三个条件同时满足：
- $dep^F_x-dep^F_u=dep^G_y-dep^G_u$，即 $dep^F_u-dep^G_u=dep^F_x-dep^G_y$。
- 在 $F$ 中 $u$ 是树点，且为 $x$ 的祖先。
- 在 $G$ 中 $u$ 是树点，且为 $y$ 的祖先。
于是将询问离线后在 $G$ 的树部分进行 dfs。用 std::set 或动态开点线段树维护 $2n$ 个线段集合 $S_i(-n\le i\le n)$。在进入一个点 $u$ 时，在 $S_{dep^F_u-dep^G_u}$ 中插入线段 $[dfn^F_u,dfn^F_u+sz^F_u-1]$（其中 $dfn^F,sz^F$ 为在 $F$ 中的 dfs 序和子树大小），回溯时撤销。对于询问 $(x,y)$，在进入 $y$ 后判断 $S_{dep^F_x-dep^G_y}$ 中是否有线段覆盖了 $dfn^F_x$ 即可。
该算法加一些简单特判后可通过子任务 7。
$[dep^F_x,dep^G_y)$
在这段时间里，$x$ 为在 $F$ 中的环点，$y$ 为在 $G$ 中的树点。
该石板会在这段时间中裂开，当且仅当存在点 $u$ 使得以下三个条件同时满足：
- $d^F_u-d^F_x\equiv dep^G_y-dep^G_u\pmod{l^F_u}$ 即 $d^F_u+dep^G_u\equiv d^F_x+dep^G_y\pmod{l^F_u}$。
- 在 $F$ 中 $u$ 是环点，且与 $x$ 在同一环中。
- 在 $G$ 中 $u$ 是树点，且为 $y$ 的祖先。
于是可以用类似的 dfs 进行求解。
该算法加一些简单特判后可通过子任务 6。
$[dep^G_y,+\infty)$
在这段时间里，$x$ 为在 $F$ 中的环点，$y$ 为在 $G$ 中的环点。
该石板会在这段时间中裂开，当且仅当存在点 $u$ 使得以下三个条件同时满足：
- $d^F_u-d^F_x\equiv d^G_u-d^G_y\pmod{\gcd(l^F_u,l^G_u)}$
- 在 $F$ 中 $u$ 是环点，且与 $x$ 在同一环中。
- 在 $G$ 中 $u$ 是环点，且与 $y$ 在同一环中。
用 std::set 维护三元组即可简单判断。
该算法可直接通过子任务 5。
结合以上三个算法即可通过本题。
