题解：P11230 [CSP-J 2024] 接龙（民间数据）

· · 题解

首先发现 个询问可以预处理完统一回答。

看到接龙问题，本能往图论建模的方向思考。我们可以假设某个开头往某个结尾连边来建图。对这张图 BFS 暴力，判断 BFS 的每一层都有哪些单词可以作为结尾就可以。

这里存在两个问题，首先我们发现边的数量太多，其次我们没办法区分上一轮和这一轮是不是同一个人。为了区分是否为同一个人，我们要建分层图，边的数量更多了。所以乍一看这条路走不通。

看一下暴力怎么做。我们每一轮，枚举每一个人的每一个子串。发现轮数很少，只有 。但是后面枚举所有人的所有子串复杂度太高了，考虑优化。

我们发现，对于一个子串 ，假设开头为 ，结尾为 。我们并不在乎 必须要绑定起来。我们只在乎上一轮作为结尾的 ，和这一轮作为开头的 ，不是同一个人，且这个子串长度在 之间。所以子串数从平分级变成了一次方级。

那问题就只剩下，如何判断 是否作为上一轮的某个结尾，和如何判断上一轮和这一轮不是同一个人。

我们可以开一个集合 set， 数组来记录一下，表示第 轮，以 结尾，都有哪些人。

这样我们只需要每一轮，枚举每一个人的每一个数字，记录一下第 人有哪些下标可以作为开头。只需要 !tag[turn-1][c].empty() && (tag[turn-1][c].size()>=2 || *tag[turn-1][c].begin()!=i)。先保证上一轮这个结尾存在，如果有多个人上一轮是这个结尾，那随便，如果只有一个人，要判断不是自己。

然后我们发现，没必要开一个 set。只需要一个变量记录即可。用 表示结尾不合法，用 表示结尾是第 个人的，用 表示有多个人。

记录下来第 个人的所有可以作为开头的下标后，再扫描一遍，钦定当前下标 可以作为结尾。那就需要满足存在一个开头，使得距离在 之间。对于刚刚的记录我们只需要解一下不等式，求出开头的下标区间，然后 lower_bound 去判断一下即可。

然后我们发现，我们只关注距离结尾最近的开头即可。所以也没必要记录所有开头的下标，也不需要 lower_bound。用一个变量存一下即可。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
/*====================*/
using lnt = long long;
/*====================*/
const int N = 1e5 + 10;
const int R = 1e2 + 10;
const int C = 2e5 + 10;
/*====================*/
const int INF = 0X3F3F3F3F;
/*====================*/
int n, k, q;
vector<int>s[N];
int tag[R][C];//记录第r层，c结尾，是谁接龙的。
/*====================*/
void Insert(int r, int c, int id)
{
    if (tag[r][c] == -1)
    {
        tag[r][c] = id;
    }
    else if (tag[r][c] != id)
    {
        tag[r][c] = 0;
    }
}
/*====================*/
void Solve(void)
{
    cin >> n >> k >> q;
    for (int i = 1; i <= n; ++i)
    {
        int l; cin >> l; s[i].assign(l, 0);
        for (int j = 0; j < l; ++j)cin >> s[i][j];
    }

    memset(tag, -1, sizeof(tag)); tag[0][1] = 0;

    for (int turn = 1; turn <= 1e2; ++turn)
    {
        for (int i = 1; i <= n; ++i)
        {
            int head = -INF;
            for (int j = 0; j < s[i].size(); ++j)
            {
                if (head >= j - k + 1)Insert(turn, s[i][j], i);
                if (tag[turn - 1][s[i][j]] != -1 && tag[turn - 1][s[i][j]] != i)head = j;
            }
        }
    }

    for (int i = 1; i <= q; ++i)
    {
        int r, c; cin >> r >> c;
        cout << (tag[r][c] == -1 ? 0 : 1) << endl;
    }
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
    freopen("IN.txt", "r+", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T = 1; cin >> T;
    while (T--)Solve();
    return 0;
}