题解：P11230 [CSP-J 2024] 接龙

· · 题解

读题！

每次选择长度从 2 到 k 的若干个连续的数字接龙。第一个人从1开始接，其余正常接。
每次询问要求恰好接龙 r_j 次，最后一次接龙的最后一个数字恰好是 c_j，问能不能做到。

让我想想怎么做？

首先很容易想到用DFS暴力枚举每一种情况，看看是否可行。
但是此时的时间复杂度为 O(\sum l q) ！！太大啦！！！
所以每次询问只能用 O(1) 的时间复杂度。
既然每次询问只能用 O(1) 的时间复杂度，那么我们就可以考虑预处理。
每次询问有给定的 r_j 和 c_j，而r \leq 100、c \leq 2e5，所以我们可以考虑预处理出 f_{r,j} 表示第 r 轮时，能不能以数字 j 结尾（能的话记是谁接的）。
它有三种取值：

从第 r−1 轮转移到第 r 轮，我们只关心：

某个数 u 如果出现在第 r−1 轮的结尾，并且不是 i 这个人接的，那么在第 i 人的词库中，以 u 开头的长度在 [2,k] 的连续子串，这些子串的结尾数字，就可以成为第 r 轮的候选。

上代码！

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

#define ll long long
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll t,f[105][200005];

void real_mian();

int main(){
    cin>>t;
    while(t--) real_mian();//真正的mian函数
    return 0;
}

void real_mian(){
    ll n,k,q,x,y;
    cin>>n>>k>>q;
    vector<vector<ll>>a(n+5);
    foru(i,1,n){
        cin>>x;
        a[i].clear();//记得清空
        foru(j,1,x){
            cin>>y;
            a[i].push_back(y);
        }
    }
    foru(i,0,100){
        foru(j,0,200000){
            f[i][j]=-1;//初始化
        }
    }
    f[0][1]=0;//第一次接龙从1开始
    foru(i,1,100){//枚举第几轮
        foru(j,1,n){//枚举每个人
            ll cnt=0;//记录还能接几个数
            for(auto x:a[j]){//枚举每个人的词库
                if(cnt>0){//还能接
                    if(f[i][x]==-1){//没人接（这是第一次接）
                        f[i][x]=j;//默认只能j接
                    }else if(f[i][x]!=j){//不是第一次接，且不是j接
                        f[i][x]=0;//那就随便接了
                    }
                    cnt--;//还能接龙的数量-1
                }
                if(f[i-1][x]!=-1&&f[i-1][x]!=j){//上一轮能接上，并且不是j接的
                    cnt=k-1;//这一轮还能接k-1个
                }
            }
        }
    }
    foru(i,1,q){
        cin>>x>>y;
        cout<<(f[x][y]==-1?0:1)<<endl;//直接输出
    }
}