「题解」：集合论
发布时间：2020-12-14 04:39:09 所属栏目：大数据 来源：网络整理
导读：问题 B: 集合论 s u b s e t 时间限制: 1 Sec?? 内存限制: 512 MB 题面 题面谢绝公开。 题解 貌似可以直接用数组模拟。 不过我当时觉得bitset的操作可以完美解决交集问题，完全忽略了bitset位数对时间复杂度的影响。 base：对于插入的每一个元素，先加上一个
问题 B: 集合论subset时间限制: 1 Sec??内存限制: 512 MB 题面题面谢绝公开。 题解貌似可以直接用数组模拟。 不过我当时觉得bitset的&操作可以完美解决交集问题，完全忽略了bitset位数对时间复杂度的影响。 base：对于插入的每一个元素，先加上一个base（有负值）再插入到bitset中。 并集：对于插入的每一个元素，直接暴力判断在当前的bitset中存不存在，不存在累加进答案中，并置成存在。 交集：先将答案置零，并新建一个bitset。对于插入的每一个元素，依旧是暴力强判在bitset中存不存在，不存在就扔掉，存在就累加进答案。 对于新建的这个bitset，和原本bitset合并的方式有三种：1.滚动。（最佳选择）2.赋值。（T85）3.大力相与。（恭喜T飞）。 同时加1：两种选择：1.bitset整体右移。（恭喜T飞）2.base--。（优秀的算法） 同时减1与上面相反。 所以bitset的位运算和位数有关。这种2e6的情况下还是非常慢的。 代码： ? #include<bits/stdc++.h>
#define read(A) A=init()
#define rint register int
using namespace std;
char xch,xB[1<<15],*xS(xB),*xTT(xB);
#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
inline int init()
{
int x=0,f=1;char ch=getc();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getc();}
while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getc();}
return x*f;
}
int m,siz,wei,opt,sum,ai,extra;
long long ans;
bitset <2000004> bit[2];
main()
{
read(m);wei=1000000;extra=1000000;
int now=1;
for(rint i=1;i<=m;++i)
{
read(opt);
if(opt==1)
{
read(sum);
while(sum--)
{
read(ai);
if(!bit[now][ai+wei])
{
ans+=ai,++siz;
bit[now][ai+wei]=1;
}
}
printf("%lldn",ans);
}
else if(opt==2)
{
ans=siz=0;
read(sum);
while(sum--)
{
read(ai);
if(bit[now][ai+wei])
{
bit[now^1].set(ai+extra);
ans+=ai,++siz;
}
}
wei=extra;
bit[now].reset();
now^=1;
printf("%lldn",ans);
}
else if(opt==3){--wei;ans+=siz;printf("%lldn",ans);}
else{++wei;ans-=siz;printf("%lldn",ans);}
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |