2019 加工零件 · 方案一递归加记忆化

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1258 字

按定义递推，用来想清题意

2019
图论

正文

// CSP-J 2019 复赛 T4 · 加工零件
// 原题：https://oj.yecheng.tv/p/CSPJ2019D
// 题意：x 号工人生产第 L 阶段零件，他的所有邻居都要生产第 L-1 阶段；
// 生产第 1 阶段时，邻居要为他提供原材料。问 1 号轩轩要不要提供原材料。
//
// 方案一 · 按定义递归 + 记忆化（直观，L 很大时会超时）
// 设 need(x, L) 为：为了 x 生产第 L 阶段，1 号是否需要提供原材料。
//   边界：need(x, 1) 为真，当且仅当 1 号是 x 的邻居；
//   递推：need(x, L) = 所有邻居 y 的 need(y, L-1) 取「或」。
// 直接递归会指数爆炸；加上记忆化仍要 O(n * L)，L 能到 1e9 时依然不行。
// 这一版用来把题意彻底想清楚，满分请看法二。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> g[MAXN];
int memo[MAXN][32];   // -1 未算过，0 否，1 是；只演示到很小的 L

int dfs(int x, int L) {
    if (L == 1) {
        for (int w : g[x]) if (w == 1) return 1;
        return 0;
    }
    if (memo[x][L] != -1) return memo[x][L];
    int res = 0;
    for (int w : g[x]) {
        if (dfs(w, L - 1)) { res = 1; break; }
    }
    return memo[x][L] = res;
}

int main() {
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);

    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    memset(memo, -1, sizeof(memo));
    while (q--) {
        int a, L;
        cin >> a >> L;
        cout << (dfs(a, L) ? "Yes" : "No") << "\n";
    }
    return 0;
}

2019 加工零件 · 方案一 递归加记忆化

正文

CSP-J 标程 · 复赛真题的其它内容

2019 加工零件 · 方案一递归加记忆化