2024 接龙 · 方案二滑动窗口逐轮推进

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 3243 字
每人每轮只扫一遍词库，窗口里数可当起点的位置
2024
动态规划
正文

// CSP-J 2024 复赛 T4 · 接龙（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/ccf-CSPJ2024D
//
// 方案二 · 逐轮推进 + 滑动窗口算「哪些位置能当本轮结尾」
// 方案一慢在两层枚举（人 × 长度）。换个角度：一轮一轮往前推，
// 只维护「第 r 轮能以元素 v 结尾」这件事，并为每个 v 记下两个不同的人编号
// （记两个就够：要避开上一轮那个人，两个里总有一个能用）。
// 推进一轮时，对每个人 p 单独扫一遍他的词库：
//   位置 j 能当起点，当且仅当 第 r-1 轮能以 S_p[j] 结尾，且那一轮里有人不是 p；
//   位置 q 能当本轮结尾，当且仅当窗口 [q-k+1, q-1] 里存在能当起点的位置。
// 后者用滑动窗口计数：q 往右挪一格时，把 j = q-1 加进来、把 j = q-k 划出去。
// 这样每个人每轮只扫一遍词库，总复杂度 O(轮数 * 词库总长)，
// r 最多 100、词库总长 2e5，完全来得及。
// 任务按 r 分好组，算完第 r 轮就把这一组的答案填进 ans 数组，最后按原顺序输出。

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

const int MAXV = 200005;

vector<vector<int> > S;
int maxR;
int k;

bool curOk[MAXV];                  // 上一轮：能不能以这个值结尾
int who1[MAXV], who2[MAXV];        // 上一轮做到这件事的两个不同人编号
bool nxtOk[MAXV];
int nw1[MAXV], nw2[MAXV];

// 第 r 轮时，第 p 个人的位置 j 能不能当接龙起点
bool canStart(int p, int j, int r) {
    int v = S[p][j];
    if (r == 1) return v == 1;                 // 第一轮必须以 1 开头
    if (!curOk[v]) return false;
    if (who1[v] != p) return true;             // 有一个做到的人不是 p
    if (who2[v] != -1 && who2[v] != p) return true;
    return false;
}

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

    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> k >> q;
        S.assign(n + 1, vector<int>(1, 0));    // 下标从 1 开始
        for (int i = 1; i <= n; i++) {
            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);
        maxR = 0;
        for (int i = 0; i < q; i++) {
            cin >> ask[i].first >> ask[i].second;
            maxR = max(maxR, ask[i].first);
        }
        vector<vector<int> > byRound(maxR + 1);
        for (int i = 0; i < q; i++) byRound[ask[i].first].push_back(i);
        vector<int> answer(q, 0);

        memset(curOk, 0, sizeof(curOk));
        for (int r = 1; r <= maxR; r++) {
            memset(nxtOk, 0, sizeof(nxtOk));
            for (int v = 0; v < MAXV; v++) {
                nw1[v] = -1;
                nw2[v] = -1;
            }
            for (int p = 1; p <= n; p++) {
                int cnt = 0;                   // 窗口内可当起点的位置个数
                int l = (int)S[p].size() - 1;
                for (int qpos = 1; qpos <= l; qpos++) {
                    if (qpos >= 2 && canStart(p, qpos - 1, r)) cnt++;
                    if (qpos - k >= 1 && canStart(p, qpos - k, r)) cnt--;
                    if (cnt > 0) {
                        int v = S[p][qpos];
                        nxtOk[v] = true;
                        if (nw1[v] == -1) nw1[v] = p;
                        else if (nw1[v] != p && nw2[v] == -1) nw2[v] = p;
                    }
                }
            }
            memcpy(curOk, nxtOk, sizeof(curOk));
            memcpy(who1, nw1, sizeof(who1));
            memcpy(who2, nw2, sizeof(who2));

            for (int t = 0; t < (int)byRound[r].size(); t++) {
                int idx = byRound[r][t];
                answer[idx] = curOk[ask[idx].second] ? 1 : 0;
            }
        }
        for (int i = 0; i < q; i++) cout << answer[i] << "\n";
    }
    return 0;
}
2024 接龙 · 方案二 滑动窗口逐轮推进

正文

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

2024 接龙 · 方案二滑动窗口逐轮推进
