Yahoo Programming Contest 2019 题解
ABC 就不写了。
D - Ears
题意
数轴上有 \(L\) 堆石头，第 \(i\) 堆石头在坐标 \(i-0.5\) 处，初始石子数量都为 \(0\)。
你可以从任意整数下标出发，每次向左或向右移动一个单位，并在经过一个石子堆时将该石子堆的石子数量加 \(1\)。你可以在任意位置结束移动。你不能移动到坐标小于 \(0\) 或大于 \(L\) 的位置。
给定 \(A_1,A_2,\ldots,A_L\)，假设最后第 \(i\) 堆石头数量为 \(x_i\)，你需要最小化 \[\sum_{i=1}^{L} |A_i-x_i|\]
\(L\le 2\times 10^5\)
题解
最后的 \(x\) 一定形如 \(\{0,\ldots,0,2,\ldots,2,1,\ldots,1,2,\ldots,2,0,\ldots,0\}\)，其中 \(2\) 和 \(1\) 分别可以替换成任意大于 \(0\) 的偶数和奇数（不同位置可以不同）。
于是直接 DP 即可。
时间复杂度 \(O(L)\)。
E - Odd Subrectangles
题意
给定一个 \(N\times M\) 的 01 矩阵，你可以从行集合中选出一个子集 \(A\)，从列集合中选出一个子集 \(B\)，取出相交的位置，可以得到一个 \(|A|\times |B|\) 的子矩阵。
求使得这个子矩阵的和为奇数的方案数。对 \(998244353\) 取模。
\(N,M\le 300\)
题解
注意到对原矩阵做初等行变换和初等列变换都不会改变答案。
我们可以通过做初等行变换和初等列变换（即类似高斯消元的过程）将原矩阵变成每行每列最多只有一个 \(1\)。
假设最后有 \(K\) 个 \(1\)，那么其余 \(N-K\) 行和 \(M-K\) 列可以任意选，最后乘上 \(2^{N-K+M-K}\) 即可。
而对于这 \(K\) 个 \(1\)，我们要选择奇数个。枚举选择的个数 \(i\)，那么其余 \(K-i\) 个 \(1\) 对应的行和列不能同时选，所以对答案的贡献为 \(\binom{K}{i}3^{K-i}\)。
假设 \(N\) 与 \(M\) 同阶，时间复杂度 \(O(N^3)\)，可以用 bitset 优化到 \(O(\frac{N^3}{w})\)。
F - Pass
题意
有 \(N\) 个人从左到右排列，第 \(i\) 个人手上有 \(2\) 个球，其中 \(A_i\) 个是红球，\(2-A_i\) 个是蓝球。另外还有一个初始为空的序列 \(S\)。
需要执行 \(2N\) 次以下操作：
- 每个有球的人同时选择一个手上的球，并将该球给左边的人。特别地，第一个人会将这个球放到 \(S\) 的末尾。
求最后可以得到多少个不同的 \(S\)。注意相同颜色的球是相同的。对 \(998244353\)。
\(N\le 2000\)
题解
考虑固定一个 \(S\) 后如何判断。
从前往后依次判断，假设前 \(i-1\) 个位置合法，那么第 \(i\) 个位置合法当且仅当初始时前 \(\min(i,N)\) 个人手中的球去掉前 \(i-1\) 个球后存在一个球与第 \(i\) 个球相同。
于是直接 DP，\(f_{i,j}\) 表示 \(S\) 中前 \(i\) 个位置，有 \(j\) 个红球时的方案数。转移只要考虑下一个是红球还是蓝球即可。
时间复杂度 \(O(N^2)\)。
