题目描述
有 $n$ 个人，每个人都有一个数字序列。有 $q$ 次询问，每次询问给出 $r$ 和 $c$，问是否存在 $r$ 次接龙的方法，使得最后一次接龙的数字是以数字 $c$ 结尾。每一次接龙需要满足下面三个条件：
- 接龙序列一定是某一个人的数字序列中的一段连续子序列
- 接龙序列的长度在 $[2, k]$ 之间
- 不能出现连续两次接龙是同一个人的情况
5分做法
注意到第 $1$ 个测试点 $r = 1$ 的情况，这意味着我们只需要判断 $n$ 个人里面是否存在一个连续子序列以数字 $1$ 开头，并且以数字 $c$ 结尾。我们可以暴力枚举连续子序列的左右端点，判断是否符合要求即可。
注意：在枚举左右端点的过程中需要保证距离不超过 $k$。
单次询问的复杂度为 $O(\sum L \times \min(n, \sum L)$，一共 $q$ 次询问，会超时。使用箱排序预处理，用 ans[c] 表示以数字 $c$ 结尾的连续子序列是否存在，就可以每次 $O(1)$ 地判断 ans[c] 的值来回答询问。
C++ 代码
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> L(n);
vector<vector<int>> a(n);
rep(i, n) {
cin >> L[i];
a[i].resize(L[i]);
rep(j, L[i]) cin >> a[i][j];
}
const int M = 200005;
vector<bool> ans(M);
rep(i, n) {
rep(r, L[i]) {
rep(l, r) {
if (r-l+1 <= k and a[i][l] == 1) ans[a[i][r]] = true;
}
}
}
rep(qi, q) {
int r, c;
cin >> r >> c;
cout << ans[c] << '\n';
}
}
另外10分做法
(dfs暴力搜索)
注意到第 $2$、$3$ 个数据点的小数据范围：$\sum L \leqslant 20$，这提示我们可以使用 $\operatorname{dfs}$ 暴力搜索每一次接龙的结尾是哪个数字，同时还需要枚举一下当前这一次接龙开头的数字是哪一个，判断一下开头的数字是否和上一次接龙结尾的数字相同。
但是我们还需要注意到的一个条件就是：连续两次接龙的人不能是同一个。因此，在 $\operatorname{dfs}$ 的过程中除了需要记录上一次接龙的结尾数字是多少，还需要记录上一次接龙的人是哪一个。
至此，我们可以这样设计暴力搜索的函数去回答每一次询问：bool dfs(int t, int last, int x) 表示进行了 $t$ 次接龙，上一次接龙的人是 $last$，并且上一次接龙结尾的数字是 $x$。
C++ 代码
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> L(n);
vector<vector<int>> a(n);
rep(i, n) {
cin >> L[i];
a[i].resize(L[i]);
rep(j, L[i]) cin >> a[i][j];
}
const int M = 200005;
vector<bool> ans(M);
rep(i, n) {
rep(r, L[i]) {
rep(l, r) {
if (r-l+1 <= k and a[i][l] == 1) ans[a[i][r]] = true;
}
}
}
rep(qi, q) {
int r, c;
cin >> r >> c;
if (r == 1) cout << ans[c] << '\n';
else {
auto dfs = [&](auto& f, int t, int last, int x) -> bool {
if (t == r) return x == c;
rep(i, n) {
if (i == last) continue;
rep(r, L[i]) {
for (int l = r-1; l >= 0; --l) {
if (r-l+1 > k) break;
if (a[i][l] == x and f(f, t+1, i, a[i][r])) return true;
}
}
}
return false;
};
cout << dfs(dfs, 0, -1, 1) << '\n';
}
}
}
另外55分做法
(动态规划、降维、暴力枚举、特殊性质B)
回想一下暴力搜索的过程，如果我们知道第 $t$ 轮，以第 $last$ 个人的数字 $x$ 结尾的方法是存在的，那么对应的我们就能求出第 $t+1$ 轮，以其他人的其他数字结尾的方法。这很明显是一个由“本轮”递推到“下一轮”的过程，有递推的性质，我们就可以尝试往动态规划的方向去思考。
按照 dfs 函数的三个参数，设计出 dp 的状态：dp[r][i][c] 表示第 $r$ 轮接龙以第 $i$ 个人的数字 $c$ 结尾的方法是否存在，这是一个三维的 bool 数组。注意到 $4 \sim 5$、$7 \sim 8$、$11 \sim 12$、$15 \sim 17$ 这 $9$ 个测试点，它们的数据范围：$r \leqslant 10$，$n \leqslant 1000$，但是每个数字的范围最大是 $2e5$，没有足够的空间去定义 dp 数组。
对于第 $1$、$3$ 维，它们对应的是每一次询问给出的 $t$ 和 $c$，因此最好的选择是将第 $2$ 维作为 dp 数组降维后的值。至此，我们可以设计出一个新的 dp 状态：dp[r][c] 表示第 $r$ 轮接龙以数字 $c$ 结尾的是哪一个人。
若 $dp[r][c] = -1$，则表示不存在能够接龙的人
若 $dp[r][c] = i$，则表示能够接龙的人是 $i$，并且是唯一的
若 $dp[r][c] = \infty$，则表示能够接龙的人有两个及以上
接下来，我们需要所有状态对应的 dp 值：枚举 $r$ 表示第几轮接龙，枚举 $i$ 表示第几个人来接龙，枚举这个人的每一个数字 $c$ 表示以它作为接龙结尾的数字，接着再枚举另一个数字 $x$ 表示接龙开头的数字。于是，我们可以得出如下的状态转移方程：
- 当 $dp[r][c] = -1$ 且 $dp[r-1][c] = -1$ 时，$dp[r][c] = -1$
- 当 $dp[r][c] = -1$ 且 $dp[r-1][c] \neq -1$ 时，$dp[r][c] = i$
- 当 $dp[r][c] \neq -1$ 且 $dp[r][c] \neq i$ 且 $dp[r-1][x] \neq -1$ 时，$dp[r][c] = \infty$
注意：如果上一轮接龙的人选如果是同一个人，那么是需要跳过当次转移的！
这个做法的时间复杂度是 $O(r \times \sum L \times \min(k, \sum L))$
代码实现
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> L(n);
vector<vector<int>> a(n);
rep(i, n) {
cin >> L[i];
a[i].resize(L[i]);
rep(j, L[i]) cin >> a[i][j];
}
const int M = 200005;
vector<vector<int>> dp(105, vector<int>(M, -1));
dp[0][1] = n;
for (int t = 1; t <= 100; ++t) {
rep(i, n) {
rep(r, L[i]) {
for (int l = r-1; l >= 0; --l) {
if (r-l+1 > k) break;
int c = a[i][r], x = a[i][l];
if (dp[t-1][x] == i) continue;
if (dp[t][c] == -1) {
if (dp[t-1][x] != -1) {
dp[t][c] = i;
}
}
else if (dp[t][c] != i and dp[t-1][x] != -1) {
dp[t][c] = n;
}
}
}
}
}
rep(qi, q) {
int t, c;
cin >> t >> c;
cout << (dp[t][c] >= 0) << '\n';
}
}
满分做法
(贪心优化暴力枚举、特殊性质A)
到目前为止，动态规划的时间复杂度过高，瓶颈在于我们需要暴力枚举上一轮以哪一个数字为结尾，才能转移到本轮的状态。此时，我们可以关注一下剩余的两个特殊性质 $A$、$C$，看看能够得到什么启发。
特殊性质 $A$：$k = 2e5$，假如我们当前正在求 $dp[r][c]$ 的值，在这个特殊性质 $A$ 的条件下，所有的数字都有机会作为上一轮结尾的数字去转移，这其中只要存在至少一个数字能够满足转移的要求，那么 $dp[r][c]$ 的值必然不会是 $-1$
如此一来，我们就没有必要每次都去暴力枚举上一轮结尾的数字，而是可以用一个变量 cnt 去记录上一轮是否存在那么一个数字能够满足转移的要求，这个变量可以在枚举第 $r$ 轮结尾的数字 $c$ 时顺便去更新。
具体的更新方法如下：依据 $dp[r-1][c]$ 的值，判断上一轮以数字 $c$ 结尾的人是否存在，如果存在并且不是和当前第 $i$ 个人是同一个人，那么就令 $cnt = 1$，否则，$cnt$ 就保持为 $0$
随后，我们便可以依据 $cnt$ 的值来求出 $dp[r][c]$ 的值：若 $cnt = 1$，说明上一轮存在一个方法能够让本轮成功接龙，而因为 $cnt$ 变量的更新方式已经保证了上一轮接龙的人不是同一个人，所以在求 $dp[r][c]$ 的值的时候就没有必要判断了；若 $cnt = 0$，那么说明上一轮并没有满足转移要求的数字，就跳过这一次转移。
如此一来，就可以利用特殊性质 $A$ 来将保留枚举的复杂度优化掉。
但如果没有特殊性质 $A$ 呢？这样的话每一次接龙序列的长度不能超过 $k$，若一个数字能够作为上一轮结尾的数字，假设它的位置是 $i$，那么它能够给后面至多 $k-1$ 个位置提供转移机会。
按照贪心的策略，我们肯定是希望每次转移的时候，拥有的转移机会尽可能多，这样一来留给后面位置的转移机会也就更多。我们可以把 $cnt$ 重新表示为剩余的转移机会有多少个，于是，在枚举本轮数字 $c$ 的时候，当我们发现数字 $c$ 在上一轮能够作为结尾，并且符合转移的要求，那么就把转移机会 $cnt$ 重新赋值为 $k$
至此，我们从特殊性质 $A$ 中受到启发，将暴力枚举上一轮结尾数字的复杂度通过贪心的策略给省去了。
整体时间复杂度为 $O(r \times \sum L)$
代码实现
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<int> L(n);
vector<vector<int>> a(n);
rep(i, n) {
cin >> L[i];
a[i].resize(L[i]);
rep(j, L[i]) cin >> a[i][j];
}
const int M = 200005;
vector<vector<int>> dp(101, vector<int>(M, -1));
dp[0][1] = n;
for (int t = 1; t <= 100; ++t) {
rep(i, n) {
int cnt = 0;
rep(r, L[i]) {
int c = a[i][r];
if (--cnt > 0) {
if (dp[t][c] == -1) {
dp[t][c] = i;
}
else if (dp[t][c] != i) {
dp[t][c] = n;
}
}
if (dp[t-1][c] != -1 and dp[t-1][c] != i) cnt = k;
}
}
}
rep(qi, q) {
int t, c;
cin >> t >> c;
cout << (dp[t][c] >= 0) << '\n';
}
}
