题目传送门：AtCoder NOMURA Programming Competition 2020。
A - Study Scheduling
略。
#include <cstdio>
int main() {
int H1, M1, H2, M2, K;
scanf("%d%d%d%d%d", &H1, &M1, &H2, &M2, &K);
printf("%d
", (H2 - H1) * 60 + M2 - M1 - K);
return 0;
}
B - Postdocs
易证存在一种最优解为把所有 ? 替换成 D。
#include <cstdio>
char str[200005];
int main() {
scanf("%s", str + 1);
for (int i = 1; str[i]; ++i)
printf("%c", str[i] == '?' ? 'D' : str[i]);
puts("");
return 0;
}
C - Folia
令 (C_d) 为最优方案中深度为 (d) 的非叶子节点数量。
则有限制 (C_d le 2 C_{d - 1} - A_d) 和 (C_d le C_{d + 1} + A_{d + 1})。
从 (d = 0) 和 (d = N) 向中心推进限制即可。
#include <cstdio>
typedef long long LL;
const int MN = 200005;
int N;
LL A[MN], B[MN], C[MN];
int main() {
scanf("%d", &N);
for (int i = 0; i <= N; ++i) scanf("%lld", &A[i]);
if (!N) return puts(A[0] == 1 ? "1" : "-1"), 0;
for (int i = N; i >= 0; --i) B[i] = B[i + 1] + A[i];
C[0] = 1 - A[0];
for (int i = 1; i <= N; ++i) {
C[i] = 2 * C[i - 1] - A[i];
if (C[i] < 0 || C[i] + A[i] == 0) return puts("-1"), 0;
if (C[i] + A[i] > B[i]) C[i] = B[i] - A[i];
}
LL Ans = 0;
for (int i = 0; i <= N; ++i) Ans += A[i] + C[i];
printf("%lld
", Ans);
return 0;
}
D - Urban Planning
假设原图由 (M) 个基环内向树和 (K) 个内向树构成。
并且令 (K) 个内向树的大小依次为 (b_1, b_2, ldots , b_K)。
要求将给定点对连通的最小边数，也就相当于求 (N) 减去连通块个数。
只要求出所有图中的连通块个数，再用 (N {(N - 1)}^K) 减去这个值即可。
显然至少有 (M) 个连通块，给总连通块个数贡献 (M {(N - 1)}^K)。
在其余的 (K) 个内向树中，可以将每个内向树看作一个整体，每在其中形成一个环，就为连通块个数贡献 (1)。
考虑枚举某个环中的所有内向树，假设为 (k)（(k ge 1)）个，为 ({ a_1, a_2, ldots , a_k })（无顺序）。
那么它们形成环的方案数就为 (displaystyle (k - 1)! prod_{i = 1}^{k} b_{a_i})。
即枚举一种圆排列（共有 ((k - 1)!) 种），每一个内向树的根可以连向下一个内向树的任何一个点，所以把所有 (b) 值相乘即可。
除了一种例外情况，当 (k = 1) 时，方案数应该为 ((b_{a_1} - 1))，因为有不能连向自己的限制。
据此可以考虑一个 DP：对于每个 (k) 满足 (1 le k le K)，求出在所有内向树中选出 (k) 个时它们的 (b) 值的乘积之和。
依次加入每个内向树即可维护。
求出后每项乘上 ((k - 1)!)，再乘上 ({(N - 1)}^{K - k})（剩下的其它内向树的方案数）贡献给答案即可，对于 (k = 1) 特殊处理一下。
#include <cstdio>
#include <vector>
typedef long long LL;
const int Mod = 1000000007;
const int MN = 5005;
inline int qPow(int b, int e) {
int a = 1;
for (; e; e >>= 1, b = (LL)b * b % Mod)
if (e & 1) a = (LL)a * b % Mod;
return a;
}
int N, M, A[MN], Fac[MN];
std::vector<int> G[MN];
int K, B[MN];
int vis[MN];
void DFS(int u) {
++B[K], vis[u] = 1;
for (int v : G[u]) DFS(v);
}
void DFS2(int u, int o) {
vis[u] = 1;
for (int v : G[u])
if (!vis[v]) DFS2(v, o);
else if (v == o) ++M;
}
int dp[MN][MN];
int main() {
scanf("%d", &N), Fac[0] = 1;
for (int i = 1; i <= N; ++i) scanf("%d", &A[i]), Fac[i] = (LL)Fac[i - 1] * i % Mod;
for (int i = 1; i <= N; ++i) if (~A[i]) G[A[i]].push_back(i);
for (int i = 1; i <= N; ++i) if (!~A[i]) ++K, DFS(i);
for (int i = 1; i <= N; ++i) if (!vis[i]) DFS2(i, i);
dp[0][0] = 1;
for (int i = 1; i <= K; ++i) {
dp[i][0] = 1;
for (int j = 1; j <= i; ++j)
dp[i][j] = (dp[i - 1][j] + (LL)dp[i - 1][j - 1] * B[i]) % Mod;
}
dp[K][1] -= K;
int Ans = (LL)M * qPow(N - 1, K) % Mod;
for (int j = 1; j <= K; ++j) Ans = (Ans + (LL)dp[K][j] * Fac[j - 1] % Mod * qPow(N - 1, K - j)) % Mod;
Ans = ((LL)N * qPow(N - 1, K) % Mod - Ans + Mod) % Mod;
printf("%d
", Ans);
return 0;
}
E - Binary Programming
令 (N = |T|)，等价于执行以下操作 (N) 次：
- 所有奇数位的数之和贡献给答案。
- 删去任意一位。
首先可以发现当 0 还没删光时，删 1 是不优的。
然而当 0 删光了的时候，之后的操作对答案的贡献就很显然了。所以这里考虑如何删 0 是最优的。
可以发现如果有两个相邻的 1，那么每次操作时它们对答案的贡献都是 (1)。所以可以先不考虑。
那么一直删除相邻的两个 1 后，只剩下 (k) 个 1 时，就形成了 (a_0mathtt{0} quad mathtt{1} quad a_1mathtt{0} quad mathtt{1} quad cdots quad mathtt{1} quad a_kmathtt{0}) 的情况。
对于其中的第 (i) 个 1，它最多给答案贡献 ((a_0 + cdots + a_{i - 1})) 的一半（取整方式取决于位置的奇偶性）加 ((a_i + cdots + a_k))。
而事实上这个上界是可以被达到的，也就是需要对每个 1 都满足在删它后面的 0 时它的位置在奇数：
先把 (a_0) 个最开始的 0 删光，然后删 (a_1 - 1) 个 0 留下恰好一个，以此类推，删掉 (a_{k - 1} - 1) 个 0 留下恰好一个。
这时形如 (mathtt{1010100000000 cdots})，然后从右到左把所有的 0 删掉即可。
所以使用上述结论求答案即可。
#include <cstdio>
#include <cstring>
typedef long long LL;
const int MN = 200005;
int N, C0, C1, K;
char T[MN];
int stk[MN], cnt[MN], tp;
LL Ans;
int main() {
scanf("%s", T + 1), N = strlen(T + 1);
for (int i = 1; i <= N; ++i) ++(T[i] & 1 ? C1 : C0);
Ans = (LL)(C1 + 1) * (C1 + 1) / 4;
T[0] = T[N + 1] = '0';
for (int i = 0; i <= N + 1; ++i) {
int x = T[i] - '0';
if (!x) {
if (tp && !stk[tp]) ++cnt[tp];
else stk[++tp] = 0, cnt[tp] = 1;
} else {
if (tp && stk[tp]) --tp, Ans += C0;
else stk[++tp] = 1, cnt[tp] = 1;
}
} --cnt[1], --cnt[tp];
for (int i = 1, s = 0; 2 * i <= tp; ++i)
s += cnt[2 * i - 1],
Ans += (s + i + 1) / 2 - (i + 1) / 2 + (C0 - s);
printf("%lld
", Ans);
return 0;
}
F - Sorting Game
注意到，一个序列是合法的，当且仅当对于所有的两个下标 (i, j)（(1 le i < j le M)），都有：
按二进制位从高到低比较 (a_i) 与 (a_j)，出现 (a_i) 该位为 (1) 且 (a_j) 该位为 (0) 后，其余的更低位 (a_i) 必须与 (a_j) 完全相同。
考虑 (a_1 sim a_M) 的最高位，有两种情况：
- 依次为形如 (mathtt{000111})，也就是先 (0) 后 (1)：不存在两个下标先 (1) 后 (0)，转化为 ((N - 1, M)) 的子问题，共有 ((M + 1)) 种方案。
- 依次为形如 (mathtt{0001????0111})，也就是删去前缀连续的 (0) 和后缀连续的 (1) 后非空的情况：
所以删去后的那一部分的更低位必须都全部相同了，而前缀连续的 (0) 和后缀连续的 (1) 则不受任何影响。
这就相当于把中间的部分缩成同一个数了，假设缩完之后的长度为 (i)，则转化为 ((N - 1, i)) 的子问题。
假设缩完之后的长度为 (i)，实际上有恰好 (i) 种方案去分配被缩起来的部分，而对于 (mathtt{????}) 部分，共有 (2^{M - i - 1}) 种方案。
也就是说，有如下 DP 转移方程：
后面的部分可以使用前缀和的思想以加速处理，时间复杂度为 (mathcal O (N M))。
#include <cstdio>
#include <vector>
typedef long long LL;
const int Mod = 1000000007;
const int MN = 5005;
int N, M, f[MN][MN];
int main() {
scanf("%d%d", &N, &M);
for (int j = 1; j <= M; ++j) f[0][j] = 1;
for (int i = 1; i <= N; ++i) {
for (int j = 2; j <= M; ++j)
f[i][j] = (2 * f[i][j - 1] + (LL)f[i - 1][j - 1] * (j - 1)) % Mod;
for (int j = 1; j <= M; ++j)
f[i][j] = (f[i][j] + (LL)f[i - 1][j] * (j + 1)) % Mod;
}
printf("%d
", f[N][M]);
return 0;
}