专栏文章

论今年csp-j T4 接龙

___czy
题解参与者 1已保存评论 0

文章操作

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

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

题目大意

每个人都有一个词库，接龙第一轮只能以1开头，其他轮必须以上一轮接龙序列最后一个数字开头，接龙序列长度不超过k。问你r次接龙能不能以c结尾，若能，输出1，否则输出0。

题目分析

这个题的正解肯定是动态规划，但是还是有一些歪门邪道的方法的，不知道是不是CCF数据造水了。
下面开始讲解思路：
可以用一个flag[i][j]表示第i个人第j个数能不能作为开头，f[i][j]表示第i轮能否以j结尾，book[i]=0，表示没有以i结尾的接龙序列，book[i]=x，表示有且仅有x这个人有接龙序列能以i为结尾，book[i]=-1表示多个人的接龙序列能以i结尾，则有以下代码：
CPP
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

const int xx = 2e5+5;

int t,n,k,q;
int len[xx],f[xx][101],book[xx];
vector<int> a[xx];
vector<int> flag[xx];

inline int read()
{
	int x=0;
	char ch=getchar();
	while(ch<='9'&&ch>='0')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

int main()
{
	t=read();
	while(t--)
	{
		n=read(),k=read(),q=read();
		for(int i=1;i<=n;i++)
		{
			len[i]=read();
			a[i].resize(len[i]+1);
			flag[i].resize(len[i]+1);
			for(int j=1;j<=len[i];j++)
			{
				a[i][j]=read();
				if(a[i][j]==1) flag[i][j]=1;
				else flag[i][j]=0;
			}
		}
//		for(int i=1;i<=n;i++)
//		{
//			for(int j=1;j<=len[i];j++) cout<<a[i][j]<<" ";
//			cout<<"\n";
//		}
//		return 0;
		for(int op=1;op<=100;++op)
		{
			for(int j=1;j<=xx;++j)
			{
				book[j]=0;
				f[j][op]=0;
			}
			for(int i=1;i<=n;++i)
			{
				int pre=-k;
				for(int j=1;j<=len[i];++j)
				{
					if(j-pre+1<=k)
					{
						int value=a[i][j];
						if(!book[value]) book[value]=i;
						else if(book[value]!=i) book[value]=-1;
						f[value][op]=1;
					}
					if(flag[i][j]) pre=j;
				}
			}
			for(int i=1;i<=n;++i)
				for(int j=1;j<len[i];++j)
				{
					int value=a[i][j];
					if(book[value]&&book[value]!=i) flag[i][j]=1;
					else flag[i][j]=0;
				}
		}
//		for(int i=1;i<=10;i++)
//		{
//			for(int j=1;j<=10;j++)
//				cout<<f[i][j]<<" ";//以i结尾,j次接龙 
//			cout<<"\n";
//		}
//		return 0;
		while(q--)
		{
			int r=read(),c=read();
			cout<<f[c][r]<<"\n";
		}
	}
	return (0^0);
}
但是很明显这样会T，~~不知道为什么有3个点会WA~~~~。
测评记录

神奇的bitset

但是我们可以用一个很神奇的东西：bitset！！！！
使用bitset优化的代码如下：
CPP
#include<iostream>
#include<cstdio>
#include<vector>
#include<bitset>

using namespace std;

const int xx = 2e5+5;

int t,n,k,q;
int len[xx],book[xx];
vector<int> a[xx];
vector<int> flag[xx];
bitset<xx> f[101];

inline int read()
{
	int x=0;
	char ch=getchar();
	while(ch<='9'&&ch>='0')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

int main()
{
	t=read();
	while(t--)
	{
		n=read(),k=read(),q=read();
		for(int i=1;i<=n;++i)
		{
			len[i]=read();
			a[i].resize(len[i]+1);
			flag[i].resize(len[i]+1);
			for(int j=1;j<=len[i];++j)
			{
				a[i][j]=read();
				if(a[i][j]==1) flag[i][j]=1;
				else flag[i][j]=0;
			}
		}
//		for(int i=1;i<=n;i++)
//		{
//			for(int j=1;j<=len[i];j++) cout<<a[i][j]<<" ";
//			cout<<"\n";
//		}
//		return 0;
		for(int op=1;op<=100;++op)
		{
			for(int j=1;j<=xx;++j)
			{
				book[j]=0;
				f[op][j]=false;
			}
			for(int i=1;i<=n;++i)
			{
				int pre=-k;
				for(int j=1;j<=len[i];++j)
				{
					if(j-pre+1<=k)
					{
						int value=a[i][j];
						if(!book[value]) book[value]=i;
						else if(book[value]!=i) book[value]=-1;
						f[op][value]=true;
					}
					if(flag[i][j]) pre=j;
				}
			}
			for(int i=1;i<=n;++i)
				for(int j=1;j<len[i];++j)
				{
					int value=a[i][j];
					if(book[value]&&book[value]!=i) flag[i][j]=1;
					else flag[i][j]=0;
				}
		}
//		for(int i=1;i<=10;i++)
//		{
//			for(int j=1;j<=10;j++)
//				cout<<f[i][j]<<" ";//以i结尾,j次接龙 
//			cout<<"\n";
//		}
//		return 0;
		for(int i=1;i<=q;++i)
		{
			int r=read(),c=read();
			if(f[r][c]) cout<<1<<"\n";
			else cout<<0<<"\n";
		}
	}
	return (0^0);
}
看测评记录还是比较轻松地A了这道题。完结撒花~~~~~
这就是如何用不纯的dp的方法做今年的普及组T4！！！。

评论

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

正在加载评论...