接龙 (CSP-J 2024)

第4题难度一般比前三题高一截，所以准备好使用DP、图算法这些基本工具。这个题达到了蓝题的难度，较有挑战。

本题复杂度要求比较高，因为 $q$ 是 $10^5$ ，所以每一次查询必须是 $\mathcal{O}(1)$ 或者 $\mathcal{O}(\log N)$ 的，这是一个思考的前提。

以下是一个思考的过程：

题目问：每个查询都是 $(r_j,c_j)$ ，表明接龙次数，和最后的数字（开头是 $1$ ），输出“可能”或者“不可能”即可
对每个人，考虑生成一个 $x\rightarrow y$ 的映射表（子串长度 $2$ 到 $k$ ），表明每个开头数字可以生成哪些结尾数字。然后我们发现，这个方法不行，我们把 $xy$ 映射关系画成一张图，边的数量明显是 $N^2$ 的，这个表内存肯定装不下，所以重想别的办法。
我们从数据范围入手，接龙次数 $r \lt 100$ ，其它长度都是 $10^5$ 的，包括： $n$ 人数, $k$ 子串长度, $q$ 查询次数, $l_i$ 每人词库长度, $S_{ij}$ 词编号。 $r$ 小是一个提示。
除了 $r$ 小外，题目有比较明显的多层计算的结构，引导我们想到用DP，比如设定状态为 $dp_{ij}$ ，表示第 $i$ 轮的时候，是否能以数字 $j$ 结尾，那么对于查询 $(r,c)$ ，答案就是 $dp_{rc}$ ，因为轮数 $r \lt 100$ ，而数字最大为 $2\cdot 10^5$ ，所以复杂度 $2\cdot 10^7$ ，可以符合要求。
难点1：初始状态 $dp_{0,1}=1$ 。朴素的办法，每一步都从 $dp_{i-1}$ 中是1的点开始，在图上做扩展。这时我们发现这个图的边特别多，这个扩展的动作会导致整体复杂度变成 $\mathcal{O}(N^2)$ 。
我们观察数据的情况来寻找降低复杂度的办法，有一个条件是 $\sum {l_i} \lt 2\cdot 10^5$ ，从这个可以想到（有难度），我们可以从扩展的终点的角度来进行遍历：将每个人的数字 $a_j$ 从左到右遍历一遍，当碰到一个 $dp_{i-1,a_j}$ 为1的点时，后面 $k-1$ 个数字就是“接龙状态”的数字，设置其 $dp_{ia_j}$ 都是 $1$ 。这样就可以一遍扫描完成 $dp_i$ 的生成。考虑 $\sum {l_i} \lt 2\cdot 10^5$ ，整体复杂度是 $\mathcal{O}(N)$ ，没有问题。
难点2：这时我们发现还有一个障碍，接龙的上轮的人不能和这一轮的人是同一个人。朴素的方法，是需要记录每一个数字上一轮都是哪些人，这个肯定就 $\mathcal{O}(N^2)$ 了。
继续观察，我们发现其实不用记录所有的状态，如果上一轮是一个人 $x$ ，那么这一轮就不能是 $x$ ，但如果上一轮由超过一个人结尾，那么这一轮就可以是任意人。所以我们可以简化这个状态， $dp_{ij}$ 只需要3种状态之一：
- $-1$ 表示第 $i$ 轮没有人以数字 $j$ 结尾
- $0$ 表示超过一个人可以在第 $i$ 轮以数字 $j$ 结尾
- $x$ ( $x > 0$ )表示第 $i$ 轮只有 $x$ 可以以数字 $j$ 结尾。

最后的复杂度基本上就是 $\mathcal{O}(N)$ ，每次查询是 $\mathcal{O}(1)$ 的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t,n,k,q;
int r,c;
vector<int> a[100005];
int l[100005];
int dp[105][200005];
 
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d %d %d", &n, &k, &q);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &l[i]);
            a[i].clear();
            for (int j = 0; j < l[i]; j++) {
                int x;
                scanf("%d", &x);
                a[i].push_back(x);
            }
        }
        // DP precalc
        memset(dp, -1, sizeof(dp));
        dp[0][1] = 0;
        for (r = 1; r <= 100; r++) {        // precalc all rounds
            for (int i = 1; i <= n; i++) {  // precalc all people
                int cnt = 0;
                for (int j = 0; j < a[i].size(); j++) {   // sum l[i] < 2e5, so complexity ok
                    int x = a[i][j];        // current number
                    if (cnt > 0) {          // current number is an ending number
                        if (dp[r][x] == -1) // is first person ending in this?
                            dp[r][x] = i;   // mark this person as the only person ending in x
                        else if (dp[r][x] != i) // more than 1 people ends in x
                            dp[r][x] = 0;
                    }
                    cnt = cnt > 0 ? cnt-1 : 0;
                    if (dp[r-1][x] != -1 && dp[r-1][x] != i)
                        cnt = k-1;          // enter "接龙状态"
                }
            }
        }
 
        // queries
        while (q--) {
            scanf("%d %d", &r, &c);
            printf("%d\n", dp[r][c] != -1);
        }
    }
    return 0;
}