A30566. 接龙(chain)
题目描述
接龙(chain)
题目描述
在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。
总共有 n 个人参与这个接龙游戏，第 i 个人会获得一个整数序列 Si 作为他的词库。 一次游戏分为若干轮，每一轮规则如下:
• n 个人中的某个人 p 带着他的词库 Sp 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
• 接龙的人选择一个长度在 [2, k] 的 Sp 的连续子序列 A 作为这一轮的接龙序列， 其中 k 是给定的常数。若这是游戏的第一轮，那么 A 需要以元素 1 开头，否则 A 需要以上一轮的接龙序列的最后一个元素开头。
• 序列 A 是序列 S 的连续子序列当且仅当可以通过删除 S 的开头和结尾的 若干元素(可以不删除)得到 A。
为了强调合作，小 J 给了 n 个参与游戏的人 q 个任务，第 j 个任务需要这 n 个人进行一次游戏，在这次游戏里进行恰好 rj 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 cj。为了保证任务的可行性，小 J 请来你判断这 q 个任务是否可以完成的， 即是否存在一个可能的游戏过程满足任务条件。
输入格式
从文件 chain.in 中读入数据。
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下:
第一行包含三个整数 n, k, q，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。
接下来 n 行:
第i行包含(li +1)个整数li,Si,1,Si,2,··· ,Si,li，其中第一个整数 li 表示序列 Si 的 长度，接下来 li 个整数描述序列 Si。
接下来 q 行:
第 j 行包含两个整数 rj , cj ，描述一个任务。
输出格式
输出到文件 chain.out 中。 对于每个任务:输出一行包含一个整数，若任务可以完成输出 1，否则输出 0。
样例 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 解释
在下文中，我们使用 {Ai} = {A1, A2, · · · , Ar} 表示一轮游戏中所有的接龙序列， {pi} = {p1, p2, · · · , pr} 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了 方便我们直接使用数字字符串表示序列。
对于第一组询问，p1 = 1、A1 = 12 是一个满足条件的游戏过程。
对于第二组询问，可以证明任务不可完成。注意 p1 = 1、A1 = 1234 不是合法的
游戏过程，因为此时 |A1| = 4 > k。
对于第三组询问，{pi} = {2, 1}、{Ai} = {12, 234} 是一个满足条件的游戏过程。
对于第四组询问，可以证明任务不可完成。注意 {pi} = {2, 1, 1}、{Ai} = {12, 23, 34}
不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 k，但第二轮和第三轮由同一个人接龙，不符合要求。
对于第五组询问，{pi} = {1, 2, 3, 1, 2, 3}、{Ai} = {12, 25, 51, 12, 25, 516} 是一个满足条件的游戏过程。
对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 2，因此 A1 = 1 不是一个合法的游戏过程。
对于第七组询问，所有人的词库均不存在字符 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、r ≤ 10、单组测试数据内所有词库的长度和 ≤ 2000、q ≤ 1000。
样例 5
见选手目录下的 chain/chain5.in 与 chain/chain5.ans。
该样例满足特殊性质 B，其中前两组测试数据满足 n ≤ 1000、r ≤ 10、单组测试数据内所有词库的长度和 ≤ 2000、q ≤ 1000。
样例 6
见选手目录下的 chain/chain6.in 与 chain/chain6.ans。
该样例满足特殊性质 C，其中前两组测试数据满足 n ≤ 1000、r ≤ 10、单组测试数据内所有词库的长度和 ≤ 2000、q ≤ 1000。
数据范围
对于所有测试数据，保证:
• 1 ≤ T ≤ 5;
• 1≤n≤105，2≤k≤2×105，1≤q≤105; • 1≤li ≤2×105，1≤Si,j ≤2×105;
• 1≤rj ≤102，1≤cj ≤2×105;
• 设 ∑ l 为单. 组. 测. 试. 数. 据. 内. 所有 li 的和，则 ∑ l ≤ 2 × 105。
特殊性质 A:保证 k = 2 × 105。
特殊性质 B:保证 k ≤ 5。
特殊性质 C:保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 5。
参考答案
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
const int inf = 1 << 30;
const int mod = 998244353;
const int N = 2e5 + 10, M = N << 1;
int T, n, k, q;
int len[N], a[N];
vector<int> s[N], tag[N];
bitset<N> vis[101];
inline void solve() {
cin >> n >> k >> q;
int sumL = 0;
for (int i = 1; i <= n; i++) {
cin >> len[i];
s[i].resize(len[i] + 1);
tag[i].resize(len[i] + 1);
for (int j = 1; j <= len[i]; j++) {
cin >> s[i][j];
if (s[i][j] == 1) tag[i][j] = 1; else tag[i][j] = 0;
}
sumL += len[i];
}
for (int t = 1; t <= 100; t++) {
for (int i = 1; i < N; i++) a[i] = 0, vis[t][i] = 0;
for (int i = 1; i <= n; i++) {
int pre = -k;
for (int j = 1; j <= len[i]; j++) {
if (j - pre + 1 <= k) {
if (!a[s[i][j]]) a[s[i][j]] = i; else if (a[s[i][j]] != i) a[s[i][j]] = -1;
vis[t][s[i][j]] = 1;
}
if (tag[i][j]) pre = j;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= len[i]; j++) {
if (a[s[i][j]] != 0 && a[s[i][j]] != i) tag[i][j] = 1; else tag[i][j] = 0;
}
}
}
for (int i = 1, r, c; i <= q; i++) {
cin >> r >> c;
if (vis[r][c]) cout << "1\n"; else cout << "0\n";
}
}
int main() {
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}