[CSP-J 2024] 接龙
2024年12月25日大约 6 分钟
【5 分】测试点 1
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXCI = 200000; // MAXLI MAXK MAXSIJ
const int MAXR = 100;
int T; // 数据组数
int n, k, q; // n 个人，最长 k 的子序列，q 个任务
vector<int> S[MAXN + 5]; // S[i] 存第 i 个人的词库
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--)
{
cin >> n >> k >> q;
for (int i = 1; i <= n; i++)
{
S[i].clear();
int li, temp;
cin >> li;
for (int j = 1; j <= li; j++)
{
cin >> temp;
S[i].push_back(temp);
}
}
while (q--)
{
int r, c;
cin >> r >> c;
// 能否在 r 轮凑出来 c
bool flag = false;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= (int)S[i].size() - 1; j++)
{
if (S[i][j] != 1)
continue;
for (int jj = j + 1; jj <= (int)S[i].size() - 1; jj++)
{
if (jj - j + 1 > k)
break;
if (S[i][jj] == c)
{
flag = true;
break;
}
}
if (flag)
break;
}
if (flag)
break;
}
cout << flag << "\n";
}
}
return 0;
}【15 分】测试点 1 ~ 3
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXCI = 200000; // MAXLI MAXK MAXSIJ
const int MAXR = 100;
int T; // 数据组数
int n, k, q; // n 个人，最长 k 的子序列，q 个任务
vector<int> S[MAXN + 5]; // S[i] 存第 i 个人的词库
int r, c; // r 轮要凑出来 c
bool flag; // 能否达成
// 当前是第 now 轮
// 上一轮是 last 这个人接的龙
// 上一个人接到了 num，当前需要 num 开头
void dfs(int now, int last, int num)
{
if (flag)
return;
if (now == r + 1)
{
if (num == c)
flag = true;
return;
}
for (int i = 1; i <= n; i++)
{
if (i == last)
continue;
for (int j = 0; j <= (int)S[i].size() - 1; j++)
{
if (S[i][j] != num)
continue;
for (int jj = j + 1; jj <= (int)S[i].size() - 1; jj++)
{
if (jj - j + 1 > k)
break;
dfs(now + 1, i, S[i][jj]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--)
{
cin >> n >> k >> q;
for (int i = 1; i <= n; i++)
{
S[i].clear();
int li, temp;
cin >> li;
for (int j = 1; j <= li; j++)
{
cin >> temp;
S[i].push_back(temp);
}
}
while (q--)
{
cin >> r >> c;
flag = false;
dfs(1, 0, 1);
cout << flag << "\n";
}
}
return 0;
}【70 分】基础 DP
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXCI = 200000; // MAXLI MAXK MAXSIJ
const int MAXR = 100;
int T; // 数据组数
int n, k, q; // n 个人，最长 k 的子序列，q 个任务
vector<int> S[MAXN + 5]; // S[i] 存第 i 个人的词库
// f[i][j]: i 轮由谁达成 j 结尾
// 0：没人能达成
// -1：>= 两个人能达成
// ~：~ 这个人能达成
int f[MAXR + 5][MAXCI + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--)
{
cin >> n >> k >> q;
for (int i = 1; i <= n; i++)
{
S[i].clear();
int li, temp;
cin >> li;
for (int j = 1; j <= li; j++)
{
cin >> temp;
S[i].push_back(temp);
}
}
// 处理 f[][]
f[0][1] = -1;
for (int i = 1; i <= MAXR; i++)
{
// 多测清空
for (int j = 1; j <= MAXCI; j++)
f[i][j] = 0;
// x 这个人可以把 yy 接到 zz
for (int x = 1; x <= n; x++)
{
for (int y = 0; y <= (int)S[x].size() - 1; y++)
{
int yy = S[x][y];
// 上一轮能接到 yy 这一轮才能接到 zz
if (f[i - 1][yy] == 0 ||
f[i - 1][yy] == x)
continue;
for (int z = y + 1; z <= (int)S[x].size() - 1; z++)
{
if (z - y + 1 > k)
break;
int zz = S[x][z];
if (f[i][zz] != 0 && f[i][zz] != x)
f[i][zz] = -1;
else
f[i][zz] = x;
}
}
}
}
while (q--)
{
int r, c;
cin >> r >> c;
cout << (bool)f[r][c] << "\n";
}
}
return 0;
}【100 分】前缀和优化 DP
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXCI = 200000; // MAXLI MAXK MAXSIJ
const int MAXR = 100;
int T; // 数据组数
int n, k, q; // n 个人，最长 k 的子序列，q 个任务
vector<int> S[MAXN + 5]; // S[i] 存第 i 个人的词库
// f[i][j]: i 轮由谁达成 j 结尾
// 0：没人能达成
// -1：>= 两个人能达成
// ~：~ 这个人能达成
int f[MAXR + 5][MAXCI + 5];
// 当前这个人，每个位置的数前一轮能否达成
bool vis[MAXCI + 5];
// vis 对应的前缀和
int sum[MAXCI + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--)
{
cin >> n >> k >> q;
for (int i = 1; i <= n; i++)
{
S[i].clear();
int li, temp;
cin >> li;
for (int j = 1; j <= li; j++)
{
cin >> temp;
S[i].push_back(temp);
}
}
// 处理 f[][]
f[0][1] = -1;
for (int i = 1; i <= MAXR; i++)
{
// 多测清空
for (int j = 1; j <= MAXCI; j++)
f[i][j] = 0;
// x 这个人可以把 yy 接到 zz
for (int x = 1; x <= n; x++)
{
for (int z = 0; z <= (int)S[x].size() - 1; z++)
{
int zz = S[x][z];
// 更新 vis[z]（前一轮能否由别人达成 zz）
if (f[i - 1][zz] == 0 ||
f[i - 1][zz] == x)
vis[z] = 0;
else
vis[z] = 1;
// 更新 sum[z]
if (z == 0)
sum[z] = vis[z];
else
sum[z] = sum[z - 1] + vis[z];
// 判断 f[i][zz] 能否由 x 达成
// 取决于 z 前面 k-1 个位置区间和是否大于 0
int now;
if (z == 0)
now = 0;
else
now = sum[z - 1];
if (z - k >= 0)
now -= sum[z - k];
if (now == 0)
continue;
if (f[i][zz] != 0 && f[i][zz] != x)
f[i][zz] = -1;
else
f[i][zz] = x;
}
}
}
while (q--)
{
int r, c;
cin >> r >> c;
cout << (bool)f[r][c] << "\n";
}
}
return 0;
}【70 分】多个 subtask 合一模式
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 100;
const int MAXN = 100000; // MAXQ=MAXN
const int MAXCI = 200000;
int T; // 数据组数
int n, k, q; // 人数、接龙序列上限、任务个数
int r[MAXN + 5], c[MAXN + 5];
vector<int> s[MAXN + 5];
bool vis[MAXCI + 5]; // vis[i] 能否由 1 走到 i
// ======== 测试点 1 ========
void subtask1()
{
for (int i = 1; i <= MAXCI; i++)
vis[i] = false;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < s[i].size(); j++)
{
if (s[i][j] != 1)
continue;
for (int jj = j + 1;
jj <= min(j + k - 1, (int)s[i].size() - 1);
jj++)
vis[s[i][jj]] = true;
}
}
for (int i = 1; i <= q; i++)
cout << vis[c[i]] << "\n";
}
// ======== 测试点 2,3 ========
bool ok; // 判断当前的 r,c 是否能完成
// 要判断 R 轮能否接到 C
// 当前处理第 now 轮，上一个人是 last
// 上一个结束的数字/这次开始的数字是 num
void dfs(int R, int C, int now, int last, int num)
{
if (ok)
return;
if (now > R)
{
if (num == C)
ok = true;
return;
}
// 进行当前接龙
for (int i = 1; i <= n; i++)
{
if (i == last)
continue;
for (int j = 0; j < s[i].size(); j++)
{
if (s[i][j] != num)
continue;
for (int jj = j + 1;
jj <= min(j + k - 1, (int)s[i].size() - 1);
jj++)
{
int nxt = s[i][jj]; // num 可以由第 i 个人接到 jj
dfs(R, C, now + 1, i, nxt);
}
}
}
}
void subtask2()
{
for (int i = 1; i <= q; i++)
{
ok = false;
dfs(r[i], c[i], 1, 0, 1);
cout << ok << "\n";
}
}
// ======== 70 分 ========
// 第 i 轮，以 j 结尾是谁达成的
// 0：无法达成
// -1：有大于等于两个人达成
// ~： 这个人达成的
int dp[MAXR + 5][MAXCI + 5];
void subtask3()
{
// 预处理 dp
dp[0][1] = -1;
for (int i = 1; i <= MAXR; i++) // MAXR
{
// 清空之前的影响
for (int j = 1; j <= MAXCI; j++)
dp[i][j] = 0;
for (int j = 1; j <= n; j++) // 每个人
{
for (int x = 0; x <= (int)s[j].size() - 1; x++)
{
int xx = s[j][x];
// 第 j 个人可以从 xx 接龙到 yy
// 如果上一轮没法达成 xx ，或者上一轮达成的人就是 j
// 那这一轮无法达成 yy
if (dp[i - 1][xx] == 0 || dp[i - 1][xx] == j)
continue;
for (int y = x + 1; y <= (int)s[j].size() - 1; y++)
{
if (y - x + 1 > k)
break;
int yy = s[j][y];
if (dp[i][yy] == 0 || dp[i][yy] == j)
dp[i][yy] = j;
else
dp[i][yy] = -1;
}
}
}
}
// 输出
for (int i = 1; i <= q; i++)
cout << (bool)dp[r[i]][c[i]] << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--)
{
cin >> n >> k >> q;
for (int i = 1; i <= n; i++)
{
int li, sij;
cin >> li;
s[i].clear();
for (int j = 1; j <= li; j++)
{
cin >> sij;
s[i].push_back(sij);
}
}
bool flag1 = true; // r==1
bool flag2 = true; // r<=5
for (int i = 1; i <= q; i++)
{
cin >> r[i] >> c[i];
if (r[i] != 1)
flag1 = false;
if (r[i] > 5)
flag2 = false;
}
if (flag1)
subtask1();
else if (flag2)
subtask2();
else
subtask3();
}
return 0;
}