不要忘了点好评！
Task #1 「ZYQ 的神秘家谱 | Family Tree」
Subtask #1：$n,m\le 100\ (60\ pts)$
将每个点与之能够直接到达的点连边，然后使用 $\text{Floyd}$（传递闭包）预处理出每个点能到达那些点，直接计算即可。时间复杂度 $\Theta(n^3)$。
Subtask #2：$n,m\le 3000\ (100\ pts)$
发现这个图是一个 $\text{DAG}$，然后使用拓扑排序就可以对于每个点可以 $\Theta(n)$ 算出他能够到达那些点。时间复杂度 $\Theta(n^2)$。
#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;
const int maxn = 3005;
const int logn = 18;
int n, m, q, cnt, du[maxn];
int tot, ter[maxn], nxt[maxn], lnk[maxn];
bool ok[maxn][maxn];
map<string, int> mmp;
queue<int> que;
string fa, ch;
void addedge(int u, int v) {
ter[++tot] = v;
nxt[tot] = lnk[u];
lnk[u] = tot;
du[v]++;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
cin >> fa;
mmp[fa] = ++cnt;
}
for (int i = 1; i <= m; i++) {
cin >> fa >> ch;
addedge(mmp[ch], mmp[fa]);
}
for (int i = 1; i <= n; i++) {
if (du[i] == 0) {
que.push(i);
}
ok[i][i] = 1;
}
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
for (int j = 1; j <= n; j++) {
ok[v][j] |= ok[u][j];
}
if (--du[v] == 0) {
que.push(v);
}
}
}
while (q--) {
cin >> fa >> ch;
puts(ok[mmp[fa]][mmp[ch]] && mmp[fa] != mmp[ch] ? "YES" : "NO");
}
return 0;
}
Subtask #3：$n,m\le 100000\ (0\ pts)$
如果一个人只有一个爸爸，我们就可以发现这个图是一棵内向树组成的森林，询问就变成了 $u$ 是否在 $v$ 的子树中。将每棵树 $\text{DFS}$ 一遍，求出每个节点子树中 $\text{DFS}$ 序的最小值和最大值。于是判断 $u$ 是否在 $v$ 的子树中就变成了判断 $lftbnd[v]\le dfn[u]\le rhtbnd[v]$ 是否成立。时间复杂度 $\Theta(n)$。
Task #2 「GWQ 与 MC 决胜 | Minecraft Duel」
Subtask #1：$n,m\le 100\ (20\ pts)$
枚举左端点和右端点，然后暴力 $\text{check}$ 即可。时间复杂度 $\Theta(n^3)$。
Subtask #2：$n,m\le 2000\ (50\ pts)$
枚举左端点和右端点，一边枚举一边 $\text{check}$ 即可。时间复杂度 $\Theta(n^2)$。
Subtask #3：$n,m\le 100000\ (100\ pts)$
使用 $\text{2-pointers}$，即可将复杂度优化到 $\Theta(n)$。
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 200005;
int cur, n, m, k, a[maxn], b[maxn], c[maxn];
long long s;
void update(int x, int y) {
if (c[x] >= b[x] && c[x] + y < b[x]) cur--;
if (c[x] < b[x] && c[x] + y >= b[x]) cur++;
c[x] += y, s += y * x;
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]), a[i + n] = a[i];
}
for (int t, i = 1; i <= m; i++) {
scanf("%d", &t), b[t]++;
}
int p = 1;
for (int i = 1; i <= n; i++) {
update(a[i], 1);
}
int ans = 0;
for (int i = n + 1; i <= n * 2; i++) {
update(a[i], 1);
while (i - p >= n || s >= k) {
update(a[p++], -1);
}
ans = max(ans, cur);
}
printf("%d\n", ans);
return 0;
}
Task #3 「ZYQ 与他的 Diep 游戏 | Diep」
Subtask #1：$n\le 2\ (40\ pts)$
直接枚举两行分别打到第几个怪物即可。时间复杂度 $\Theta(1)$。
Subtask #2：$n\le 8\ (100\ pts)$
状压 $\text{DP}$。$dp[mask]$ 表示每排打 $0,1,2,3,4$ 时剩余的最大子弹数量。时间复杂度 $\Theta(5^n)$。具体细节见代码。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 10;
const int maxm = 390630;
int n, m, a[maxn][5], pw[maxn], dp[maxm];
int main() {
pw[0] = 1;
for (int i = 1; i <= 8; i++) {
pw[i] = pw[i - 1] * 5;
}
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 4; j >= 1; j--) {
scanf("%d", &a[i][j]);
if (a[i][j] == 3) {
a[i][j] = -1;
} else if (a[i][j] == 4) {
a[i][j] = 1;
} else {
a[i][j] = -2;
}
}
}
dp[0] = m;
for (int i = 1; i < pw[n]; i++) {
for (int j = 1; j <= n; j++) {
int t = i / pw[j - 1] % 5;
if (t && dp[i - pw[j - 1]]) {
dp[i] = max(dp[i], dp[i - pw[j - 1]] + a[j][t]);
}
}
}
if (dp[pw[n] - 1]) {
puts("YES");
return 0;
}
for (int i = 1; i <= n; i++) {
if (a[n][i] < 0 && dp[pw[n] - 1 - pw[i - 1]] >= -a[n][i]) {
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}
Subtask #3：$n\le 2000\ (100\ pts)$
我们发现最优方案肯定是每次打掉最右边的一个怪物。直接 $\Theta(n^2)$ 枚举打那些怪物即可。
对出题人的建议：
- 本次比赛题目的细节非常多，但是思维难度非常低，完全不符合 $\text{CCF-NOIP}$ 的
尿性出题标准，导致比赛全场出现很多爆零的情况，使得出题人不得不提前报出不爆零的名单。希望出题人进行深刻反思。
- 不过总之：
题出的好！覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！出题人精心构造数据，防止了好多同学因为各种奇怪的乱搞搞到了较高的分数，具有较高的区分度。分数段分布设置合理，每个题目都给了巧妙的暴力分。出题人沥尽心血，精心打造的 $CCF-NOIP$ 模拟题，得到了前所未有的效果。这是给我印象最深刻的一次模拟比赛！
