题解：P11230 [CSP-J 2024] 接龙（官方数据）

· · 题解

Analysis

这道题光读题很困难，重点是我们要找到题目的规律和性质：

我们要找是否存在 r 个头尾相接、长度为 2 \sim k 的序列（第一个序列一定以 1 开头）。

因为这是第四题，加上是序列类的问题，首先考虑 dp。题目有三个关键条件：轮数、结尾数字、上一轮选择的行。

从数据范围入手，这道题的数据范围很大，q \le 10^5，说明要 O(1) 回答询问，不难想到要用 dp 预处理。

又因为 r \le 100，S_{i,j} \le 2 \times 10^5，两者相乘刚好是 2 \times 10^7，在 1s 时限内。所以考虑用这两个维度设状态，另一个维度存数据，这样也方便转移。

下面是重点！

设 dp[r][j] 记录在第 r 轮能否以数字 j 作为结尾。我们设 dp[r][j] 的取值有以下三种情况：

要判断 dp[r][j] 是否能接龙，就要看在 dp[r-1] 中 j 是否在长为 2 \sim k 的子序列中出现过，且可以进行接龙。

具体来说：

  1. 枚举所有人的所有数字 u。因为题目中说 \sum l \le 2 \times 10^5，所以此处不超时。
  2. 看 u 前面的 k 个数字中，是否有作为上一轮结尾的。
  3. 若 u 可以被接上，则 u 之后的 k-1 个数字都可以作为第 r 轮的结尾。同时标记 dp 数组。

这样就可以做到 O(r \times n + \sum l) 的预处理，O(1) 询问。

几个注意事项：

  2. 在上面的步骤三中，“u 之后的 k-1 个数字都可以作为第 r 轮的结尾”这一操作可以用差分实现，还可以记录一个 cnt 变量表示还剩几个可以作为结尾的数：在循环遍历的同时，每遍历到一个就把 cnt 减一，可以在迭代同时实现和差分一样的效果。
  3. 多组数据，注意每次都要清空 vector 数组及 dp 数组！！！

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;

int n, k, q, dp[110][maxn];
vector <int> v[maxn];

void solve()
{
    memset(dp, -1, sizeof dp); // 初始化！！！
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i ++){
        int l; cin >> l;
        v[i].clear(); // 清空！！！
        for(int j = 0, x; j < l; j ++){
            cin >> x; v[i].push_back(x);
        }
    }

    // 预处理dp
    dp[0][1] = 0; // 第一轮一定从1开始
    for(int r = 1; r <= 100; r ++){ // 枚举轮数
        for(int i = 1; i <= n; i ++){ // 枚举当前轮要接的行数
            int cnt = 0; // 记录还有多少个可以作为接龙结尾的数
            for(auto u : v[i]){ // 遍历第i行每一个数
                if(cnt > 0){
                    if(dp[r][u] == -1) dp[r][u] = i; // 第一次被接龙
                    else if(dp[r][u] != i) dp[r][u] = 0; // 第二次被接龙后可以任意接龙
                    -- cnt; // 要接龙的个数--
                    //（这里也可以用差分实现）
                }

                if(dp[r - 1][u] != -1 && dp[r - 1][u] != i){
                    cnt = k - 1; // u之后的k-1个数都可以被接
                }
            }
        }
    }

    // O(1)处理询问
    while(q --){
        int r, c; cin >> r >> c;
        cout << (dp[r][c] == -1? 0 : 1) << '\n';
    }
}

signed main()
{
    int T; cin >> T;
    while(T --) solve();
    return 0;
}