接龙题解

zxcvbnm

2025-08-17 18:11:38

发布于：上海

3阅读

0回复

0点赞

T4 接龙

1 题目大意

有 $n$ 个同学，每人一行“数字表”（一串整数）。
一共接 $r$ 轮。每一轮一个同学在自己那一行里，选一段连续子串，长度在 $[2,k]$ 。
第一轮这段必须“以 1 开头”；之后每一轮这段必须“以上一轮的结尾数字开头”。
相邻两轮不能是同一个同学出手。
问很多次：给定 $(r,c)$ ，能不能恰好接 $r$ 轮，且第 $r$ 轮的最后一个数字是 $c$ ？

2 解题思路

状态定义：
- dp[r][j] 表示在第 r 轮能否以数字 j 作为结尾。
- dp[r][j] 的取值：
  - -1：不能接龙。
  - 0：可以从任意行接龙。
  - i：上一轮由第 i 个人接龙。
预处理：
- 初始化 dp[0][1] = 0，表示第一轮可以从 1 开始。
- 对于每一轮 r，遍历每个人 i 的词库：
  - 维护一个计数器 cnt，表示当前可以接龙的数字个数。
  - 遍历词库中的每个数字 now：
    - 如果 cnt > 0，则 now 可以作为接龙的结尾，更新 dp[r][now]。
    - 如果 dp[r-1][now] 不为 -1 且上一轮不是 i，则设置 cnt = k - 1，表示接下来的 k-1 个数字可以作为接龙的结尾。
查询处理：
- 对于每个查询 (r, c)，检查 dp[r][c] 是否为 -1，输出 1 或 0。

3 难点与核心想法

难点有两个：

既要看“数能不能接上”，还要看“相邻两轮不能同一个人”；
查询多，需要一次预处理，之后 $O(1)$ 回答。

核心想法是做一张“可达数字表”，按轮数一层一层推：

设 $dp[r][x]$ $d p [r] [x]$ 表示“接到第 $r$ $r$ 轮时，以数字 $x$ 结尾的情况”，并且用取值记录“上一轮是谁”：
- $-1$ ：不可达；
- $i$ ：只知道必须由第 $i$ 个人把 $x$ 接出来（否则会违背相邻不同人）；
- $0$ ：有人能，也不止一个人能（“任意人可接”状态，方便下一轮规避同人）。
初始化： $dp[0][1]=0$ ，表示“第 0 轮相当于已经在数字 1 上（不限谁）”。让 $dp[0][1]=0$ 是为了保证“第一轮以1开头的时候”任何人都能接。

为什么要记录“上一轮是谁”？

相邻两轮不能同一个人。如果上一层把 $x$ 接到手上的只有人 $i$ ，那下一层人 $i$ 就不能从 $x$ 开始；
如果上一层把 $x$ 能由至少两个人接到（记成 $0$ ），那下一层无论你选谁，总能挑到“与上一轮不同的人”。（比如第三轮3号和4号都可以接，那么第四轮需要3号接的时候，可以使用第三轮4号接的情况；第四轮需要4号接的时候，可以使用第三轮3号接的情况。因此第r轮只要不止一个人能接，第r+1轮就可以让任何人接。）

“ $cnt$ ” 是什么？（滑窗计数）

在代码中，cnt 是一个计数器，用于记录当前可以接龙的数字个数。具体来说，cnt 的作用如下：

表示可接龙的数字个数：
- cnt 的值表示当前数字 u 之后还有多少个数字可以作为接龙的结尾。
- 例如，如果 cnt = 3，则表示接下来的 3 个数字可以作为接龙的结尾。
控制接龙序列的长度：
- 题目要求接龙序列的长度必须在 [2, k] 之间。
- 当遇到一个可以作为接龙起点的数字 now 时，设置 cnt = k - 1，表示接下来的 k - 1 个数字都可以作为接龙的结尾数字。
- 这样，接龙序列的最长长度就是 k（起点 u 加上 k - 1 个后续数字）。
更新 dp 状态：
- 如果 cnt > 0，说明当前数字 now 可以作为接龙的结尾。
- 更新 dp[r][now]：
  - 如果now是第一次被接龙，设置为当前人 i。
  - 如果不是第一次被接龙，设置为 0（代表“有人能且不止一人能”）。
- 每次更新后，cnt 减 1，表示已经处理了一个接龙的数字。

4 小例子手推（ $k=3$ ）

假设 k = 3，当前人 i 的词库为 [a, b, c, d, e]，且 dp[r-1][a] != -1 且 dp[r-1][a] != i：

遍历到 a：
- dp[r-1][a] 有效，且上一轮不是 i，因此设置 cnt = k - 1 = 2。
- 表示接下来的 2 个数字可以作为接龙的结尾。
遍历到 b：
- cnt = 2 > 0，因此 b 可以作为接龙的结尾。
- 更新 dp[r][b]：
  - 如果是第一次被接龙，设置为 i。
  - 否则设置为 0。
- cnt 减 1，变为 1。
遍历到 c：
- cnt = 1 > 0，因此 c 可以作为接龙的结尾。
- 更新 dp[r][c]。
- cnt 减 1，变为 0。
遍历到 d 和 e：
- cnt = 0，不处理。

这样，a 可以作为接龙的起点，b 和 c 可以作为接龙的结尾，形成长度为 2 或 3 的接龙序列。

5 复杂度

设所有行的总长度为 $M$ （全部数字个数之和）。
我们做 $r=1\sim 100$ 层，每层把所有行扫一遍：时间 $O(100\cdot M)$ ；

6 代码

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

// N：数字值域
// R：最大询问轮数（题面里 <= 100）
const int N = 2e5 + 5;
const int R = 100 + 5;

int n, k, q;
int dp[R][N];          // dp[r][j] 表示在第 r 轮能否以数字 j 作为结尾
vector <int> word[N];    //word[i]表示第i个人的词库
int T;

int main() {

    cin >> T;
    while (T--) {
        cin >> n >> k >> q;

        for(int i = 1; i <= n; i ++){
            int l;
            cin >> l;
            word[i].clear();  // 清空旧数据
            for(int j = 0; j < l; j ++){
                int x;
                cin >> x;
                word[i].push_back(x);
            }
    }

        // 预处理dp
        memset(dp, -1, sizeof(dp)); //一开始所有情况都不能接龙
        dp[0][1] = 0; // 第一轮一定从1开始
        
        for(int r = 1; r <= 100; r ++){ // 枚举轮数
            for(int i = 1; i <= n; i ++){ // 枚举当前轮要接的人
                int cnt = 0; // 记录还有多少个可以作为接龙结尾的数
                for (int j = 0; j < word[i].size(); ++j) {// 遍历第i个人的词库
                    int now = word[i][j];
                    //先消耗掉上一轮的cnt情况
                    if (cnt > 0) {
                        // now 作为“本轮结尾”可达
                        if (dp[r][now] == -1) dp[r][now] = i;   // 首次由 i 人标记
                        else if (dp[r][now] != i) dp[r][now] = 0; // 多人可达，置 0
                        --cnt;
                    }
                    //再更新cnt，两个if顺序不能换
                    // 若上一轮允许以 now 结尾，且上一轮不是 i 接的
                    if (dp[r - 1][now] != -1 && dp[r - 1][now] != i) {
                        //那么这一轮可以以now开头
                        cnt = k - 1; // now 接下来的 k-1 个位置都可作结尾
                    }

                    
                }
            }
        }

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