题解：P11230 [CSP-J 2024] 接龙（民间数据）
Luogu P11230 [CSP-J 2024] 接龙 Solution
这（蓝）题真真有 S 组的难度了，但是放在 CSP-J T4 的位置来说也没有太超纲。
Update
第一更：2024.10.27 11:35
第二更：2024.10.30 16:35 【修改了引言的一点错误】
第三更：2024.11.9 11:35 【修改了民间数据的题解方法】
题目大意
给定
解法
每次询问恰好有
Step 1 预处理
状态：
Step 2 处理接龙
定义
- 对于每个人输入第
i 个人数字序列的长度，并累加到l[i] 。输入第i 个人的数字序列，并存储到s 数组中。 - 初始化第一轮接龙情况，如果数字为
s ，则dp[0][1] 和dp2[0][该数字下标] 设为\text{true} ，并增加cnt[0][1] 。 - 处理每一轮接龙：对于每个人，减去上一轮这个人对当前状态的影响并遍历这个人的数字序列。如果当前位置减去
k 大于上一个人的累计和，说明超出了长度范围，减去对应的影响，并更新dp[r][s[j]] ，如果tot 大于\text{0} ，表示上一轮有以当前位置数字结尾的接龙方法； - 如果
tot 大于\text{0} ，设置dp2[r][j] 为\text{true} ，表示当前轮有以j 位置数字结尾的接龙方法。增加cnt[r][s[j]] ，表示以当前位置数字结尾的接龙方法数量；增加tot ，表示当前位置数字在本轮接龙中的影响。 - 恢复上一轮这个人对当前状态的影响。
- 处理询问：输出询问结果，即是否存在恰好
r 轮接龙且最后一个数字为c 的情况。
Step 3 调用函数
用一个
注意：本题数据规模较大，注意优化。
代码 【民间数据】
最后贴上code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, R = 1e2 + 10;
bool dp[R][N];
bool dp2[R][N];
int n, k, q, l[N], s[N], cnt[R][N];
void solve(){
memset(dp, 0, sizeof dp);
memset(dp2, 0, sizeof dp2);
memset(cnt, 0, sizeof cnt);
cin >> n >> k >> q;
for (int i = 1; i <= n; i++){
cin >> l[i];
l[i] += l[i - 1];
for (int j = l[i - 1] + 1; j <= l[i]; j++) cin >> s[j];}
for (int i = 1; i <= l[n]; i++)
if (s[i] == 1){
dp[0][1] = dp2[0][i] = 1;
cnt[0][1]++;}
for (int r = 1; r <= 100; r++){
for (int i = 1; i <= n; i++){
for (int j = l[i - 1] + 1; j <= l[i]; j++)
cnt[r - 1][s[j]] -= dp2[r - 1][j];
int tot = 0;
for (int j = l[i - 1] + 1; j <= l[i]; j++){
if (j - k > l[i - 1])
tot -= (cnt[r - 1][s[j - k]] > 0);
dp[r][s[j]] = dp[r][s[j]] || (tot > 0);
if (tot > 0) dp2[r][j] = 1;
cnt[r][s[j]] += dp2[r][j];
tot += (cnt[r - 1][s[j]] > 0);}
for (int j = l[i - 1] + 1; j <= l[i]; j++)
cnt[r - 1][s[j]] += dp2[r - 1][j];}}
while (q--){
int r, c;
cin >> r >> c;
cout << dp[r][c] << endl;}}
signed main(){
//freopen("chain.in", "r", stdin);
//freopen("chain.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
//fclose(stdin);
//fclose(stdout);
return 0;
}