简答题
偏难
#22131
T4 接龙
T4 接龙

答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5, R = 105;
vector<int> s[N];
int n, k, q;
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
dp[0][1] = -2;
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i;
else if (dp[r][tmp] != i)
dp[r][tmp] = -2;
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;
}
}
}
return dp;
}
int main() {
int t;
cin >> t;
while (t--) {
int mx = -1;
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
int l;
cin >> l;
s[i].clear();
s[i].resize(l);
for (int j = 0; j < l; j++) {
cin >> s[i][j];
mx = max(mx, s[i][j]);
}
}
vector<vector<int> > dp = Solve(mx);
while (q--) {
int r, c;
cin >> r >> c;
cout << (dp[r][c] != -1 ? 1 : 0) << endl;
}
}
return 0;
}</pre>
解析
解题思路
本文的解题思想为dp。
dp[r][x]:接龙 r 轮、以 x 结尾的状态:
dp[r][x] = -1:不可实现。
dp[r][x] = i(一个自然数):可以通过词库 i 实现(最后一次接龙操作使用的是词库 i 中的某个连续子序列)。
dp[r][x] = -2:可以通过多个词库实现。
代码解析
完整的求解部分:
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
dp[0][1] = -2;
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i;
else if (dp[r][tmp] != i)
dp[r][tmp] = -2;
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;
}
}
}
return dp;
}逐行分析
mx:所有词库中的最大值,用于构建dp的第二个维度。
dp的大小为R(最大轮数) * mx(所有词库中的最大值)。
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));dp[0][1] = -2:作为虚拟起点,使得第一次接龙可以从数字 1 开始。
dp[0][1] = -2;
r:轮数。
i:尝试让第 i 个人接龙。
j:第 i 个人词库中第 j 个词语。
lst:当前序列 i 中最近一个满足接龙条件的起始位置(可以以lst为起点开始接龙)。
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
}
}
}获取当前人员 i 的词库中第 j 个词语。
如果当前词库中有一个合适的起点可以开始接龙,并且长度合适:
那么选择子序列[lst, j]开始接龙。
更新当前状态。
如果上一轮接龙不是 i 在接龙,并且可以以tmp结束,那么这一轮也可以从tmp开始接龙。
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i; // 首次发现路径则记录序列i
else if (dp[r][tmp] != i)
dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;