AtCoder Grand Contest 037 题解
A - Dividing a String
题意
给定一个字符串 \(S\)，求最多可以把该字符串分成多少份，使得相邻两份不相同。
\(|S|\le 2\times 10^5\)
题解
显然每一份的长度一定不超过 \(2\)。直接 DP 即可。
B - RGB Balls
题意
有 \(3N\) 个球，编号 \(1\) 到 \(3N\)。每个球有红（R）、绿（G）、蓝（B）三种颜色，每种颜色的球恰好有 \(N\) 个。
你要将这些球分给 \(N\) 个人，每个人得到恰好一个红球、一个绿球、一个蓝球。令第 \(i\) 个人得到的球的编号按升序排列为 \(a_i,b_i,c_i\)，则分配方案需要最小化 \[\sum_{i=1}^{N} (c_i-a_i)\]
求使得上式最小的分配方案数，对 \(998244353\) 取模。两种方案不同当且仅当存在某个人分到的球的集合不同。
题解
有一种贪心是，从左往右依次扫描每个球，记录单个的，两个的，以及三个球都配好的数量。那么加入一个球时，优先与已经有两个球的对配成三个球；若不行，再尝试与单个的球配成两个球；若仍然不行，则单独成为一个球。
可以通过调整证明这样贪心得到的方案一定恰好能覆盖所有最小的方案。
于是直接用乘法原理计算答案即可。
C - Numbers on a Circle
题意
环上有 \(N\) 个正整数 \(A_i\)，你可以执行若干次以下操作：
- 选择环上的一个数，将该数加上与它相邻的两个数。
你的目标是使得 \(A_i=B_i\)。求最少操作次数，或输出无解。
\(N\le 2\times 10^5\)
题解
考虑倒着做，假设所有数中最大的为 \(x\)。那么在操作 \(x\) 之前不可能操作与 \(x\) 相邻的两个数，所以我们一定会先操作 \(x\)。
于是只要用堆模拟即可，因为每次相当于会对最大值取模，所以复杂度是 \(O(N\log N\log A_i)\) 的。
D - Sorting a Grid
题意
给定一个 \(N\times M\) 的矩阵，第 \(i\) 行第 \(j\) 列的数为 \(A_{i,j}\)。矩阵满足 \(1\) 到 \(NM\) 的每个数恰好出现一次。你需要按顺序执行以下操作：
- 对于矩阵 \(A\) 的每一行，重新排列该行的元素得到矩阵 \(B\)；
- 对于矩阵 \(B\) 的每一列，重新排列该列的元素得到矩阵 \(C\)；
- 对于矩阵 \(C\) 的每一行，重新排列该行的元素得到矩阵 \(D\)。
你的目标是使矩阵 \(D\) 第 \(i\) 行第 \(j\) 列的数为 \((i-1)M+j\)。
构造一种方案。可以证明一定有解。
\(N,M\le 100\)
题解
对于矩阵 \(C\)，我们可以将每个数替换成最终矩阵中的行号，\(C\) 的每一列需要满足恰好是 \(1\) 到 \(N\)。
那么对于矩阵 \(B\)，每一列需要恰好是 \(1\) 到 \(N\) 的一个排列。
于是我们考虑从左到右填 \(B\) 的每一列。这可以直接跑二分图匹配。
我们可以用数学归纳法，根据霍尔定理证明一定有解。
时间复杂度 \(O(MN^3)\)。
E - Reversing and Concatenating
题意
给定一个长度为 \(N\) 的字符串 \(S\)，你需要执行以下操作 \(K\) 次：
- 令 \(T\) 为 \(S\) 翻转后的串，令 \(U\) 为 \(S\) 与 \(T\) 按顺序拼接得到的串。
- 将 \(S\) 替换为 \(U\) 的一个长度为 \(N\) 的子串。
求最后得到的字典序最小的 \(S\)。
\(N\le 5000,K\le 10^9\)
题解
因为需要字典序最小，所以我们会尽量使最小的字符在开头的出现次数最多。
假设最小的字符为 \(a\)，假设初始字符串有一段长度为 \(l\) 的字符 \(a\)。那么我们可以执行以下若干次操作：
- \(\ldots aaa\ldots\to \ldots aaa\boxed{\ldots\ldots aaa}\ldots\)
- \(\ldots\ldots aaa\to \ldots\boxed{\ldots aaaaaa}\ldots\ldots\)
- \(\ldots aaaaaa\to \ldots aaaaaaaaaaaa\ldots\)
- \(\ldots\)
使得最后得到的字符串最前面有 \(l\times 2^{k-1}\) 个 \(a\)。
通过手动模拟可以得到后面部分一定是初始字符串中从这一段 \(a\) 的下一个字符开始，到末尾，再从末尾返回得到的字符串。
于是我们枚举每一段最长的 \(a\) 后暴力求出最后的字符串，暴力比较即可。
时间复杂度 \(O(N^2)\)。
F - Counting of Subarrays
题意
定义一个序列 \(S\) 是属于 level \((k,l)\) 的当且仅当满足以下条件之一：
- \(S\) 的长度为 \(1\) 且元素为 \(k\)；
- \(k>1\) 且存在属于 level \((k,l-1)\) 的序列 \(T_1,T_2,\ldots,T_m\ (m\ge l)\) 满足 \(T_1,T_2,\ldots,T_m\) 按顺序拼接得到 \(S\)。
给定整数 \(L\) 和一个序列 \(A_1,A_2,\ldots,A_N\)，求 \(A\) 有多少个连续子序列满足，存在一个 \(K\) 使得该序列是属于 level \((K,L)\) 的。
\(N\le 2\times 10^5\)
题解
一个序列 \(a_1,a_2,\ldots, a_n\) 合法当且仅当满足以下条件之一：
- \(n=1\)
- 令 \(x\) 为该序列的最小值，对于所有 \(a_i=x\) 的极长连续段，假设长度为 \(l_1,l_2,\ldots,l_m\)，都有 \(l_i\ge L\)，且将第 \(i\) 段连续段替换成 \(\lfloor\frac{l_i}{L}\rfloor\) 个 \(x+1\)，得到一个新的序列 \(b_1,b_2,\ldots,b_k\)，有 \(b\) 序列合法。
考虑将原序列不断地按上述过程进行变换，则原序列的一个区间对应新序列的一个区间，而新序列的一个区间对应原序列的若干个区间。
考虑在变换过程中维护 \(L_i\)，表示原序列中有多少个左端点对应到新序列中为 \(i\)，\(R_i\) 同理。
我们只要在变换时维护答案即可，注意计入答案的区间必须满足区间中包含至少一个不是通过收缩得到的点。
用链表和堆模拟变换过程，时间复杂度 \(O(N\log N)\)。
