论今年csp-j T4 接龙
题目链接
题目大意
每个人都有一个词库，接龙第一轮只能以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结尾，则有以下代码：
#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优化的代码如下：
#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！！！。