2024 接龙 · 方案一按定义广搜

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 3000 字
状态是上一轮的人与末尾元素
2024
搜索
正文

// CSP-J 2024 复赛 T4 · 接龙
// 原题：https://oj.yecheng.tv/p/ccf-CSPJ2024D
// 题意：n 个人各有自己的词库 S_i。一轮接龙由某个人 p 挑出自己词库的一个
// 连续子序列 A，长度在 [2, k] 之间；第一轮 A 要以 1 开头，之后每轮 A 要以上一轮
// A 的最后一个元素开头；相邻两轮不能是同一个人。
// 每个任务问：能不能恰好做 r 轮，且最后一轮的 A 最后一个元素正好是 c。
//
// 方案一 · 按定义做 BFS（直观，只能过小数据）
// 状态记成 (上一轮是谁, 上一轮的最后一个元素)。
// 第一轮的起点必须是元素 1；之后从每个状态出发，枚举另一个人 p'、
// 枚举他词库里值等于「上一轮末尾」的位置、再枚举接龙长度 2..k，得到新状态。
// 用 set 存每一轮的状态集合，顺便把这一轮能到达的末尾元素记下来，用来回答任务。
// 复杂度大约是 O(r * n * 词库总长 * k)，只能过 n <= 1e3、r <= 10 那批测试点。

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

vector<int> S[1005];

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

    int T;
    cin >> T;
    while (T--) {
        int n, k, q;
        cin >> n >> k >> q;
        for (int i = 1; i <= n; i++) {
            S[i].clear();
            S[i].push_back(0);                   // 占位，让下标从 1 开始
            int l;
            cin >> l;
            for (int j = 0; j < l; j++) {
                int x;
                cin >> x;
                S[i].push_back(x);
            }
        }
        vector<pair<int, int>> ask(q);
        int maxR = 0;
        for (int i = 0; i < q; i++) {
            cin >> ask[i].first >> ask[i].second;
            maxR = max(maxR, ask[i].first);
        }

        set<pair<int, int>> cur;                 // (上一轮的人, 上一轮的末尾元素)
        for (int p = 1; p <= n; p++) {
            for (int j = 1; j < (int)S[p].size(); j++) {
                if (S[p][j] != 1) continue;      // 第一轮必须以 1 开头
                for (int t = 2; t <= k && j + t - 1 < (int)S[p].size(); t++) {
                    cur.insert(make_pair(p, S[p][j + t - 1]));
                }
            }
        }

        vector<set<int>> reach(maxR + 1);
        for (set<pair<int, int>>::iterator it = cur.begin(); it != cur.end(); ++it) {
            reach[1].insert(it->second);
        }
        for (int r = 2; r <= maxR; r++) {
            set<pair<int, int>> nxt;
            for (set<pair<int, int>>::iterator it = cur.begin(); it != cur.end(); ++it) {
                int lastPerson = it->first;
                int lastValue = it->second;
                for (int p = 1; p <= n; p++) {
                    if (p == lastPerson) continue;             // 不能连着同一个人
                    for (int j = 1; j < (int)S[p].size(); j++) {
                        if (S[p][j] != lastValue) continue;    // 这一轮要接着它开头
                        for (int t = 2; t <= k && j + t - 1 < (int)S[p].size(); t++) {
                            nxt.insert(make_pair(p, S[p][j + t - 1]));
                        }
                    }
                }
            }
            cur = nxt;
            for (set<pair<int, int>>::iterator it = cur.begin(); it != cur.end(); ++it) {
                reach[r].insert(it->second);
            }
        }

        for (int i = 0; i < q; i++) {
            int r = ask[i].first;
            int c = ask[i].second;
            cout << (r <= maxR && reach[r].count(c) ? 1 : 0) << "\n";
        }
    }
    return 0;
}
2024 接龙 · 方案一 按定义广搜

正文

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

2024 接龙 · 方案一按定义广搜
