题解：P11230 [CSP-J 2024] 接龙（民间数据）
huangboning
·
·
题解
动态规划题。
设 dp_{i,j} 表示第 j 轮时数字 i 能否被转移。其中 dp_{i,j}=-1 表示不能，
每次转移将每个人扫一遍，用 x 来维护当前是否有可以转移的状态，特判前一个状态和这个状态是否为同一个人即可。
upd:发现不用快读，优化了一下码风。
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n,k,q,l[200010],xx[200010],yy[200010],dp[200010][110];
vector<int>v[200010];//每个人的词库
int main()
{
ios::sync_with_stdio(0);
cin>>T;
while(T--){
cin>>n>>k>>q;
int maxl=0,maxr=0;
for(int i=1;i<=n;i++){
cin>>l[i];
v[i].clear();
for(int j=1;j<=l[i];j++){
int x;
cin>>x;
maxl=max(maxl,x);
v[i].push_back(x);
}
}
for(int i=1;i<=q;i++){
cin>>xx[i]>>yy[i];
maxr=max(maxr,xx[i]);
}
for(int i=0;i<=maxl;i++){
for(int j=0;j<=maxr;j++){
dp[i][j]=-1;
}
}
dp[1][0]=0;//必须从1开始
for(int i=1;i<=maxr;i++){//i为轮数
for(int j=1;j<=n;j++){
int x=-1;
for(int k1=0;k1<v[j].size();k1++){
int t1=v[j][k1];//t1为这个人的第k1+1个单词
if(k1>=k){//长度超过k
int t2=v[j][k1-k];
if(dp[t2][i-1]!=-1&&dp[t2][i-1]!=j&&x==k1-k)x=-1;//如果唯一能转移的状态出界
}
if(x!=-1){//更新当前状态
if(dp[t1][i]==-1)dp[t1][i]=j;
else if(dp[t1][i]!=j)dp[t1][i]=0;
}
if(dp[t1][i-1]!=-1&&dp[t1][i-1]!=j)x=k1;//更新x
}
}
}
for(int i=1;i<=q;i++){
if(yy[i]>maxl)cout<<"0";//如果不存在yy[i]
else cout<<(dp[yy[i]][xx[i]]!=-1);//否则输出是否无解
cout<<"\n";
}
}
}
```