[CSP-J 2024] 接龙

70pts

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5;
/*
状态：设dp[i][j]为第i轮，以j结尾的可能性
初始状态：dp[i][j]=0
状态：dp[i][j]=-1(指不存在以j结尾) ,dp[i][j]=0(存在以j结尾同事有行满足),dp[i][j]=x(存在j结尾，但只有x行) 
a[x][y]表示x个字符的第y个
枚举r轮，每一轮再去枚举是否可以以数a[x][y]为结尾
状态转移方程：：dp[i][j]=
if(dp[i-1][j]!=-1){
	//说明上一轮以j为结尾的数是存在的，但仅存在剩余不足2个--->dp[i][j]=-1;
	//否则可选择是否继承
	//如果只有一种且在同一行--->-1
	//如果有多种或不在一行--->{0(存在多个),x(只有一个)}
}else {
	dp[i][j]=-1;
}
*/
int dp[101][N+1];
void solve(){
 	int n,k,q;
 	cin>>n>>k>>q;//输入行数、每行最多往前看的列数和查询次数
	 
 	vector<vector<int> >a(n+1); //二维数组，a[i]存储数第i行的数字
	vector<int>sz(n+1);//sz[i]表示第i行的数字个数
	 
	for(int i=1;i<=n;i++){
		cin>>sz[i];//输入第i行的数字个数 
		a[i].resize(sz[i]+1);//调整a[i]的大小 
		for(int j=1;j<=sz[i];j++){
			cin>>a[i][j];//输入第i行的第j个数字 
		}
	} 
	/*
	dp[i][j]=-1表示不能以j为结尾完成接龙
	dp[i][j]=0表示当前以i为结尾的接龙有多行符合的情况 
	dp[i][j]=x 表示当前以j为结尾的接龙有唯一情况，且当前行为x 
	*/ 
	int R=100;//定义最大轮数为100 
	dp[0][1]=0;//初始化第0轮，以1为结尾的情况为0(初始状态) 
	for(int r=1;r<=R;r++){//遍历每一轮 
		for(int i=1;i<=n;i++){//遍历每一行 
			for(int j=2;j<=sz[i];j++){//遍历每一行的数字(从第2个开始) 
				int now=a[i][j];//当前数字 
				if(dp[r][now]==0)continue;//如过当前数字在本轮已经被标记为多行符合，则跳过
				//遍历当前数字前面的k-1个数字(最多往前看k-1个) 
				for(int f=max(1ll,j-k+1);f<j;f++){
					int pre=a[i][f];//前一个数字	 
					//如果前一个数字在上一轮不可用，或者上一轮的行数与当前行相同 
					if(dp[r-1][pre]==-1||dp[r-1][pre]==i)continue;
					//如果当前数字在本轮还没有被处理，则跳过 
					if(dp[r][now]==-1)dp[r][now]=i;	
					else if(dp[r][now]!=i)dp[r][now]=0;
				}
			}
		}
	} 
 	while(q--){
 		int r,c;
		cin>>r>>c;
		if(dp[r][c]>=0){
		 	cout<<1<<"\n";
		}else{
		 	cout<<0<<"\n";
		} 
 		
	}
	 
	 
    return;
}
signed main(){
    freopen("chain.in","r",stdin);
    freopen("chain.out","w",stdout);
	int T=1;
    cin>>T;
    while(T--){
    	memset(dp,-1,sizeof dp);
    	solve();
	}
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}

100pts

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
int dp[101][N + 1]; // 动态规划数组, dp[round][C] 表示在第 round 轮时, 以数字 c 结尾的接龙情况
int n, k, q;

void solve(){
    cin >> n >> k >> q; // 输入行数、每行最多往前看的列数和查询次数
    vector<vector<int>> a(n + 1); // 二维数组, a[i] 存储第 i 行的数字
    vector<int> sz(n + 1); // sz[i] 表示第 i 行的数字个数
    for (int i = 1; i <= n; i++) {
        cin >> sz[i]; // 输入第 i 行的数字个数
        a[i].resize(sz[i] + 1); // 调整 a[i] 的大小
        for (int j = 1; j <= sz[i]; j++) {
            cin >> a[i][j]; // 输入第 i 行的第 j 个数字
        }
    }

    // dp[i][j] = -1 表示不能以 j 结尾完成接龙
    // dp[i][j] = 0 表示当前以 j 结尾的接龙有多行符合的情况
    // dp[i][j] = x 表示当前以 j 结尾的接龙有唯一情况, 且当前行是 x
    int R = 100; // 定义最大轮数为 100
    dp[0][1] = 0; // 初始化第 0 轮, 以 1 结尾的情况为 0 (初始状态)
    for (int round = 1; round <= R; round++) { // 遍历每一轮
        for (int i = 1; i <= n; i++) { // 遍历每一行
            int l = 0, pre = -1; // l 表示当前行的起始位置, pre 表示前一个有效状态的行号
            for (int j = 1; j <= sz[i]; j++) { // 遍历每一行的每个数字
                int val = a[i][j]; // 当前数字
                // 如果前一个有效状态不是当前行, 并且当前数字在允许的范围内
                if (!(pre == -1 || pre == i)) {
                    if (l + k - 1 >= j) {
                        // 如果当前数字在本轮还没有被处理, 则标记为当前行
                        if (dp[round][val] == -1) {
                            dp[round][val] = i;
                        }
                        // 如果当前数字在本轮已经被其他行处理过, 则标记为多行符合
                        else if (dp[round][val] != i) {
                            dp[round][val] = 0;
                        }
                    }
                }

                // 获取上一轮当前数字的状态
                int now = dp[round - 1][a[i][j]];
                // 如果上一轮的状态有效, 并且不是当前行或者多行符合的情况
                if (now != -1 && (now == 0 || now != i)) {
                    pre = now; // 更新前一个有效状态的行号
                    l = j; // 更新当前行的起始位置
                }
            }
        }
    }

    // 处理每个查询
    while (q--) {
        int r, c;
        cin >> r >> c; // 输入查询的轮数和数字
        // 如果 dp[r][c] >= 0，说明存在符合条件的情况，输出 1，否则输出 0
        if (dp[r][c] >= 0) {
            cout << 1 << endl;
        }
        else {
            cout << 0 << endl;
        }
    }
}

int main(){
    freopen("chain.in","r",stdin);
    freopen("chain.out","w",stdout);
    int t;
    cin >> t;
    while(t--){
        memset(dp,-1,sizeof dp);
        solve();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}