错题集 4

1、小V的序列

链接

题意

给定一个长度为 $n$ 的序列，保证序列中每个数取值随机。

接下来给定 $m$ 个询问，每次给定一个数 $b$，问序列中是否存在数与 $b$ 异或后二进制表示中 $1$ 的个数不超过 $3$。

题解

考虑将 $b$ 的二进制表示分成四部分，每部分表示一个长度为 $16$ 二进制数。

则如果要与 $b$ 异或后二进制表示中 $1$ 的个数不超过 $3$，则至少四部分要有一个部分与 $b$ 相同。

考虑将序列中的每个数分成四个，每个数投入对应位置二进制数的桶中，然后暴力查询，时间复杂度 $O\left(4\cfrac {nm}{2^{16}}\log v\right)$。

查看代码

const int MAXN=1e6+5,MAXM=1<<16,Mod=998244353;
LL a[MAXN];
vector<LL> c[4][MAXM];
uint64_t G(uint64_t x){
    x^=x<<13;
    x^=x>>7;
    x^=x<<17;
    return x;
}
bool check(LL x){
	int cnt=0;
	_for(i,0,64){
		if((x>>i)&1)
		cnt++;
	}
	return cnt<=3;
}
int main()
{
	int n=read_int(),m=read_int();
	a[0]=read_LL();
	_for(i,1,n)a[i]=G(a[i-1]);
	_for(i,0,n){
		_for(j,0,4)
		c[j][(a[i]>>(16*j))&((1<<16)-1)].push_back(a[i]);
	}
	int ans=0;
	while(m--){
		LL b=read_LL();
		bool flag=false;
		_for(i,0,4){
			int t=(b>>(16*i))&((1<<16)-1);
			_for(j,0,c[i][t].size()){
				if(check(c[i][t][j]^b)){
					flag=true;
					break;
				}
			}
			if(flag)
			break;
		}
		ans=(ans<<1|flag)%Mod;
	}
	enter(ans);
	return 0;
}

CVBB ACM Team

目录

错题集 4

1、小V的序列

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

错题集 4

1、小V的序列

题意

题解

页面工具