本文同时发布于
题目分析
给你n个集合,每个集合里面都有可能会重复的数字
q个询问,每次询问两个数是否会在同一集合内
$n<=1000$
$q<=200000$
做法分析
算法一: $\mathcal{O}(nq)$ 的暴力做法
$vis[x][i]$ 表示 x 是否出现在第 i 个集合中,是为1,否为0
每一次询问枚举
算法二: 状态压缩压掉第二维
时间复杂度 $\mathcal{O}(n+q)$
但是 $n<=1000$ 范围会爆空间
具体做法:
vis[x]表示 x所包括的集合,如果 x 在第 i 个集合中出现,则第 i 位为1 ( 二进制位 )
储存操作: 第 i 个集合读到 x 时,则vis[x]|=(1<<i)
查询操作:查询 x 和 y 是否在同一集合内出现过,就是查询vis[x]&vis[y]
是否为1
但是显然就算使用 unsigned long long 也经不过n<=1000的数据范围
参考Code:
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
int vis[10010];
int n,q,c,x,y;
bool f;
inline int read()
{
int r=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9'){
r=(r<<3)+(r<<1)+(ch^48);
ch=getchar();
}
return r;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
c=read();
for(int j=1;j<=c;j++)
{
x=read();
vis[x]|=(1<<i);
}
}
q=read();
for(int i=1;i<=q;i++)
{
x=read();y=read();
if(vis[x]&vis[y])
puts("Yes");
else
puts("No");
}
return 0;
}
算法三: 用bitset对算法二进行优化
奇技淫巧bitset是一个极其好用的STL,类似于bool数组却比bool数组支持更多的操作,更快,占用空间更小
关于具体的bitset的各种骚操作珂以去网上找找
bitset在#include<bitset>
头文件里
bitset<1010>vis[10010]
这样就声明了10010个bitset
每一个bitset共有1010个bit,每个bit为1或0,初始都为0
bitset也支持按位与,按位或,按位异或,左移右移等操作等操作.
而且占用空间也小,一个bool是1byte,而bitset的一位只占1bit
时间复杂度$ \mathcal{O}(n+q)$
参考Code:
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
bitset<1010>tmp,vis[10010];
int n,q,c,x,y;
bool f;
inline int read()
{
int r=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9'){
r=(r<<3)+(r<<1)+(ch^48);
ch=getchar();
}
return r;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
c=read();
for(int j=1;j<=c;j++)
{
x=read();
vis[x][i]=1;//存入可以按正常的bool数组写
}
}
q=read();
for(int i=1;i<=q;i++)
{
x=read();y=read();
tmp=vis[x]&vis[y];
if(tmp.count()!=0)
puts("Yes");
else
puts("No");
}
return 0;
}