[CSP-J 2024] 接龙（官方数据）
题目描述
在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。
总共有 n n n 个人参与这个接龙游戏，第 i i i 个人会获得一个整数序列 S i S_i Si 作为他的词库。
一次游戏分为若干轮，每一轮规则如下：
- n n n 个人中的某个人 p p p 带着他的词库 S p S_p Sp 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
- 接龙的人选择一个长度在
[
2
,
k
]
[2, k]
[2,k] 的
S
p
S_p
Sp 的连续子序列
A
A
A 作为这一轮的接龙序列，其中
k
k
k 是给定的常数。若这是游戏的第一轮，那么
A
A
A 需要以元素
1
1
1 开头，否则
A
A
A 需要以上一轮的接龙序列的最后一个元素开头。
- 序列 A A A 是序列 S S S 的连续子序列当且仅当可以通过删除 S S S 的开头和结尾的若干元素（可以不删除）得到 A A A。
为了强调合作，小 J 给了 n n n 个参与游戏的人 q q q 个任务，第 j j j 个任务需要这 n n n 个人进行一次游戏，在这次游戏里进行恰好 r j r_j rj 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 c j c_j cj。为了保证任务的可行性，小 J 请来你判断这 q q q 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 T T T，表示数据组数。
接下来包含 T T T 组数据，每组数据的格式如下：
第一行包含三个整数 n , k , q n, k, q n,k,q，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。
接下来 n n n 行：
第 i i i 行包含 ( l i + 1 ) (l_i + 1) (li+1) 个整数 l i , S i , 1 , S i , 2 , … , S i , l i l_i, S_{i,1}, S_{i,2}, \dots , S_{i,l_i} li,Si,1,Si,2,…,Si,li，其中第一个整数 l i l_i li 表示序列 S i S_i Si 的长度，接下来 l i l_i li 个整数描述序列 S i S_i Si。
接下来 q q q 行：
第 j j j 行包含两个整数 r j , c j r_j, c_j rj,cj，描述一个任务。
输出格式
对于每个任务：输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。
样例 #1
样例输入 #1
1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 4
3 4
6 6
1 1
7 7
样例输出 #1
1
0
1
0
1
0
0
提示
【样例 1 解释】
在下文中，我们使用 { A i } = { A 1 , A 2 , … , A r } \{A_i\} = \{A_1, A_2, \dots , A_r\} {Ai}={A1,A2,…,Ar} 表示一轮游戏中所有的接龙序列， { p i } = { p 1 , p 2 , … , p r } \{p_i\} = \{p_1, p_2, \dots , p_r\} {pi}={p1,p2,…,pr} 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。
- 对于第一组询问， p 1 = 1 p_1 = 1 p1=1、 A 1 = 12 A_1 = 12 A1=12 是一个满足条件的游戏过程。
- 对于第二组询问，可以证明任务不可完成。注意 p 1 = 1 p_1 = 1 p1=1、 A 1 = 1234 A_1 = 1234 A1=1234 不是合法的游戏过程，因为此时 ∣ A 1 ∣ = 4 > k |A_1| = 4 > k ∣A1∣=4>k。
- 对于第三组询问， { p i } = { 2 , 1 } \{p_i\} = \{2, 1\} {pi}={2,1}、 { A i } = { 12 , 234 } \{A_i\} = \{12, 234\} {Ai}={12,234} 是一个满足条件的游戏过程。
- 对于第四组询问，可以证明任务不可完成。注意 { p i } = { 2 , 1 , 1 } 、 { A i } = { 12 , 23 , 34 } \{p_i\} = \{2, 1, 1\}、\{A_i\} = \{12, 23, 34\} {pi}={2,1,1}、{Ai}={12,23,34} 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 k k k，但第二轮和第三轮由同一个人接龙，不符合要求。
- 对于第五组询问， { p i } = { 1 , 2 , 3 , 1 , 2 , 3 } \{p_i\} = \{1, 2, 3, 1, 2, 3\} {pi}={1,2,3,1,2,3}、 { A i } = { 12 , 25 , 51 , 12 , 25 , 516 } \{A_i\} = \{12, 25, 51, 12, 25, 516\} {Ai}={12,25,51,12,25,516} 是一个满足条件的游戏过程。
- 对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 2 2 2，因此 A 1 = 1 A_1 = 1 A1=1 不是一个合法的游戏过程。
- 对于第七组询问，所有人的词库均不存在字符 7 \tt 7 7，因此任务显然不可完成。
【样例 2】
见选手目录下的 chain/chain2.in 与 chain/chain2.ans。
该样例满足测试点 1 的特殊性质。
【样例 3】
见选手目录下的 chain/chain3.in 与 chain/chain3.ans。
该样例满足测试点 2 的特殊性质。
【样例 4】
见选手目录下的 chain/chain4.in 与 chain/chain4.ans。
该样例满足特殊性质 A，其中前两组测试数据满足 n ≤ 1000 n \leq 1000 n≤1000、 r ≤ 10 r \leq 10 r≤10、单组测试数据内所有词库的长度和 ≤ 2000 \leq 2000 ≤2000、 q ≤ 1000 q \leq 1000 q≤1000。
【样例 5】
见选手目录下的 chain/chain5.in 与 chain/chain5.ans。
该样例满足特殊性质 B，其中前两组测试数据满足 n ≤ 1000 n \leq 1000 n≤1000、 r ≤ 10 r \leq 10 r≤10、单组测试数据内所有词库的长度和 ≤ 2000 \leq 2000 ≤2000、 q ≤ 1000 q \leq 1000 q≤1000。
【样例 6】
见选手目录下的 chain/chain6.in 与 chain/chain6.ans。
该样例满足特殊性质 C，其中前两组测试数据满足 n ≤ 1000 n \leq 1000 n≤1000、 r ≤ 10 r \leq 10 r≤10、单组测试数据内所有词库的长度和 ≤ 2000 \leq 2000 ≤2000、 q ≤ 1000 q \leq 1000 q≤1000。
【数据范围】
对于所有测试数据，保证：
- 1 ≤ T ≤ 5 1 \leq T \leq 5 1≤T≤5；
- 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105， 2 ≤ k ≤ 2 × 1 0 5 2 \leq k \leq 2 \times 10^5 2≤k≤2×105， 1 ≤ q ≤ 1 0 5 1 \leq q \leq 10^5 1≤q≤105；
- 1 ≤ l i ≤ 2 × 1 0 5 1 \leq l_i \leq 2 \times 10^5 1≤li≤2×105， 1 ≤ S i , j ≤ 2 × 1 0 5 1 \leq S_{i,j} \leq 2 \times 10^5 1≤Si,j≤2×105；
- 1 ≤ r j ≤ 1 0 2 1 \leq r_j \leq 10^2 1≤rj≤102， 1 ≤ c j ≤ 2 × 1 0 5 1 \leq c_j \leq 2 \times 10^5 1≤cj≤2×105；
- 设 ∑ l \sum l ∑l 为单组测试数据内所有 l i l_i li 的和，则 ∑ l ≤ 2 × 1 0 5 \sum l\leq 2\times 10^5 ∑l≤2×105。
| 测试点 | n ≤ n\leq n≤ | r ≤ r\leq r≤ | ∑ l ≤ \sum l\leq ∑l≤ | q ≤ q\leq q≤ | 特殊性质 |
|---|---|---|---|---|---|
| 1 1 1 | 1 0 3 10^3 103 | 1 1 1 | 2000 2000 2000 | 1 0 3 10^3 103 | 无 |
| 2 , 3 2,3 2,3 | 10 10 10 | 5 5 5 | 20 20 20 | 1 0 2 10^2 102 | 无 |
| 4 , 5 4,5 4,5 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | A |
| 6 6 6 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | A |
| 7 , 8 7,8 7,8 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | B |
| 9 , 10 9,10 9,10 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | B |
| 11 , 12 11,12 11,12 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | C |
| 13 , 14 13,14 13,14 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | C |
| 15 ∼ 17 15\sim 17 15∼17 | 1 0 3 10^3 103 | 10 10 10 | 2000 2000 2000 | 1 0 3 10^3 103 | 无 |
| 18 ∼ 20 18\sim 20 18∼20 | 1 0 5 10^5 105 | 1 0 2 10^2 102 | 2 × 1 0 5 2\times 10^5 2×105 | 1 0 5 10^5 105 | 无 |
特殊性质 A：保证 k = 2 × 1 0 5 k = 2 \times 10^5 k=2×105。
特殊性质 B：保证 k ≤ 5 k ≤ 5 k≤5。
特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 5 5 5。
容易发现是图论题，建模就是每个位置往他能接的位置连边，于是不妨先考虑给定一个一般的有向图怎么做。简单的想法是预处理出所有答案，你可以用一个类似广搜的东西，从 111 开始每次向外拓展一层，记录可达性即可，复杂度是 O(nr)O(nr)O(nr) 的。
但是这题的图边数特别多，那我们干脆不建边了，直接去判断每个点能否被当前的点到达。每次记录的就是当前接龙的最后一个数。
题目有个很烦的限制，一个人不能接两次。但是可以发现，如果当前这一层的某个数 xxx 同时在至少两个人的序列里，那么所有人的数 xxx 都能接到下一个了。所以只要考虑只有一个人有 xxx 的情况。开个数组记录这一层的每个数在谁手上，没有为 −1-1−1，有一个人 iii 有就设为 iii，两个人及以上有设为 000。这样处理后就可以快速找出可以接到哪些位置上了。
然后再通过这些新接的头找出所有能接的尾巴。先对所有头打标记，然后遍历每一个位置，如果他距离上一个标记（不含自己）的距离 ≤k\le k≤k 就加入下一层的队列。重复做这个就好了，单组数据复杂度 O(nr+q)O(nr+q)O(nr+q)。
AC 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
const int MAXM = 1e2 + 10;
inline
void read(int &x) {
x = 0; char c = getchar();
for (; isspace(c); c = getchar());
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
}
int T, n, m, q; int cnt[MAXN]; bool ans[MAXM][MAXN];
int a[MAXN]; bool vis[MAXN]; int pos[MAXN];
inline
void init() {
vector<pair<int, int>> f, g;
for (int i = 1; i <= n; i++) {
for (int j = pos[i], p = -1e9; j < pos[i + 1]; j++) {
if (j - p < m) f.emplace_back(i, j), ans[1][a[j]] = 1;
if (a[j] == 1) p = j;
}
}
for (int t = 2; t <= 100; t++) {
memset(cnt, 0xff, sizeof cnt);
for (pair<int, int> x : f) {
int y = a[x.second];
if (cnt[y] == -1) cnt[y] = x.first;
else if (cnt[y] != x.first) cnt[y] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = pos[i]; j < pos[i + 1]; j++) {
if (~cnt[a[j]] && cnt[a[j]] != i) g.emplace_back(i, j);
}
}
f.clear();
for (pair<int, int> x : g) vis[x.second] = 1;
for (int i = 1; i <= n; i++) {
for (int j = pos[i], p = -1e9; j < pos[i + 1]; j++) {
if (j - p < m) f.emplace_back(i, j), ans[t][a[j]] = 1;
if (vis[j]) p = j;
}
}
for (pair<int, int> x : g) vis[x.second] = 0;
g.clear();
}
}
int main() {
freopen("chain.in", "r", stdin);
freopen("chain.out", "w", stdout);
for (read(T); T--; ) {
read(n), read(m), read(q);
memset(ans, 0, sizeof ans);
memset(vis, 0, sizeof vis);
for (int i = 1, k; i <= n; i++) {
read(k), pos[i + 1] = pos[i] + k;
for (int j = pos[i]; j < pos[i + 1]; j++) read(a[j]);
}
// clock_t st = clock();
init();
// fprintf(stderr, "init time: %.3lfs\n", (double)(clock() - st) / CLOCKS_PER_SEC);
for (int r, c; q--; read(r), read(c), printf("%d\n", ans[r][c]));
}
}思路：
容易发现是动态规划题，状态是 dpk,i,jdp_{k, i, j}dpk,i,j 表示在 kkk 轮第 iii 个人是否可以出以第 jjj 张牌结尾的接龙序列，然后考虑状态转移方程：
dpk,i,j=⋁[l≠i&al,p∈Si,j−k+1,j]dpk−1,l,pdp_{k,i,j} = \bigvee [l \ne i \& a_{l,p} \in S_{i, j - k + 1,j}] dp_{k -1, l, p}dpk,i,j=⋁[l=i&al,p∈Si,j−k+1,j]dpk−1,l,p其中 Si,l,rS_{i, l, r}Si,l,r 表示 ai,l⋯ra_{i, l \cdots r}ai,l⋯r 这些数构成的集合。
然后考虑令：
sk,x=∑i=1n∑j=1leni[ai,j=x]dpk,i,jgk,i,x=∑j=1leni[ai,j=x]dpk,i,js_{k, x} = \sum_{i = 1}^n \sum_{j = 1} ^{len_i} [a_{i, j} = x] dp_{k,i,j} \\ g_{k, i, x} = \sum_{j = 1} ^{len_i} [a_{i, j} = x] dp_{k,i,j}sk,x=i=1∑nj=1∑leni[ai,j=x]dpk,i,jgk,i,x=j=1∑leni[ai,j=x]dpk,i,j则状态转移方程优化为：
dpk,i,j=⋁[sk−1,al,p≠gk−1,i,al,p](al,p∈Si,j−k+1,j)dp_{k, i, j} = \bigvee [s_{k - 1, a_{l,p}} \ne g_{k - 1, i, a_{l,p}} ] (a_{l,p} \in S_{i, j - k + 1,j})dpk,i,j=⋁[sk−1,al,p=gk−1,i,al,p](al,p∈Si,j−k+1,j)然后可以走指针优化一下，就可以实现 O(1)O(1)O(1) 转移了，时间复杂度为 O(q+nr)O(q + nr)O(q+nr)。
考场代码：
#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define mkp(x, y) make_pair(x, y)
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, M = 105;
inline ll read(){
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
inline void write(ll x){
if(x < 0){
putchar('-');
x = -x;
}
if(x < 10){
putchar('0' + x);
return ;
}
write(x / 10);
write(x % 10);
return ;
}
int T, n, m, q, r, c, cnt, Max;
int len[N], h[N], f[N], s[N];
bool F[M][N];
vector<int> a[N], id[N], g[N];
vector<bool> dp[N];
void solve(){
Max = 0;
n = read(), m = read(), q = read();
for(int i = 1; i <= n; ++i){
cnt = 0;
a[i].clear(), g[i].clear(), id[i].clear(), dp[i].clear();
len[i] = read();
for(int j = 0; j < len[i]; ++j){
a[i].push_back(read());
h[++cnt] = a[i][j];
Max = max(Max, a[i][j]);
}
sort(h + 1, h + cnt + 1);
cnt = unique(h + 1, h + cnt + 1) - (h + 1);
for(int j = 0; j < len[i]; ++j)
id[i].push_back(lower_bound(h + 1, h + cnt + 1, a[i][j]) - (h + 1));
dp[i].resize(len[i]);
g[i].resize(len[i]);
}
for(int i = 1; i <= Max; ++i){
s[i] = 0;
for(int j = 1; j <= 100; ++j)
F[j][i] = 0;
}
for(int i = 1; i <= n; ++i){
for(int j = 0; j < len[i]; ++j){
if(j - m >= 0)
--f[a[i][j - m]];
if(j && f[1]){
F[1][a[i][j]] = dp[i][j] = 1;
++s[a[i][j]];
++g[i][id[i][j]];
}
++f[a[i][j]];
}
for(int j = 0; j < len[i]; ++j)
f[a[i][j]] = 0;
}
for(int k = 2; k < M; ++k){
for(int i = 1; i <= n; ++i){
int sum = 0;
for(int j = 0; j < len[i]; ++j){
dp[i][j] = 0;
if(j - m >= 0){
--f[a[i][j - m]];
if(!f[a[i][j - m]]){
if(s[a[i][j - m]] != g[i][id[i][j - m]])
--sum;
}
}
dp[i][j] = (sum >= 1);
if(!f[a[i][j]]){
if(s[a[i][j]] != g[i][id[i][j]])
++sum;
}
++f[a[i][j]];
}
for(int j = 0; j < len[i]; ++j)
f[a[i][j]] = 0;
}
for(int i = 0; i < N; ++i)
s[i] = 0;
for(int i = 1; i <= n; ++i){
for(int j = 0; j < len[i]; ++j)
g[i][j] = 0;
for(int j = 0; j < len[i]; ++j){
if(dp[i][j]){
F[k][a[i][j]] = 1;
++s[a[i][j]];
++g[i][id[i][j]];
}
}
}
}
while(q--){
r = read(), c = read();
if(F[r][c])
puts("1");
else
puts("0");
}
}
int main(){
// fin("chain.in"), fout("chain.out");
T = read();
while(T--)
solve();
return 0;
}