真题解析:P11230 [CSP-J 2024] 接龙(子序列匹配·状态递推·分类讨论)

四季读书网 2026-08-02 08:33:15 2 0

题目来源：洛谷 P11230 [CSP-J 2024] 接龙

题目大意

有 n 个人参加接龙游戏，第 i 个人拥有一个整数序列 A_i。一次游戏进行若干轮，每轮规则如下：

• 每一轮由某一个人 p 接龙。若当前不是第一轮，则 p 不能与上一轮接龙的人相同（可以与更前面的轮次相同）。
• 第 p 个人从自己的序列 A_p 中选出一段长度在 [2, L] 的连续子序列作为本轮的“接龙序列”。
• 第一轮的接龙序列必须以整数 1 开头；第 r（r>1）轮的接龙序列必须以上一轮接龙序列的最后一个整数开头。

现在给出 m 个任务，每个任务给定两个整数 k 和 x，要求判断：是否存在一个恰好进行 k 轮的游戏，使得第 k 轮接龙序列的最后一个整数恰好为 x。

输入输出样例

样例输入 #1

13 3 75 1 2 3 4 13 1 2 53 5 1 61 21 42 43 46 61 17 7

样例输出 #1

第 1 个任务 k=1, x=2：第 1 个人取 [1, 2]，合法。

第 2 个任务 k=1, x=4：第 1 轮必须从 1 开始且长度不超过 3，从任意一个人的序列里都无法直接得到 4，不合法。

第 3 个任务 k=2, x=4：第 2 个人先取 [1, 2]，第 1 个人再取 [2, 3, 4]，两次由不同的人接龙且长度均不超过 3，合法。

考点梳理

• 连续子序列匹配：快速判断“以某个值开头、长度受限”能到达哪些末尾值。
• 状态递推 DP：把游戏过程抽象为“轮数 + 末尾值 + 上一轮玩家”三维状态。
• 去重与玩家互斥：相邻两轮不能由同一个人完成，用 0 / i / -1 三种状态区分唯一玩家、多玩家可行、不可行。
• 分类讨论：首轮必须从头为 1 开始，与后续轮次的转移条件不同，需要分别处理。
• 复杂度控制：k 的上限很小，而值域受总长度限制，可用二维数组 + 差分思想在 O(k · Σ|A_i|) 内预处理。

解题思路

一、关键观察：只关心末尾值与上一轮玩家

一轮接龙结束后，唯一影响后续决策的信息只有两点：

1. 当前轮接龙序列的最后一个整数 v；
2. 本轮由谁接龙 i。

下一轮必须选另一个人 j ≠ i，且 j 的词库中存在一段连续子序列以 v 开头、长度在 [2, L] 之间。因此可以把整个过程看成一张有向图上的状态转移：顶点为 (轮数 r, 末尾值 v, 上轮玩家 i)，边由“连续子序列首尾相接”决定。

由于 k 的范围很小（不超过 100），我们可以直接按轮数递推，而不需要对玩家序列做复杂建图。

二、状态定义

设 f[r][v] 表示“第 r 轮能否以数值 v 结尾”，同时用这个状态值记录“上一轮由谁完成”这一信息：

• f[r][v] = -1：第 r 轮不能以 v 结尾；
• f[r][v] = 0：能以 v 结尾，且至少存在两个不同的人都能完成；
• f[r][v] = i（i > 0）：能以 v 结尾，但所有可行方案中第 r 轮都由第 i 个人完成。

为什么需要区分“唯一玩家”和“多玩家”？因为相邻两轮不能是同一个人。如果第 r-1 轮可以由多个人完成，那么第 r 轮无论选谁，总能避开冲突；如果只能由第 i 个人完成，则第 r 轮必须避开 i。

三、预处理与转移

对每一个人的序列从左到右扫描，维护一个计数器 cnt：它表示“从当前位置往前数，还有多少个数可以作为一个合法起点的延伸末尾”。

具体规则如下：

• 若 cnt > 0，说明当前数值 x 距离某个合法起点不超过 L-1，因此 x 可以作为第 r 轮的结尾。根据当前扫描的是第几个人，更新 f[r][x] 为这个人编号或 0；然后 cnt--。
• 若当前是第 1 轮且 x == 1，则 x 是一个合法起点（第一轮必须从 1 开始），于是 cnt = L - 1，让后面 L-1 个位置都可以成为第 1 轮的结尾。
• 若 f[r-1][x] ≠ -1 且 f[r-1][x] ≠ 当前人编号，说明上一轮以 x 结尾且不是当前这个人完成的，所以当前人可以从 x 开始新的一段接龙，于是 cnt = L - 1。

这里有一个容易忽略的细节：必须先尝试把当前值作为“结尾”使用，再把它作为“新起点”去更新 cnt。因为如果同一个 x 同时是上一轮的结尾和本轮的起点，它只能属于长度 ≥ 2 的新序列，不能自己接自己。

四、查询回答

预处理完 f 数组后，每个任务 (k, x) 只需判断 f[k][x] 是否为 -1：

• 不等于 -1，输出 1；
• 等于 -1，输出 0。

由于多组测试数据，每次都要清空 f 数组和每个人的序列。

参考代码

#include <bits/stdc++.h>using namespace std;const int MAXR = 100;int n, k, q;vector<vector<int>> vseq;vector<vector<int>> dp;void solve(){    cin >> n >> k >> q;    vseq.assign(n + 1, {});    int max_val = 1;    for (int i = 1; i <= n; i++) {        int len;        cin >> len;        vseq[i].resize(len);        for (int j = 0; j < len; j++) {            cin >> vseq[i][j];            max_val = max(max_val, vseq[i][j]);        }    }    // dp[r][j]: -1=不能接, 0=任意行, >=1=只能第 i 人    dp.assign(MAXR + 1, vector<int>(max_val + 1, -1));    dp[0][1] = 0;  // 起始状态    for (int r = 1; r <= MAXR; r++) {        for (int i = 1; i <= n; i++) {            int cnt = 0;            for (int j : vseq[i]) {                if (cnt > 0) {  // j 可作为本轮结尾                    if (dp[r][j] == -1) dp[r][j] = i;                    else if (dp[r][j] != i) dp[r][j] = 0;                    cnt--;                }                if (dp[r - 1][j] != -1 && dp[r - 1][j] != i) {                    cnt = k - 1;  // j 是桥梁，后面 k-1 个数可接                }            }        }    }    while (q--) {        int r, c;        cin >> r >> c;        if (c < (int)dp[r].size())            cout << (dp[r][c] != -1) << '\n';        else            cout << "0\n";    }}int main(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    int T;    cin >> T;    while (T--) solve();    return 0;}

复杂度分析

设单组测试数据中所有序列长度之和为 S，轮数上限为 R（题目中 R ≤ 100），数值范围为 V（V 与 S 同阶，不超过 2×10⁵）。

• 时间复杂度：每一轮扫描所有人的所有元素一次，共 R 轮，所以为 O(R · S)。取 R = 100，S = 2×10⁵，总操作数约为 2×10⁷，在 2 秒时限内可以通过。
• 空间复杂度：f 数组需要 R × V 个整数，约为 100 × 2×10⁵ = 2×10⁷ 个 int，占用约 80 MB；加上所有人的序列，总内存不超过 512 MB 限制。

真题解析:P11230 [CSP-J 2024] 接龙(子序列匹配·状态递推·分类讨论)

题目大意

输入输出样例

考点梳理

解题思路

一、关键观察：只关心末尾值与上一轮玩家

二、状态定义

三、预处理与转移

四、查询回答

参考代码

复杂度分析

推荐阅读