CSP历年复赛题-P11230 [CSP-J 2024] 接龙

原题链接：https://www.luogu.com.cn/problem/P11230

题意解读：有n个人，每个人有一组整数序列，从任意整数1开始，取长度[2,k]的子序列作为一个龙，然后在其他人的序列中选长度[2,k]的子序列跟上一个子序列首尾相连（上一个子序列的尾等于当前子序列的头）称为接龙，每选择一个子序列是1轮接龙，有q个询问，问接r轮龙结尾是c是否可行，可行输出1不可行输出0。

解题思路：第r轮接龙以c结尾是否可行，可以通过第r-1轮c前面k-1个是否可行推出来，因此可以采用动态规划。

1、状态表示

设f[i][j]表示第i轮接龙以j结尾是否可行，由于要处理上一轮不能是同一个人，f[i][j]的值有三种：

f[i][j] = -1表示不可行，f[i][j] = x表示第i轮以j结尾是从x过来的，f[i][j] = 0表示第i轮以j结尾不止一个人

2、状态转移

枚举i:1~100轮

枚举j:1~n个人

枚举第j个人的所有序列

设当前整数为x，设当前可以接龙的数字个数为cnt

如果cnt>0

如果f[i][x]=-1，那么f[i][x]=j，表示没有接过龙则设置可以从当前人接龙

如果f[i][x]!=j，那么f[i][x]=0，表示之前接过龙则设置可以从不止一个人接龙

cnt—，表示当前数标记为可以接龙，可以接龙的数量减少一个

如果f[i-1][x]!=-1且f[i-1][x]!=j，则cnt=k-1，表示如果上一轮接龙的结尾是x则接下来可以接龙的数字数量更新为k-1个

3、初始化

f[i][j]默认值为-1，f[0][1] = 0，表示1是可以接龙的

4、结果

f[r][c]=-1时输出0，否则输出1

100分代码：

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

const int N = 200005, R = 105;
vector<int> s[N];
int f[R][N];
int n, k, q;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> k >> q;
        memset(f, -1, sizeof(f));
        for(int i = 1; i <= n; i++)
        {
            int l;
            cin >> l;
            s[i].clear();
            while(l--)
            {
                int x;
                cin >> x;
                s[i].push_back(x);
            }
        }
        f[0][1] = 0;
        for(int i = 1; i <= 100; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                int cnt = 0;
                for(auto x : s[j])
                {
                    if(cnt > 0)
                    {
                        if(f[i][x] == -1) f[i][x] = j;
                        else if(f[i][x] != j) f[i][x] = 0;
                        cnt--;
                    }
                    if(f[i - 1][x] != -1 && f[i - 1][x] != j) 
                        cnt = k - 1;
                }
            }
        }

        while(q--)
        {
            int r, c;
            cin >> r >> c;
            if(f[r][c] == -1) cout << 0 << endl;
            else cout << 1 << endl;
        }
    }

    return 0;
}

CSP-J复赛真题解析

CSP历年复赛题-P11230 [CSP-J 2024] 接龙