真的T了。（滑稽

Final

Miemeng

100

03:12:51

03:12:54

03:12:55

115

03:12:55

幸好$T1$还能要，不然就……

前言

中午$\scr ZZN$告诉我，快把「×精×落」的代码下下来，不然下午$T1$是个神题一定跪。

$emm\dots$

思考良久……下午并没有下源码。

……

我觉得吧……没必要。

我不是那种一定要高分的人……而且我也不在乎现在的分。反正都垫底

过程

于是开题。

不是神题吧……

看了看觉得可做，就切掉了T1。

后来还查了几个错误。

打了点对拍。

T2T3丢个暴力上去。

后面T2跪了TLE0

题解

尽量写吧。

T1

有人还不会位运算吗？5*7同学问了我半天。

简单哒位运算：

有与，或，非，异或。

与，全1为1，其余为0

或，有1为1，无1为0

异或，不同为1，相同为0

非（这里说的是取反），0变1，1变0（纯右值表达式）

这里把数$A,B$看做两个集合，$1$看做两个集合中的元素。

然后就好不少。

于是：

好丑

于是有几个等式：

$$
(A\,and\,B)xor(A\,xor\,B)=A\,or\,B \\
(A\,or\,B)xor(A\,and\,B)=A\,xor\,B \\
(A\,or\,B)xor(A\,xor\,B)=A\,and\,B
$$

事实上这些柿子只有判0和知二推一时有用。

下面我们称$A\,and\,B$为集合$\mathcal{A}$

称$A\,or\,B$为集合$\mathcal{S}$

称$A\,xor\,B$为集合$\mathcal{B}$

那么如果我们只知道$\mathcal{S}$显然可以$3^{size_{\mathcal{S}}}$直接算。

剩下的情况可以判$inf$或是$2^{size_{\mathcal{B}}}$

于是代码：

#include <iostream>

#include <cstring>

#include <cstdio>

#define LL long long

using namespace std;

LL andn,orn,xorn;

LL ppow(LL a,LL b){

	LL res=1;

	while(b){

		if(b&1)res*=a;

		a*=a;

		b>>=1;

	}

	return res;

}

LL lowbit(LL x){

	return x&(-x);

}

LL count(LL x){

	LL n_1=0;

	while(x){

		n_1++;

		x-=lowbit(x);

	}

	return n_1

}

int main(){

	int T;

//	freopen("bits.in" ,"r",stdin);\

	freopen("bits.out","w",stdout);

	cin>>T;

	while(T--){

		scanf("%lld%lld%lld",&andn,&orn,&xorn);

		if(andn==-1 && xorn==-1){

			printf("%lld\n",ppow(3,count(orn)));

			continue;

		}

		if(xorn==-1 && orn==-1){

			puts("inf");

			continue;

		}

		if(orn==-1 && andn==-1){

			puts("inf");

			continue;

		}

		if(xorn==-1)

			xorn=orn^andn;

		if(orn==-1)

			orn=xorn|andn;

		if(andn==-1)

			andn=orn^xorn;

		if((xorn|orn)!=orn || (andn|orn)!=orn || (xorn&andn)!=0){

			puts("0");

			continue;

		}

//		cout<<count(orn^andn)<<endl;

		printf("%lld\n",1ll<<count(orn^andn));

	}

}

T2

考场上以为是个数据结垢，结果只有个$lazy$标记。

考察开桶和时间戳的应用。

……时间戳是好东西。

#include <iostream>

#include <cstring>

#include <cstdio>

#define N 111111

#define V 1111111

#define vis(i) vis[(i)+1000000]

#define LL long long

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 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;

}

int cn,

	vis[V<<1],

	mkv,

	siz,

	tim=1,

	nn;

LL ans=0;

int main(){

	int dat;

	cn=read();

	for(int i=1;i<=cn;i++){

		int opt=read();

		if(opt==1){

			nn=read();

			for(int j=1;j<=nn;j++){

				dat=read();

				if(vis(dat-mkv)!=tim){

					ans+=dat;

					siz++;

				}

				vis(dat-mkv)=tim;

			}

		}

		else if(opt==2){

			tim++;

			nn=read();

			ans=0,siz=0;

			for(int j=1;j<=nn;j++){

				dat=read();

				if(vis(dat-mkv)==tim-1){

					ans+=dat;

					siz++;

					vis(dat-mkv)=tim;

				}

			}

		}

		else if(opt==3){

			mkv++;

			ans+=siz;

		}

		else if(opt==4){

			mkv--;

			ans-=siz;

		}

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

	}

}

T3

先咕着。

巴特西

19-10-17-T

Final

前言

过程

题解

T1

简单哒位运算：

T2

T3

最新文章

热门文章