题解

然而这道题是提高+/省选-

典型的动态规划题

具体看注释

#include<bits/stdc++.h>
using namespace std;
#define L long long
const int max1=2e5+10,max2=110,max3=1e5+3;
int Ans[max2][max1];
int S[max1],l[max3];
int n,k,q;
inline int qcin(){
	//快读，getchar速度大于scanf
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
			f=-1;
		}
        c=getchar();
    }
    while(c>='0'&&c<='9'){
		k=k*10+c-'0';
		c=getchar();
	}
    return k*f;
}
void qcout(int x){
	//快输，putchar速度大于printf
    if(x<0){
		putchar('-');
		x=-x;
	}
    if(x<10){
		putchar(x+'0');
	}else {
		qcout(x/10);
		putchar(x%10+'0');
	}
}
void solve(){
	memset(Ans,-1,sizeof Ans);
	Ans[0][1]=0; //第一个接龙的人数字必须从1开始，因此，这是一定能成的
	for(int i=1;i<=100;i++){
		for(int j=1;j<=n;j++){
			//j：人的编号
			int a=0; //接下来a个数字都能接龙
			for(int k1=l[j-1]+1,x=S[k1];k1<=l[j];k1++,x=S[k1]){
//				记录每个最后一个数为S[i]的接龙的人
				a--;    //无论如何a都要-1
				if(a>0){
					//证明是可接龙的
					if(Ans[i][x]==-1){
						Ans[i][x]=j; //在最后一个数为x的轮数为i的接龙人为j
					}else if(Ans[i][x]&&Ans[i][x]!=j){
						//不是j接龙，但是其他人接了龙，一定能接上去，这种情况标记为0
						Ans[i][x]=0;
					}
				}
				if(Ans[i-1][x]!=-1 && Ans[i-1][x]!=j){
					//如果有人接但不是j接的
					a=k;//接下来的k-1个数字都能接龙（前面减了）
				}
			}
		}
	}
		for(int r,c;q;putchar('\n'),q--){
			r=qcin();
			c=qcin();
			qcout((Ans[r][c]!=-1?1:0));
		}
		//O(1)回答即可
}
int main(){
//	freopen("Example.in","r",stdin);
//	freopen("Example.out","w",stdout);
	int T=qcin();
	for(;T;T--){
		//Read
		n=qcin();
		k=qcin();
		q=qcin();
		l[0]=0;
		for(int i=1;i<=n;i++){
			l[i]=l[i-1]+qcin();
			for(int j=l[i-1]+1;j<=l[i];j++){
				S[j]=qcin();		
			}

		}
		solve();
	}
	   //  fclose(stdin);
    // fclose(stdout);
	return 0;
}