NOMURA Programming Competition 2020 题解
ABC 之前做过，就不写了。
D - Urban Planning
题意
有一个 \(n\) 个点的无向图，初始没有边。
定义一个序列 \(a_1,a_2,\ldots,a_n\ (1\le a_i\le n,a_i\ne i)\) 的权值为，要求对于每个 \(1\le i\le n\)，最终的无向图中 \(i\) 与 \(a_i\) 连通，最少需要加入的边数。
给定序列 \(P_1,P_2,\ldots,P_n\)，有些 \(P_i\) 可能为 \(-1\)，你需要将所有 \(P_i=-1\) 的位置替换成一个不为 \(i\) 的 \(1\) 到 \(n\) 的整数，求所有这些序列的权值之和。对 \(10^9+7\) 取模。
\(n\le 5000\)
题解
显然序列 \(a_1,a_2,\ldots,a_n\) 的权值为 \(i\) 与 \(a_i\) 连边时的最小生成森林大小，即点数减环数。那么不妨计算环数之和。考虑计算每个环对答案的贡献。
对于所有 \(P_i\ne -1\) 的位置，我们将 \(i\) 与 \(P_i\) 连边，这样每个连通块就是一个基环树或树。
设 \(-1\) 的数量为 \(k\)。
对于是基环树的连通块，每一种方案都会包含这个环，所以答案直接加上 \((n-1)^k\) 即可。
接下来我们考虑是树的连通块之间形成的环。假设这些连通块大小为 \(a_1,a_2,\ldots,a_m\)。
若我们选出了 \(x_1,x_2,\ldots,x_l\) 这些连通块连成一个基环树，那么方案数为 \[(l-1)!\prod_{i=1}^{l} a_{x_i}\]
对答案的贡献只要再乘上 \((n-1)^{m-l}\) 即可。
简单的 DP 即可。时间复杂度 \(O(n^2)\)。
E - Binary Programming
题意
有一个初始为空的字符串 \(S\) 和初始为 \(0\) 的整数变量 \(x\)。
给定 01 字符串 \(T\)，你可以执行以下操作 \(|T|\) 次：
- 在 \(S\) 的任意位置插入字符 \(0\) 或 \(1\)。
- 将 \(x\) 加上 \(S\) 中奇数位置的数字之和。\(S\) 从 \(1\) 开始标号。
你需要保证最后 \(S=T\)。
求最终 \(x\) 的最大值。
\(|T|\le 2\times 10^5\)
题解
首先我们可以将操作变成从 \(T\) 中不断删除字符。
那么一定是先删 \(0\) 再删 \(1\)。
证明可以考虑如果当前存在 \(0\) 但是删除了 \(1\)，假设这个字符串是 \(S\)，那么我们如果不删除这个 \(1\)，改而删除这个 \(1\) 左边或右边最近的一个 \(0\)，得到的字符串 \(S'\) 相比于 \(S\) 一定是某个位置的 \(0\) 变成了 \(1\)，不会更劣。
而删除 \(0\) 时一定是不断删除第一个奇数位置的 \(0\)。若不存在奇数位置的 \(0\)，则从后往前依次删除 \(0\)。
证明可以考虑对于一段长度为偶数的连续的 \(1\)，在删除 \(0\) 的过程中贡献一定相同，可以不考虑，直接删去。
于是我们可以将原串处理成没有连续两个 \(1\) 相邻的形式。剩下对于所有 \(1\) 的位置 \(i\)，记 \(pre_i\) 为 \(1\) 到 \(i\) 中 \(0\) 的数量，\(suf_i\) 为 \(i\) 到 \(|T|\) 中 \(0\) 的数量，那么这个位置的 \(1\) 在删除 \(0\) 的过程中贡献最多为 \(\lfloor\frac{pre_i+1+i\bmod 2}{2}\rfloor+suf_i\)，而上述删除顺序恰好可以达到该上界。
删除 \(1\) 时的贡献可以简单的算出。
时间复杂度 \(O(|T|)\)。
F - Sorting Game
题意
A 和 B 玩游戏，过程如下：
- 给出一个长度为 \(M\)，元素为 \(0\) 到 \(2^N-1\) 的整数的序列 \(a_1,\ldots,a_M\)。
- A 可以选择一些二进制位，将 \(a\) 中每个数的这些二进制位置为 \(0\)。
- B 可以执行若干次交换 \(a_i\) 和 \(a_{i+1}\) 的操作，需要满足 \(a_i\) 和 \(a_{i+1}\) 二进制位恰好有一位不同。
你需要求有多少种不同的序列 \(a\)，使得 A 无论如何操作，B 都可以将 \(a\) 从小到大排序。对 \(10^9+7\) 取模。
\(N,M\le 5000\)
题解
注意到合法的 \(a\) 需要满足对于所有 \(1\le i < j\le M\)，\(a_i\) 与 \(a_j\) 从高到低第一次出现 \(a_i\) 的这一位为 \(1\)，\(a_j\) 的这一位为 \(0\) 的位置后，更低位都相同。
考虑 \(a_1,a_2,\ldots,a_M\) 的最高位，有两种情况：
- 形如 \(0\ldots01\ldots1\)，这样我们就不需要考虑这一位，变成一个 \(N-1\) 位的子问题，最高位的填数方案数为 \(M+1\)。
- 形如 \(0\ldots0\mathbf{1x\ldots x0}1\ldots 1\)，此时中间加粗部分的更低位需要全部相同，所以假设加粗部分的长度为 \(i\)，那么变成了一个 \(N-1\) 位，序列长度为 \(M-i+1\) 的子问题，最高位的填数方案为 \((M-i+1)2^{i-2}\)。
可以证明除这两种情况以外的情况一定不合法。
所以我们就有了一个朴素的 \(O(NM^2)\) DP，用前缀和优化可以做到 \(O(NM)\)。
