题解：P11230 [CSP-J 2024] 接龙（暂无数据）

· · 题解

特别难的题！

思路

我们把所有人的序列依次排列成的一个序列设为 a，设第 i 个人的序列对应长序列中的 L_i\sim R_i 这一段。

当我们看到 r_j\le100，可以用动态规划，设 f_{i,t} 表示当前为第 i 轮，结束位置是 t 的方案数答案就是 F(f_{r_j,c_j})，其中当 f_{r_j,c_j}>0 函数返回 1，反之返回 0。然而转移需要枚举上一轮的结束点，再检查是否有合法的起始点，这样复杂度至少也要 O(m^2r)，其中 m=\sum l_i。

我们可以把一轮接龙的过程分成两步：先选择一个和上一次接龙未尾数字相同的起始点，在选择一个满足是同一个人，且位置相差在 2\sim k 之间的结束点。

这样，我们发现，第一步只和每个位置上的数字有关，而第二步只和位置有关。因此我们可以把转移分成两步，先根据上一轮的 f，计算出合法的起始点，再根据起始点，转移到结束点。

我们再设 g_{i,s} 表示第 i 轮，结束的位置数字为 s 的方案数。则我们可以在求完 f_{i-1} 后直接计算出函数 g。

现在我们想如何利用 g_{i-1}，计算出 f_i。如果没有两轮接龙不能使用同一个人的序列，则我们发现，

f_{i,t}=\sum_{l_t\le j\le t-1}g_{i-1,a_j}

其中 l_t 是 t-k+1 和 t 对应的小序列的第一项较大值，因为 l_t 是单调的，所以利用一个指针，同时记录区间和就可以快速求出 f_{i,t}。

但是题目要求两轮接龙不能使用同一个人的序列，而 g 并没有考虑结束的位置属于哪一个人的序列，因此我们需要把两轮接龙相同的人的方案数减掉。考虑这个限制后，新的转移方程为：

f_{i,t}=\sum_{l_t\le j\le t-1}(g_{i-1,a_j}-\sum_{L_{B_t}\le b\le R_{B_t},a_b=a_j}f_{i-1,b})

其中 B_t 表示 t 属于哪一个人的序列，而 \sum_{L_{B_t}\le b\le R_{B_t},a_b=a_j}f_{i-1,b} 可以求出在 f_{i-1} 后的东西。通过维护数组 pre_i 表示上一个 a_j=a_i 的位置 j 快速计算求出。

综上我们可以在 O(mr) 的时间复杂度通过此题，但此题要开 long long。

代码

#include <bits/stdc++.h>
#define N 200100
#define M 110
using namespace std;

int T, n, K, Q, ok[M][N];
vector<int> num[N];

int main()
{
    cin >> T;
    while (T--)
    {
        memset(ok, -1, sizeof(ok));
        scanf("%d%d%d", &n, &K, &Q);
        for (int i = 1; i <= n; i++)
        {
            num[i].clear();
            int len;
            scanf("%d", &len);
            for (int j = 1; j <= len; j++)
            {
                int t;
                scanf("%d", &t);
                num[i].push_back(t);
            }
        }

        ok[0][1] = 0;
        for (int T = 1; T <= 100; T++)
        {
            for (int i = 1; i <= n; i++)
            {
                int len = 0;
                for (auto t : num[i])
                {
                    len = max(len - 1, 0);
                    if (len)
                    {
                        if (ok[T][t] == -1)
                            ok[T][t] = i;
                        else if (ok[T][t] && ok[T][t] != i)
                            ok[T][t] = 0;
                    }
                    if (ok[T - 1][t] != -1 && ok[T - 1][t] != i)
                        len = K;
                }
            }
        }
        while (Q--)
        {
            int p, q;
            scanf("%d%d", &p, &q);
            puts(ok[p][q] != -1 ? "1" : "0");
        }
    }
}//update:2024.10.29