[CSP-S模拟测试]:集合论（模拟）

题目传送门（内部题73）

输入格式

　　输入文件$jihe.in$
　　第一行一个整数$m$，表示操作的次数。
　　接下来$m$行，每行描述一个操作。
　　每行的开始都是一个数字，$1,2,3,4$依次代表$union,intersection,plus,minus$。
　　对于$plus$和$minus$操作，这一行只包含数字$3$或数字$4$。
　　对于$union$和$intersection$操作，数字$1$或$2$后面会给出集合$B$。集合$B$与前面的数字之间用空格隔开。集合$B$的描述方式是：首先给出一个数字$Size$表示集合$B$的元素个数，接下来给出$Size$个空格隔开的整数。保证这$Size$个整数互不相同。

输出格式

　　输出文件$jihe.out$
　　$m$行，第$i$行一个整数，表示第$i$次操作之后集合$A$中所有元素之和

样例

见下发文件

数据范围与提示

　　我们用$SUM$表示给出的集合的$Size$之和（也就是给出的集合的元素总个数），$MAX$表示给出的集合中元素的绝对值的最大值
　　第$1$个测试点：只有$plus$操作和$minus$操作，$m\leqslant 10^5$
　　第$2,3$个测试点：$m\leqslant 10^5,SUM\leqslant 10^5,MAX\leqslant 10^6$，没有$plus$操作和$minus$操作
　　第$4$个测试点：$m\leqslant 10^5,SUM\leqslant 3\times 10^6,MAX\leqslant 10^6$，没有$plus$操作和$minus$操作和$intersection$操作。
　　第$5,6,7,8$个测试点：$m\leqslant 10^5,SUM\leqslant 3\times 10^6,MAX\leqslant 10^6$，没有$plus$操作和$minus$操作
　　第$9,10$个测试点：$m\leqslant 10^3,SUM\leqslant 10^3,MAX\leqslant 10^3$
　　第$11,12,13,14,15$个测试点：$m\leqslant 10^5,SUM\leqslant 10^5,MAX\leqslant 10^6$
　　第$11$个测试点还满足：所有$plus$和$minus$操作出现在所有$intersection$和$union$操作之后。
　　第$16,17,18,19,20$个测试点：$m\leqslant 10^5,SUM\leqslant 3\times 10^6,MAX\leqslant 10^6$
　　由于输入的数据量可能过大，为选手提供一个用于快速读入的函数，复制粘贴到程序开头就可以用了。在程序内调用$read()$将返回读入的下一个数字。
　　（需要$\#include<cstdio>$）

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 read()

{

	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*10+ch-'0';ch=getc();}

	return x*f;

}

题解

你是不是学数据结构学傻了？

其实就是一个模拟……

发现$intersection$操作很难搞，时间复杂度是$\Theta(n)$的。

我的做法其实很简单，对于当前集合里的数维护一个时间，是当前时间即表示在集合里，不是当前时间就不在集合里。

注意数组尽可能开打点就好了。

时间复杂度：$\Theta(Size)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int m;

int opt[100001],size[100001];

vector<int> v[100001];

int bit[3000000];

int base=0x3f3f3f3f;

long long sss;

long long ans;

int main()

{

	scanf("%d",&m);

	for(int i=1;i<=m;i++)

	{

		scanf("%d",&opt[i]);

		if(opt[i]==1||opt[i]==2)

		{

			scanf("%d",&size[i]);

			for(int j=1;j<=size[i];j++)

			{

				int x;

				scanf("%d",&x);

				base=min(base,x);

				v[i].push_back(x);

			}

		}

	}

	base-=100000;

	int tim=1;

	for(int i=1;i<=m;i++)

	{

		if(opt[i]==1)

		{

			for(int j=0;j<v[i].size();j++)

				if(bit[v[i][j]-base]!=tim)

				{

					bit[v[i][j]-base]=tim;

					ans+=v[i][j];

					sss++;

				}

		}

		if(opt[i]==2)

		{

			ans=0;sss=0;

			for(int j=0;j<v[i].size();j++)

				if(bit[v[i][j]-base]==tim)

				{

					ans+=v[i][j];

					bit[v[i][j]-base]++;

					sss++;

				}

			tim++;

		}

		if(opt[i]==3)

		{

			base++;

			ans+=sss;

		}

		if(opt[i]==4)

		{

			base--;

			ans-=sss;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

rp++

巴特西