专栏文章

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

aaaa_lvzekai
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir12fxq
此快照首次捕获于
2025/12/04 14:01
3 个月前
此快照最后确认于
2025/12/04 14:01
3 个月前
查看原文

题目介绍

有 nn 个人，第 ii 个人有一个整数序列 SiS_i 作为他的词库。
一次游戏分为 tt 轮，每一轮规则如下：
  • 若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
  • 接龙的人选择一个长度在 [2,k][2, k] 的 SiS_i 的连续子序列 AA 作为这一轮的接龙序列。若这是游戏的第一轮，那么 AA 需要以元素 11 开头，否则 AA 需要以上一轮的接龙序列的最后一个元素开头。
  • 序列 AA 是序列 SS 的连续子序列当且仅当可以通过删除 SS 的开头和结尾的若干元素（可以不删除）得到 AA。
  • 有 qq 次询问，每次询问包括两个参数 (r,c)(r,c)，表示询问是否存在一个 rr 轮的接龙游戏，满足最后一次接龙的 AA 以数字 cc 结尾。

样例

样例输入

CPP
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

样例输出

CPP
1
0
1
0
1
0
0

提示

【样例 1 解释】
在下文中，我们使用 {Ai}={A1,A2,…,Ar}\{A_i\} = \{A_1, A_2, \dots , A_r\} 表示一轮游戏中所有的接龙序列，{pi}={p1,p2,…,pr}\{p_i\} = \{p_1, p_2, \dots , p_r\} 表示对应的接龙的人的编号。由于所有字符均为一位数字，为了方便我们直接使用数字字符串表示序列。
  • 对于第一组询问，p1=1p_1 = 1、A1=12A_1 = 12 是一个满足条件的游戏过程。
  • 对于第二组询问，可以证明任务不可完成。注意 p1=1p_1 = 1、A1=1234A_1 = 1234 不是合法的游戏过程，因为此时 ∣A1∣=4>k|A_1| = 4 > k。
  • 对于第三组询问，{pi}={2,1}\{p_i\} = \{2, 1\}、{Ai}={12,234}\{A_i\} = \{12, 234\} 是一个满足条件的游戏过程。
  • 对于第四组询问，可以证明任务不可完成。注意 {pi}={2,1,1}、{Ai}={12,23,34}\{p_i\} = \{2, 1, 1\}、\{A_i\} = \{12, 23, 34\} 不是一个合法的游戏过程，因为尽管所有的接龙序列长度均不超过 kk，但第二轮和第三轮由同一个人接龙，不符合要求。
  • 对于第五组询问，{pi}={1,2,3,1,2,3}\{p_i\} = \{1, 2, 3, 1, 2, 3\}、{Ai}={12,25,51,12,25,516}\{A_i\} = \{12, 25, 51, 12, 25, 516\} 是一个满足条件的游戏过程。
  • 对于第六组询问，可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 22，因此 A1=1A_1 = 1 不是一个合法的游戏过程。
  • 对于第七组询问，所有人的词库均不存在字符 7\tt 7，因此任务显然不可完成。
【数据范围】
对于所有测试数据，保证：
  • 1≤T≤51 \leq T \leq 5；
  • 1≤n≤1051 \leq n \leq 10^5，2≤k≤2×1052 \leq k \leq 2 \times 10^5，1≤q≤1051 \leq q \leq 10^5；
  • 1≤li≤2×1051 \leq l_i \leq 2 \times 10^5，1≤Si,j≤2×1051 \leq S_{i,j} \leq 2 \times 10^5；
  • 1≤rj≤1021 \leq r_j \leq 10^2，1≤cj≤2×1051 \leq c_j \leq 2 \times 10^5；
  • 设 ∑l\sum l 为单组测试数据内所有 lil_i 的和，则 ∑l≤2×105\sum l\leq 2\times 10^5。
测试点n≤n\leqr≤r\leq∑l≤\sum l\leqq≤q\leq特殊性质
1110310^3112000200010310^3无
2,32,3101055202010210^2无
4,54,510310^310102000200010310^3A
6610510^510210^22×1052\times 10^510510^5A
7,87,810310^310102000200010310^3B
9,109,1010510^510210^22×1052\times 10^510510^5B
11,1211,1210310^310102000200010310^3C
13,1413,1410510^510210^22×1052\times 10^510510^5C
15∼1715\sim 1710310^310102000200010310^3无
18∼2018\sim 2010510^510210^22×1052\times 10^510510^5无
特殊性质 A：保证 k=2×105k = 2 \times 10^5。
特殊性质 B：保证 k≤5k ≤ 5。
特殊性质 C：保证在单组测试数据中，任意一个字符在词库中出现次数之和均不超过 55。

原题链接

100pts 思路讲解

算法：动态规划

时间复杂度：O(n)O(n)

通过搜索可以拿 2525 分，可以考虑运用记忆化搜索来优化程序效率，进而可以想到从动态规划的角度思考这道题的解法。
对于第 jj 个数字序列 SjS_j ，将其长度记为 lenjlen_j。不妨认为 SjS_j 的下标范围为 0∼lenj−10 \sim len_j-1。
我们定义状态 dpi,j,tdp_{i,j,t} 表示在第 ii 轮中，能否以第 jj 个数字序列的第 tt 个位置作为起点（其中第 22 维和第 33 维的状态总数不超过 ∑len=200,000\sum len = 200,000）。
定义状态 fi,j,tf_{i,j,t} 表示在第 ii 轮中，能否以第 jj 个数字序列的第 tt 个位置作为终点（其中第 22 维和第 33 维的状态总数不超过 ∑len=200,000\sum len = 200,000）。
动态规划的边界条件：若 Sj,t=1S_{j,t}=1，则 dp1,j,t=truedp_{1,j,t}=\text{true}；否则 dp1,j,t=falsedp_{1,j,t}=\text{false}。
动态规划的答案表示：对于询问 (r,c)(r,c)，若存在 j,tj,t 满足 Sj,t=cS_{j,t}=c 并且 fr,j,t=truef_{r,j,t}=\text{true}，则说明存在一种接龙方案，否则说明不存在。

分析状态转移方程

转移可以分为两类：
  • dpdp 转移到同一轮 ff。
  • ff 转移到下一轮 dpdp。
第一类转移的暴力实现需要 O(k∑l)O(k\sum l ) 的时间复杂度，因为对于每一个 dpi,j,t=truedp_{i,j,t} = \text{true} 的位置，需要将 fi,j,t+1…fi,j,min⁡(t+k−1,lj−1)f_{i,j,t+1}\ldots f_{i,j,\min(t+k-1,l_j - 1)} 都标记为 true\text{true}。
第二类转移的暴力实现需要需要 O((∑l)2)O((\sum l)^2) 的时间复杂度，因为对于每一个 fi,j,tf_{i,j,t} 为 true\text{true} 的位置，我们需要找到所有的 j′t′j't' 满足 Sj′,t′=Sj,tS_{j',t'}=S_{j,t} 且 j′≠jj' \neq j，将 dpi+1,j′,t′dp_{i+1,j',t'} 设置为 true\text{true}。
上面两种转移的暴力实现总时间复杂度为O(r(k+∑l)∑l) O(r(k+\sum l)\sum l )，会超时，需要进一步优化。

dpidp_i 转移到同一轮 fif_i 的优化

我们发现，对于每一个 dpi,j,tdp_{i,j,t} 为 true\text{true} 的位置，需要将连续一段区间的 fi,j,tf_{i, j, t} 标记为 true\text{true}。那么我们可以通过一个长度为 ljl_j 的差分数组 numnum 比较快地实现连续一段区间标记。
如果某一轮中 dpi,j,tdp_{i,j,t} 为 true\text{true}，我们就对第 jj 个数字序列在区间 [t+1,min⁡(t+k−1,lj−1)][t+1, \min(t+k-1, l_j-1)] 进行加 11 标记。这一操作表示能以 [t+1,min⁡(t+k−1,lj−1)][t+1, \min(t+k-1, l_j-1)] 区间的数字作为这一轮接龙的结尾。
然后对 numnum 每个位置进行前缀和处理，这样只要前缀和后数组 numnum 位置 tt 的值大于 00，就知道 fi,j,tf_{i,j,t} 的值应该为 true\text{true}。

代码+注释

CPP
#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 记录

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...