ARC 补题目录

所有题目均已 AC，部分题目待补题解。
我：去你的哪来的时间补题解。

$\color{blue}{hack}$：赛时过了，赛后被 hack。
$\color{red}{sol}$：AC 但是没写题解。

讲评题目（ARC）$(45/45)$

讲评题目题解落实情况 $(38/45)$

Day1

• AT_arc133_b [ARC133B] Dividing Subsequence
  • 注意给定的是排列，需要满足 $a_i | b_i$（$a_i$ 是 $b_i$ 的因数）。
  • 由于是排列，显然可以处理出所有形如 $(y, x)$ 的数对，满足 $a_x | a_y$，显然有 $n \log n$ 个这样的数对，$(y, x)$ 表示 $b_y$ 可以匹配 $a_x$。
  • 然后发现，每一个 $b_y$ 只能匹配一个 $a_x$！因此，对所有二元组第一维升序，第二维降序，再对第二维做一次 LIS，即可得到答案。
  • 注意：LIS 需要用优化版本。
• AT_arc133_c [ARC133C] Row Column Sums
  • 判定无解：每行之和与每列之和 $\bmod k$ 不一样。因为整个网格的和是一定的。
  • 考虑对行和列分别计算，答案取 $\max$。
  • 以行为例，假设所有点都填 $k-1$，再计算需要减去多少使 $\mod k$ 之后满足条件。
• AT_arc133_d [ARC133D] Range XOR
  • 前缀和转化后，数位 DP。
  • 详解版。
• AT_arc133_e [ARC133E] Cyclic Medians
  • 我写不动。
  • @zrzzrz の $\Large\color{red}{题解}$。

Day2

• AT_arc134_b [ARC134B] Reserve or Reverse
  • 对于每一个字符，记录它出现的位置。
  • 考虑使用双指针，每次找到当前区间内最小的字符，将右指针移动到该点并交换。
• AT_arc134_c [ARC134C] The Majority
  • 采取“一对一”战略，对于 $2 \dots n$ 中的每一个颜色的球，选一个 $1$ 号球与之匹配。
  • 接着在每一个盒子里放一个 $1$ 号球，还剩下 $( \sum\limits_{i=2}^{n} a_i ) - a_1 - k$ 个 $1$ 号球。
  • 接着所有球都可以随便放了，根据 【组合数学】盒球问题详解 答案即为 $\prod_{i=1}^{n} C_{a_i + k - 1}^{k - 1}$。
• AT_arc134_d [ARC134D] Concatenate Subsequences
  • 构造题，线段树优化。
  • 详解
• AT_arc134_e [ARC134E] Modulo Nim
  • 题单中最难的一道题。
  • 博弈论配合状压 DP。
  • 详解版

Day3

• AT_arc135_b [ARC135B] Sum of Three Terms
  • 发现答案是有周期性的：$a_i + x, a_{i+1} + y,a_{i+2} - x - y$，每一项要加上一些偏移量系数。
  • 考虑让 $a_1, a_2, a_3$ 取最小值，如果它们之和 $\gt S_1$，则显然无解。否则可以让 $a_3$ 加上这个差值。
  • 接下来递推即可。
• AT_arc135_c [ARC135C] XOR to All
  • 诈骗题。结论是只会操作一次。
  • 设第一次选取 $a_j$，则经过一次操作变为：$b_i = a_i \oplus a_j$。
  • 设第二次选取 $b_k$，则经过两次操作变为：$c_i = b_i \oplus b_k = (a_i \oplus a_j) \oplus (a_k \oplus a_j) = a_i \oplus a_k$。
  • 即操作两次等价于第一次直接选取 $a_k$ 进行操作。
  • 只操作一次，接下来就是板子了，可以直接做。
• AT_arc135_d [ARC135D] Add to Square
  • 待补题解。
• AT_arc136_d [ARC136D] Without Carry
  • 先考虑值域 $[0,9]$ 怎么做。
  • 观察到 $x$ 和 $y \leq 9 - x$ 是不会产生进位的，这样的 $y$ 显然可以开一个桶维护。
  • 但如果 $x \leq 4$，就会出现 $x \leq 9 - x$ 的情况，这种贡献要减掉。
  • 再考虑值域更大的情况，显然是高维前缀和，二进制版本变成十进制，维护的方法是一样的。

Day4

• AT_arc136_b [ARC136B] Triple Shift
  • 首先，出现的数不一样肯定无解。
  • 手玩小数据发现，操作后的逆序对奇偶性不会变化。
  • 并且只要 $A$ 中有重复元素，就一定有解。
  • 因此只要判定逆序对奇偶性即可。
• AT_arc136_c [ARC136C] Circular Addition
  • 结论：记 $x = \max\limits_{i=1}^{n} a_i$，$y = \frac{\sum\limits_{i=1}^{n} a_{(i \bmod n) + 1}}{2}$，则答案为 $\max(x, y)$
  • 证明：分类讨论 $x,y$ 的大小关系，并考虑把它们转移到 $x=y$ 的情况，然后会发现 $x=y$ 时候一定可以让 $x,y$ 同时 $-1$，问题得到解决。
• AT_arc137_b [ARC137B] Count 1's
  • 显然在一个区间内，方案数是“连续的”，即只要能操作后让 $1$ 的个数变为 $l$ 或 $r$（$l \leq r$），那么就一定可以变成 $[l,r]$ 中的任何一个数。
  • 贪心地做，就是每个区间取 $[Min, Max]$，方案数就是 $Max - Min + 1$。
  • 那么记前缀和，实时更新就好了。
• AT_arc137_c [ARC137C] Distinct Numbers
  • 博弈论，考虑分类讨论。
  • 若 $a_{n-1} + 1 < a_{n}$，则：
    • 若后手必败，则先手必胜。
    • 若后手存在一种方法必胜，则先手一定可以反悔，代替后手的移动方法，使得后手必败。
    • 因此先手必胜。
  • 若 $a_{n-1} + 1 = a_{n}$，则：
    • 由上一种情况，先手要保证每次操作后，最后两个棋子之间都没有间隙，否则就让后手必胜了。
    • 那么每一次都会“贴着”棋子走，到达最后一个空位，容易算出需要的步数为 $a_{n} - (n - 1)$。
    • 由于是轮流操作，只要判定这个步数的奇偶性就好了。
• AT_arc181_d [ARC181D] Prefix Bubble Sort
  • 详解版点此处。
  • 简述：观察每一轮排序后的答案变化情况，对每个数分开计算贡献。
  • 会发现每个数对答案的贡献是区间 +1 的形式，可以差分解决。

Day5

• AT_arc138_b [ARC138B] 01 Generation
  • 考虑双指针，倒着模拟即可。
  • 只需要每次判定是否末尾都是 $0$，前面也是 $0$。
  • 特判长度为 $1$ 的情况，或者写 $l \leq r$，不然会 WA on test #2。
• AT_arc138_c [ARC138C] Rotate and Play Game
  • 发现先手一定会取走最大的 $\frac{n}{2}$ 个数，由此解决第二问。
  • 考虑如何循环移位解决第一问：
  • 把要取走的数标记为 $-1$，留给对方的数标记为 $1$，可以根据前缀和画出一条折线图。
  • 要满足条件，就要使得这条折线不经过 $x$ 轴之下。
  • 那就好做了，把转化后的数组复制一遍，直接用滑动窗口单调队列、ST 表或者线段树都可以维护区间最小值。
• AT_arc139_b [ARC139B] Make N
  • 贪心，考虑根号分治。
  • 详解版。
• AT_arc139_d [ARC139D] Priority Queue 2
  • 这类期望题可以巧妙地拆贡献，即“横向计算矩形面积”变成“纵向计算”，改变计算角度。
  • 枚举 $t$，并计算每个数在最终数列出现的期望之和。
  • 设 $k$ 次操作中有 $j$ 次操作插入了 $\geq t$ 的数。
  • 设原本数列中有 $cnt$ 个数 $\geq t$，则可以分情况讨论：
    • $n - x + 1 \gt cnt$，每次多插入一个 $\geq t$ 让 $cnt+1$，上界是 $n - x + 1$，因此 $cnt’=\min(n-x+1,cnt+j)$。
    • $n - x + 1 \leq cnt$，每次插入 $\lt t$ 让 $cnt-1$，下界也是 $n - x + 1$，因此 $cnt’=\max(n-x+1,cnt-(k-j))$。
  • 对每个 $(t,j)$ 计算贡献。
• AT_arc140_c [ARC140C] ABS Permutation (LIS ver.)
  • 挺水的，贪心策略一定是跳到中间然后左右反复横跳。
  • 特判一下开头是中位数就可以过了。

Day6

• AT_arc140_b [ARC140B] Shorten ARC
  • 显然，只要操作一次 ARC -> AC，就不能再操作这一区间（因为没有 R 了）。
  • 那么记录只使用操作 1，最多能操作多少次，可以直接模拟之后的操作情况。
• AT_arc140_d [ARC140D] One to One
  • 一道非常幽默的计数题。
  • 需要观察性质然后再 DP 转移。
  • 详解版。
• AT_arc141_a [ARC141A] Periodic Number
  • 枚举前缀作为循环节。
  • 若当前前缀构成的数大于该数，则取 前缀 $-1$ 作为新的循环节再试一次。
  • 答案就是所有前缀构成的数的最大值。记得判定形如 $99 \dots 99$ 的数。
• AT_arc141_b [ARC141B] Increasing Prefix XOR
  • 发现性质：若 $2^n \gt m$ 则显然无解。
  • 观察到 $a,b$ 都要单调递增，所以最高位每次 $+1$。
  • 设 $f_i$ 表示序列长度为 $i$ 的答案，则 $f_i = \sum\limits_{j=1}^{i + 1} f_{j - 1} \times (\min(2^{i}, m) - 2^{i-1})$。
  • 答案即 $f_{n}$。
• AT_arc178_c [ARC178C] Sum of Abs 2
  • 待补题解。

Day7

• AT_arc132_b [ARC132B] Shift and Reverse
  • 分类讨论：
    1. 只用循环移位，所需步数 $n - a_1 + 1$。
    2. 循环移位并翻转一次，所需步数 $a_1 + 1$。
  • 取最小值即可。
• AT_arc132_c [ARC132C] Almost Sorted
  • 观察到 $d$ 非常小，考虑用状压 DP 解决这题。
  • 令 $S$ 表示 $[i-d, i+d]$ 之间数字的使用状态。
  • $f_{i,S}$ 表示前 $i$ 个数，使用状态是 $S$ 的方案数。
  • 转移方程详见代码。

    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for (int j = 0; j < (1 << 2 * m + 1); j++) {
            for (int k = -m; k <= m; k++) {
                if ((a[i] == -1 || a[i] == k + i) && (i + k <= n) && (i + k >= 1))
                    if (!((j >> (k + m)) & 1)) {
                        (f[i][(j | (1 << k + m)) >> 1] += f[i - 1][j]) %= mod;
                    }
            }
        }

• AT_arc132_d [ARC132D] Between Two Binary Strings
  • 待补题解。
• AT_arc132_e [ARC132E] Paw
  • 原本这题是紫的，被 shy 嘲讽说太简单了应该评绿。
  • 结果变成黑的惹。
  • 观察到最终状态显然满足：左边都是 <，右边都是 >，中间恰好一个区间不变。
  • 设 $f_i$ 表示第 $i$ 块左边都是 <，不影响到右边的概率。
  • 之前有 $i-1$ 个点，所以第一次操作有 $\frac{1}{2i - 2}$ 的概率会失败，即 $f_i = f_{i-1} \times (1 - \frac{1}{2i - 2})$。
  • 答案即枚举每个段，它保留的概率就是 $f_{左边} \times f_{右边}$，因为 < 和 > 本质相同。
  • 题目要求期望，乘权值即可。

Day8

• AT_arc131_b [ARC131B] Grid Repainting 4
  • 有五种颜色，一定不冲突，直接填。
• AT_arc131_c [ARC131C] Zero XOR
  • 显然，若先手可以通过一次操作获胜，则先手必胜。
  • 考虑 $n$ 为奇数的情况。
    • 若先手操作 $a_i$ 后，后手想要必胜，则一定要选择一个 $a_j$ 满足 $i \not= j$ 且 $a_i \oplus a_j = \oplus_{k=1}^{n} a_k$。
    • 显然由于 $a_i$ 互不相同，这种数对 $(i, j)$ 是两两配对的。
    • 因为 $n$ 是奇数，所以一定存在一个位置无法配对，因此**先手必胜。
  • 再考虑 $n$ 为偶数的情况。
    • 若先手无法一击必杀，则后手获得了 $n$ 为奇数的必胜局面，因此先手必败。
• AT_arc131_d [ARC131D] AtArcher
  • 待补题解。
• AT_arc131_e [ARC131E] Christmas Wreath
  • 一道很好的构造题。
  • 发现异色三元环的性质，找出构造方案，然后 DP。
  • 详解版。

Day9

• AT_arc182_a [ARC182A] Chmax Rush!
• AT_arc182_b [ARC182B] |{floor(A_i/2^k)}|
  • 最大化所有数二进制表示下不同前缀的个数。
  • 扔到 Trie 树上，每次取一个最大的没有被选过的子树的一个叶节点。
  • 模拟即可。
• AT_arc182_c [ARC182C] Sum of Number of Divisors of Product
  • 待补题解。
• AT_arc179_b [ARC179B] Between B and B
  • 独立做出的一道状压 DP。
  • 第一步观察到 $M$ 非常小，这正适合我们进行状压 DP。
  • 详解版通道。
• AT_arc142_c [ARC142C] Tree Queries
  • 这是一道交互题。没加 fflush(stdout); 开幕雷击，评测三分钟 TLE。
  • 由于询问次数限制在 $2n$ 以内，考虑求出 $1,2$ 号点到 $3 \dots n$ 中每个点的距离。
  • 则 $1,2$ 的距离就是 $\min\limits_{i=3}^{n} d_{1,i} + d_{2,i}$。
  • 可是还有一种情况：$1,2$ 相邻，距离为 $1$，此时算出来的答案应该是 $3$。
  • 我们会发现，只询问了 $2n - 4$ 次，还有 $4$ 次机会。
  • 我们选两个点 $a,b$，使得 $d_{1,a}+d_{2,a}=d_{1,b}+d_{2,b}=3$。
  • 若 $d_{a,b}$ 是 $1$，说明答案真的是 $3$，否则说明答案是 $1$。

Day10

• AT_arc129_c [ARC129C] Multiple of 7
  • 考虑长度为 $l$ 的形如 $77 \dots 77$ 的串，它有 $\frac{l (l + 1)}{2}$ 个子串是 $7$ 的倍数。
  • 那么把 $n$ 拆分成若干个这样的串，再把它们拼接在一起。
  • 但是无论你怎么拼接，只要中间插的数长度到达一定值，就一定有一个区间会多 $+1$。
  • 那么怎么办呢？你会发现要插入的数其实很少，但又没有少到可以暴力枚举。
  • 所以对每个要插入的数随机化！事实证明是可过的。
• AT_arc129_d [ARC129D] -1+2-1
  • 观察到操作后 $\sum a_i$ 不变，所以若 $\sum a_i \not= 0$ 则无解。
  • 记 $s_i = \sum\limits_{j=1}^{i} a_j$ ，手玩发现：$\sum s_i$ 的变化量始终是 $n$ 的倍数。
  • 由于最终状态 $s_i = 0$，所以只要 $\sum s_i$ 不是 $n$ 的倍数也无解。
  • 接下来每次操作相当于 $s_p - 1$，$s_{p+1} + 1$，并保证 $s_i$ 的前缀和 $\geq 0$，求最小操作次数。
• AT_arc130_b [ARC130B] Colorful Lines
  • 倒序之后处理，每个点就只会被覆盖一次。
  • 用 map 进行离散化，直接模拟即可。
• AT_arc130_c [ARC130C] Digit Sum Minimization
  • 转换方向，考虑让进位最多。
  • 最低位 $\geq 10$，接下来要有尽可能多的连续位 $\geq 9$，直接贪心然后枚举即可。
• AT_arc130_d [ARC130D] Zigzag Tree
  • 待补题解。