AcWing 3705. 子集mex值
原题链接
简单
作者:
@月@
,
2021-06-24 23:11:17
,
所有人可见
,
阅读 245
#include <iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int re[150]={0};
for (int i = 1; i <= n; i ++ ){
int a;
cin>>a;
re[a]++;//桶数组记录每个数出现的个数
}
int flag=1,ans=0;
for(int i=0;i<=100;i++)//看数据范围,直接遍历每个数
{
if(re[i]==1&&flag)ans+=i,flag=0;//如果这个数只出现一次,那么肯定有一个集合没有这个元素,mex(A)=i or mex(B)=i
else if(re[i]==0&&flag){ans+=2*i;break;}//如果这个数出现零次,那么mex(A)=i and mex(B)=i
else if(re[i]==0&&!flag){ans+=i;break;}//如果前面有只出现一次的数,那么这个数出现零次,那么mex(A)=第一个if那里的值 and mex(B)=i
}
cout<<ans<<endl;
}
return 0;
}