DISCO Presents Discovery Channel Code Contest 2020 Qual 题解
A 就不写了。
B - Iron Bar Cutting
题意
有一个长度为 \(n\) 的序列 \(A_1,A_2,\ldots,A_n\)，每次操作你可以将某个数加 \(1\) 或减 \(1\)，求使得序列满足以下条件的最小操作次数：
- 存在一个 \(1\le i < n\)，满足 \(\sum\limits_{j=1}^{i}A_j=\sum\limits_{j=i+1}^{n}A_j\)。
\(n\le 2\times 10^5\)
题解
当固定 \(i\) 时，由于可以任意加减，最小操作次数显然是前面部分的和与后面部分的和的差的绝对值。对所有 \(i\) 取 \(\min\) 即可。
时间复杂度 \(O(n)\)。
C - Strawberry Cakes
题意
在 \(H\times W\) 的网格中有 \(K\) 个黑色格子，你需要构造一组将网格划分成 \(K\) 个矩形的方案，使得每个矩形内有恰好一个黑色格子。
\(H,W\le 300\)
题解
只有一行时构造非常简单。
当每行都有至少一个黑色格子时，每行独立按只有一行的方式构造即可。
当存在一些行没有黑色格子时，只要将上一行或下一行的构造延伸到这一行即可，显然仍然是矩形。
时间复杂度 \(O(HW)\)。
D - Digit Sum Replace
题意
有一个正整数 \(N\)，每次可以执行如下操作，直到 \(N\le 9\)：
- 在 \(N\) 的十进制表示中，选择相邻的两位，并将这两位替换成他们的和。
如 \(N=2378\)，则可以执行一次操作变成 \(578\)，\(2108\) 或 \(2315\)。
求最多可以执行多少次操作。
\(N\) 的给定方式为，给定两个序列 \(d_1,\ldots,d_M\) 和 \(c_1,\ldots,c_M\)，\(N\) 的十进制表示为 \(c_1\) 个 \(d_1\)，紧接着 \(c_2\) 个 \(d_2\)，以此类推，最后有 \(c_M\) 个 \(d_M\)。
\(M\le 2\times 10^5,\sum c_i\le 10^{15}\)
题解
注意到一次操作会导致 \(N\) 的位数 \(C\) 和每位上的和 \(S\) 有以下两种变化：
- \(C\) 减 \(1\)，\(S\) 不变；
- \(C\) 不变，\(S\) 减 \(9\)。
由于最终一定有 \(C=1,S\le 9\)，所以两种变化的数量是确定的，也即总操作次数是固定的，即 \(C-1+\lceil\frac{S}{9}\rceil-1\)。
E - Majority of Balls
题意
这是一个交互题。
有 \(2N\) 个球，编号 \(1,\ldots,2N\)，其中 \(N\) 是奇数。每个球的颜色为红色或蓝色，红球和蓝球各有 \(N\) 个。
你可以询问不超过 \(210\) 次确定每个球的颜色。每次可以询问一个大小为 \(N\) 的球的子集中，红球数量是否比蓝球数量更多。
\(N\le 99\)
题解
如果我们把红球看成 \(+1\)，蓝球看成 \(-1\)，每次相当于询问一个集合的和是否大于 \(0\)。
若 \(1,\ldots,N\) 的和大于 \(0\)，那么 \(N+1,\ldots,2N\) 的和一定小于 \(0\)。同理，若 \(1,\ldots,N\) 的和小于 \(0\)，那么 \(N+1,\ldots,2N\) 的和一定大于 \(0\)。
注意到从左往右扫描每个长度为 \(N\) 的区间时，和每次的变化只有 \(+2,0,-2\) 三种情况。那么中途一定会出现和从 \(+1\) 到 \(-1\) 的变化或从 \(-1\) 到 \(+1\) 的变化。此时我们就可以找到一个长度为 \(N-1\) 的，红蓝球数量相等的区间。
找到这样一个区间后，我们可以轻松地判断出每个不在该区间内球的颜色。而求出其余球的颜色后，我们又可以找到另一个大小为 \(N-1\) 的，不包含原区间内任意一个球的，红蓝球数量相等的集合，我们可以利用该集合确定原区间内每个球的颜色。
这样我们总共需要 \(3N\) 次询问，不能满足要求。
注意到对于第一部分，记 \(S_i\) 为 \([i,i+N)\) 这些球进行查询的结果，我们需要求出一个 \(0\le i < N\) 满足 \(S_i\ne S_{i+1}\)。
假设当前我们要在 \([L,R)\) 中找出一个 \(i\) 使得 \(S_i\ne S_{i+1}\)。考虑区间中点 \(M=\lfloor\frac{L+R+1}{2}\rfloor\)。若 \(S_M\ne S_L\)，那么我们可以将区间缩小到 \([L,M)\)；否则我们可以将区间缩小到 \([M,R)\)。
于是第一部分的查询数量就可以缩小到 \(\log_2 N\)，可以通过本题。
F - DISCOSMOS
题意
有一个 \(H\times W\) 的网格。在第 \(0\) 秒，你需要在每个格子上放一个机器人。机器人有三种：
- Type-H，始终不移动。
- Type-R，每一秒会向右移动，即从 \((x,y)\) 到 \((x,y+1)\)。特别地，若 \(y=W\)，则下一步到 \((x,1)\)。
- Type-D，每一秒会向左移动，即从 \((x,y)\) 到 \((x+1,y)\)。特别地，若 \(x=H\)，则下一步到 \((1,y)\)。
同一时刻某个格子上可以有多个机器人。
求有多少种放置机器人的方案，使得在时刻 \(0,T,2T,3T,\ldots\)（即所有 \(T\) 的倍数的时刻），每个格子上恰好有一个机器人。
\(H,W,T\le 10^9\)。
题解
首先我们可以令 \(n=\frac{H}{\gcd(H,T)},m=\frac{W}{\gcd(W,T)}\)，转化成 \(T=1\) 的情况，只要最后将答案 \(s\) 变为 \(s^{\frac{H}{n}\cdot\frac{W}{m}}\) 即可。
注意到有一些显然合法的情况：
- 选择若干行，这些行的每个格子都放 Type-R 的机器人。其余位置放 Type-H 的机器人。
- 选择若干列，这些列的每个格子都放 Type-D 的机器人。其余位置放 Type-H 的机器人。
这些情况有 \(2^n+2^m-1\) 种。接下来我们考虑同时有 Type-R 和 Type-D 的情况。
假设 \(n=m\)，下面的同余符号默认都在模 \(n\) 意义下同余。
对于所有 \(i+j\equiv k\) 的位置 \((i,j)\) 的机器人，移动一步后，一定只有这些机器人可以移动到 \(i+j\equiv k+1\) 的位置 \((i,j)\)。而这些位置上都只能有恰好一个机器人，所以 \(i+j\equiv k\) 的位置 \((i,j)\) 上的机器人必须都是 Type-R 或都是 Type-D 的。
所以除去全部相等的两种情况，共 \(2^n-2\) 种情况。
对于 \(n\ne m\) 的情况，可以类似说明所有 \(i+j\equiv k\pmod{\gcd(n,m)}\) 的位置必须都是同一类型且会移动的机器人。
综上，总方案数为 \(2^n+2^m+2^{\gcd(n,m)}-3\)。
时间复杂度 \(O(\log H+\log W+\log T)\)。
