• 搬题人：
  • 一维围棋：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)$。

算法二

考虑用线段树优化上述过程：

1. 计算 $\max_{k\in [l_i,r_i]}dp_{k}$ 即为一次查询区间最大值。
2. 更新 $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。

结合以上三个算法即可通过本题。