Zhuky_RLG Round #1 题解

不要忘了点好评！

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$ 模拟题，得到了前所未有的效果。这是给我印象最深刻的一次模拟比赛！

gaolinxiang的博客

博客