P11230 [CSP-J 2024] 接龙（官方数据） 题解

aaa_lvzekai · 2024-11-23 16:27:11 · 个人记录

题目介绍

有 n 个人，第 i 个人有一个整数序列 S_i 作为他的词库。

一次游戏分为 t 轮，每一轮规则如下：

• 若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
• 接龙的人选择一个长度在 [2, k] 的 S_i 的连续子序列 A 作为这一轮的接龙序列。若这是游戏的第一轮，那么 A 需要以元素 1 开头，否则 A 需要以上一轮的接龙序列的最后一个元素开头。
• 序列 A 是序列 S 的连续子序列当且仅当可以通过删除 S 的开头和结尾的若干元素（可以不删除）得到 A。
• 有 q 次询问，每次询问包括两个参数 (r,c)，表示询问是否存在一个 r 轮的接龙游戏，满足最后一次接龙的 A 以数字 c 结尾。

样例

样例输入

1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 4
3 4
6 6
1 1
7 7

样例输出

1
0
1
0
1
0
0

提示

【样例 1 解释】

在下文中，我们使用 \{A_i\} = \{A_1, A_2, \dots , A_r\} 表示一轮游戏中所有的接龙序列，\{p_i\} = \{p_1, p_2, \dots , p_r\} 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。

• 对于第一组询问，p_1 = 1、A_1 = 12 是一个满足条件的游戏过程。
• 对于第二组询问，可以证明任务不可完成。注意 p_1 = 1、A_1 = 1234 不是合法的游戏过程，因为此时 |A_1| = 4 > k。
• 对于第三组询问，\{p_i\} = \{2, 1\}、\{A_i\} = \{12, 234\} 是一个满足条件的游戏过程。
• 对于第四组询问，可以证明任务不可完成。注意 \{p_i\} = \{2, 1, 1\}、\{A_i\} = \{12, 23, 34\} 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 k，但第二轮和第三轮由同一个人接龙，不符合要求。
• 对于第五组询问，\{p_i\} = \{1, 2, 3, 1, 2, 3\}、\{A_i\} = \{12, 25, 51, 12, 25, 516\} 是一个满足条件的游戏过程。
• 对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 2，因此 A_1 = 1 不是一个合法的游戏过程。
• 对于第七组询问，所有人的词库均不存在字符 \tt 7，因此任务显然不可完成。

【数据范围】

对于所有测试数据，保证：

• 设 \sum l 为单组测试数据内所有 l_i 的和，则 \sum l\leq 2\times 10^5。

特殊性质 A：保证 k = 2 \times 10^5。

特殊性质 B：保证 k ≤ 5。

特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 5。

原题链接

100pts 思路讲解

算法：动态规划

时间复杂度：O(n)

通过搜索可以拿 25 分，可以考虑运用记忆化搜索来优化程序效率，进而可以想到从动态规划的角度思考这道题的解法。

对于第 j 个数字序列 S_j ，将其长度记为 len_j。不妨认为 S_j 的下标范围为 0 \sim len_j-1。

我们定义状态 dp_{i,j,t} 表示在第 i 轮中，能否以第 j 个数字序列的第 t 个位置作为起点（其中第 2 维和第 3 维的状态总数不超过 \sum len = 200,000）。

定义状态 f_{i,j,t} 表示在第 i 轮中，能否以第 j 个数字序列的第 t 个位置作为终点（其中第 2 维和第 3 维的状态总数不超过 \sum len = 200,000）。

动态规划的边界条件：若 S_{j,t}=1，则 dp_{1,j,t}=\text{true}；否则 dp_{1,j,t}=\text{false}。

动态规划的答案表示：对于询问 (r,c)，若存在 j,t 满足 S_{j,t}=c 并且 f_{r,j,t}=\text{true}，则说明存在一种接龙方案，否则说明不存在。

分析状态转移方程

转移可以分为两类：

第一类转移的暴力实现需要 O(k\sum l ) 的时间复杂度，因为对于每一个 dp_{i,j,t} = \text{true} 的位置，需要将 f_{i,j,t+1}\ldots f_{i,j,\min(t+k-1,l_j - 1)} 都标记为 \text{true}。

第二类转移的暴力实现需要需要 O((\sum l)^2) 的时间复杂度，因为对于每一个 f_{i,j,t} 为 \text{true} 的位置，我们需要找到所有的 j't' 满足 S_{j',t'}=S_{j,t} 且 j' \neq j，将 dp_{i+1,j',t'} 设置为 \text{true}。

上面两种转移的暴力实现总时间复杂度为 O(r(k+\sum l)\sum l )，会超时，需要进一步优化。

dp_i 转移到同一轮 f_i 的优化

我们发现，对于每一个 dp_{i,j,t} 为 \text{true} 的位置，需要将连续一段区间的 f_{i, j, t} 标记为 \text{true}。那么我们可以通过一个长度为 l_j 的差分数组 num 比较快地实现连续一段区间标记。

如果某一轮中 dp_{i,j,t} 为 \text{true}，我们就对第 j 个数字序列在区间 [t+1, \min(t+k-1, l_j-1)] 进行加 1 标记。这一操作表示能以 [t+1, \min(t+k-1, l_j-1)] 区间的数字作为这一轮接龙的结尾。

然后对 num 每个位置进行前缀和处理，这样只要前缀和后数组 num 位置 t 的值大于 0，就知道 f_{i,j,t} 的值应该为 \text{true}。

代码+注释

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=200010,M=110;
ll t,n,m,k,len[N],num[N],l,r;
vector<ll> a[N];
vector<bool> dp[N],f[N];
bool vis[N],ans[M][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>len[i];
            a[i].resize(len[i]),dp[i].resize(len[i]),f[i].resize(len[i]);
            for(int j=0;j<len[i];j++)
            {
                cin>>a[i][j];
                if(a[i][j]==1)
                {
                    dp[i][j]=true;
                }
                else
                {
                    dp[i][j]=false;
                }
            }
        }
        memset(ans,false,sizeof(ans));
        for(int i=1;i<=100;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int l=0;l<len[j];l++)
                {
                    num[l]=0;
                }
                for(int l=0;l<len[j];l++)
                {
                    if(dp[j][l])
                    {
                        num[l+1]++;
                        if(len[j]>l+m)
                        {
                            num[l+m]--; 
                        }
                    }
                }
                for(int l=0;l<len[j];l++)
                {
                    if(l>0)
                    {
                        num[l]+=num[l-1];
                    }
                    if(num[l]>0)
                    {
                        f[j][l]=true;
                    }
                    else
                    {
                        f[j][l]=false;
                    }
                    ans[i][a[j][l]]|=f[j][l];
                }
            }
            memset(vis,false,sizeof(vis));
            for(int j=1;j<=n;j++)
            {
                for(int l=0;l<len[j];l++)
                {
                    dp[j][l]=vis[a[j][l]];
                }
                for(int l=0;l<len[j];l++)
                {
                    if(f[j][l])
                    {
                        vis[a[j][l]]=true;
                    }
                }
            }
            memset(vis,false,sizeof(vis));
            for(int j=n;j>=1;j--)
            {
                for(int l=0;l<len[j];l++)
                {
                    dp[j][l]=dp[j][l]||vis[a[j][l]];
                }
                for(int l=0;l<len[j];l++)
                {
                    if(f[j][l])
                    {
                        vis[a[j][l]]=true;
                    }
                }
            }
        }
        while(k--)
        {
            cin>>l>>r;
            cout<<ans[l][r]<<"\n";
        }
    }
    return 0;
}

100pts 记录