AtCoder Grand Contest 041 题解
A - Table Tennis Training
题意
有 \(n\) 张桌子，编号 \(1\) 到 \(n\)，有两个人，一个在桌子 \(A\)，另一个在桌子 \(B\)。
每一个人每次可以向左或向右移动，但不能不动。特别地，如果在桌子 \(1\)，向左移动则仍留在桌子 \(1\)；如果在桌子 \(n\)，向右移动则仍留在桌子 \(n\)。
问最少多少次两个人可以移动到同一张桌子。
\(n\le 10^{18}\)
题解
分两种情况：
- \(A\) 与 \(B\) 奇偶性相同。此时每个人往另一个人的方向移动即可。
- \(A\) 与 \(B\) 奇偶性不同。又分两种情况：
- 两个人同时向 \(1\) 移动，当左边的人移动到 \(1\) 时，在 \(1\) 停留一次，然后向右移动；右边的人则保持向左移动。
- 两个人同时向 \(n\) 移动，情况同理。
B - Voting Judges
题意
有 \(N\) 个数 \(A_i\)，执行恰好 \(M\) 次操作，每次操作选择恰好 \(V\) 个数加 \(1\)。然后降序排列，有相同时顺序任意。
求有多少个数有可能能进入最终的前 \(P\) 个。
\(N\le 10^5,M\le 10^9\)
题解
将 \(A_i\) 从大到小排序。前 \(P\) 个显然可以，考虑对于 \(P < i \le N\) 判断是否可以进入前 \(P\) 个。
首先每次加 \(1\) 的数中，前 \(P-1\) 个一定选，\(i\) 和 \(i\) 之后的数也一定选，但是此时可能仍然不足 \(V\) 个数。
此时我们每次需要选择一些中间的数补足 \(V\) 个。假设还需要 \(R\) 个数，则充要条件是 \[\sum_{j=P}^{i-1}(A_i+M-A_j)\le MR\]
必要性显然，充分性可以通过每次选最小的 \(R\) 个数证明。
时间复杂度瓶颈在于排序。
C - Domino Quality
题意
在 \(N\times N\) 的网格中放一些多米诺骨牌。至少放一个骨牌，每个格子最多只能被一个骨牌覆盖，可以不被覆盖。对于网格的每一行，定义质量为覆盖该行中至少一个格子的骨牌数量。列同理。
构造一组方案使得所有行、列的质量相等。
\(N\le 1000\)
题解
发现 \(N=4,5,6,7\) 时都可以构造出行列质量为 \(3\) 的方案。于是我们在对角线上铺上这些方案即可。
\(N=3\) 的时候可以构造出质量为 \(1\) 的方案，需要特判。
D - Problem Scores
题意
求满足以下条件的长度为 \(N\) 的序列 \(A\) 的数量：
- \(1\le A_1\le A_2\le A_3\le \ldots \le A_N\le N\)
- 对于所有 \(1\le k < N\)，都满足序列 \(A\) 的任意一个大小为 \(k\) 的子集和严格小于任意一个大小为 \(k+1\) 的子集和。
对 \(M\) 取模。
\(N\le 5000,9\times 10^8 < M < 10^9\)，\(M\) 是质数。
题解
显然只要 \(k=\lfloor\frac{n-1}{2}\rfloor\) 时满足条件即可。
令 \(t=\sum\limits_{i=1}^{k+1} A_i-\sum\limits_{i=n-k+1}^{n}A_i\)，即我们需要满足 \(t>0\)。
于是考虑将原序列差分，设为 \(x_1,x_2,\ldots,x_n\)，那么对 \(t\) 的贡献分别为 \[w=\{1,0,-1,-2,-3,\ldots,-3,-2,-1\}\]
令 \(A=\sum\limits_{i=2}^{n}x_i,B=-\sum\limits_{i=2}^{n}w_ix_i\)，则 \(B+1\le x_1\le n-A\)，即贡献为 \(n-A-B\)。
于是我们只要考虑 DP \(A+B=d\) 的方案数。完全背包即可。
时间复杂度 \(O(n^2)\)。
E - Balancing Network
题意
一个网络中有水平的 \(n\) 根导线，以及 \(m\) 个竖直的平衡器。平衡器从左往右依次编号 \(1\) 到 \(m\)。第 \(i\) 个平衡器连接导线 \(x_i\) 和 \(y_i\)，其中 \(x_i < y_i\)。
你可以为每个平衡器确定一个方向，向上或向下。
有一个点从某根导线，所有平衡器左边的某一位置开始，向右运动，当经过第 \(i\) 个平衡器时：
- 若该点在导线 \(x_i\) 且平衡器向下，则移动到导线 \(y_i\) 的对应位置，继续向右运动。
- 若该点在导线 \(y_i\) 且平衡器向上，则移动到导线 \(x_i\) 的对应位置，继续向右运动。
- 否则保持向右运动。
若从任意导线出发，最终都能到达同一根导线的无穷远处，则称该网络是均衡的，否则是不均衡的。
给定参数 \(T\)，若 \(T=1\) 你需要构造一个均衡的网络，\(T=2\) 你需要构造一个不均衡的网络。
\(n\le 5\times 10^4,m\le 10^5,T\in \{1,2\}\)
题解
对于 \(T=1\) 的情况，假设我们已经确定终点 \(w\)，我们从后往前依次加入平衡器，同时维护 \(A_i\) 表示第 \(i\) 个点是否可以到达终点 \(w\)。初始时 \(A_w=1\)。
对于当前的平衡器 \((x,y)\)，分四种情况：
- \(A_x=1,A_y=1\)，此时平衡器如何定向都不会改变状态。
- \(A_x=0,A_y=0\)，同理不会改变状态。
- \(A_x=0,A_y=1\)，此时将平衡器方向定为 \(x\to y\) 可以使得 \(A_x=1\)。
- \(A_x=1,A_y=0\)，同理将平衡器方向定为 \(y\to x\) 可以使得 \(A_y=1\)。
发现这是一个将 \(A_x,A_y\) 都置为原来 \(A_x,A_y\) 的二进制或值的过程。
于是我们可以用 bitset 优化。时间复杂度 \(O(\frac{nm}{w})\)。
对于 \(T=2\) 的情况，显然 \(n\le 2\) 一定无解，否则可以通过构造证明一定有解。
仍然考虑从后往前考虑每个平衡器的方向。
记录 \(P_x\) 表示起点为 \(x\) 时的终点，\(S_x\) 表示终点为 \(x\) 的起点数量。我们可以保证任意时刻 \(S_x < n\)。
对于当前平衡器 \((x,y)\)，若 \(S_{P_x}=n-1\)，那么如果此时将平衡器定向为 \(y\to x\)，会导致 \(S_{P_x}=n\)。但是因为有 \(\sum S_i=n\)，所以此时有 \(S_{P_y}\le 1 < n-1\)，于是定向为 \(x\to y\) 即可。\(S_{P_y}=n-1\) 同理。
时间复杂度 \(O(n+m)\)。
F - Histogram Rooks
题意
有一个 \(n\) 列的棋盘，第 \(i\) 列从底向上有 \(h_i\) 个格子。
你可以在棋盘上放一些车，使得对于棋盘上每个格子都能被某个车覆盖到。
一个车可以覆盖某个格子当且仅当它们在同一行或同一列，且中间的格子都存在。
求放置车的方案数。对 \(998244353\) 取模。
\(1\le h_i\le N\le 400\)
题解
一个朴素的容斥是，我们可以求出钦定 \(k\) 个位置不被车覆盖，其他位置没有限制的方案数，乘上容斥系数 \((-1)^k\) 即为对答案的贡献。
考虑建出笛卡尔树后 DP。用 \(f_{u,i}\) 表示 \(u\) 表示的列区间中，有 \(i\) 列中有钦定不覆盖的位置时，对答案的贡献（即容斥系数乘方案数之和）。
转移时，先可以考虑第 \(u\) 列是否有钦定不覆盖的位置将左右子树合并，然后我们在底部加入若干行。当加入一行时，假设 \(u\) 表示的列区间长度为 \(L\)，则转移分两种情况：
- 当前行中没有格子被钦定。此时该行中可以任意放车而不会有影响，方案数为 \(2^{L-i}\)，容斥系数为 \(1\)。
- 当前行中有格子被钦定。此时该行中一定不能放车，且被钦定的格子一定是那 \(i\) 列的一个子集，所以方案数为 \(1\)，容斥系数为 \(\sum\limits_{k=1}^{i} (-1)^k\begin{pmatrix}i\\k\end{pmatrix}=-[i\ne 0]\)。
然而，这样的 DP 状态设计和转移有一个问题，我们并不能保证这 \(i\) 列每一列都有被钦定的位置。
这仍然可以通过容斥解决。考虑加入一维 \(j\) 表示 \(i\) 列中有 \(j\) 列不存在被钦定的位置。DP 的转移第一种不变，第二种变为选择其余 \(i-j\) 列的一个子集，容斥系数变为 \(-[i\ne j]\)。
注意到其实我们只需要在 DP 状态中记录 \(j\) 是否等于 \(i\)，并将容斥系数 \((-1)^j\) 压入 DP 值中，而不需要记录 \(j\) 的具体数值。
时间复杂度 \(O(N^2)\)。
