【NOI D2T1】量子通信
解题思路
这道题，怎么看，第一眼都感觉像 (01) trie 啊。。。。
在同步赛中我发现了 (sqrt {256}approx 15)，但是没有好好利用。
其实这就是本题的突破口。
令 (x=2^{16}=65536)，我们把询问串和字典串由 (16) 进制和 (2) 进制改为 (x) 进制。由于在 (2) 进制下，最多有 (k) 位不同，而 (kleq 15)，也就是说在 (16) 位的 (x) 进制数中，字典串和询问串至少一有一位完全相同。这个由抽屉原理可以证明。
那么思路就很明晰了。我们先预处理字典串，然后用 vector 记录在第 (i) 位上为 (j) 的询问串的编号。那么对于每一个 vector，它的大小平均为 (frac{n}{x})。由于数据是用给定函数 gen 生成的，数据相对比较随机，我们可以认为大小就基本为 (frac nx) 左右。
对于每一个询问，我们可以枚举在 (x) 进制下，哪一位与字典串相等，然后取出对应 vector 中的所有字典串，暴力算一遍看看是否符合要求即可。这样时间复杂度为 (O(mcdot 16cdot frac nxcdot 256))。把 (x=65536) 代入，复杂度为 (O(frac{nm}{16}))。这不肯定爆炸吗？
我们考虑如何继续优化一下。
我们发现，检查字典串和询问串是否符合要求的时间复杂度过高。想办法优化。
我们可以先预处理出 (forall iin [0,x),iin N^+) 的 popcnt，即二进制下 (1) 的位数，然后对于 (x) 进制下的每一位，我们就可以快速求出这一位上有多少位二进制是不同的这样，时间复杂度变为了 (O(mcdot 16cdot frac nxcdot 16)=O(frac{nm}{256})) 。把 (n,m) 的极值代入，时间复杂度大约为 (O(1.8*10^8)) 。
显然我们还要卡卡常。
还是再检验，我们实时比较 (k) 和当前二进制不同位数，若已经超过了 (k)，直接退出，所以时间是跑不满的。在加个 快读，基本就过了。当然你要保证你的其他常数不是特别大。
如果你在考场上想再稳一些，还可以做以下操作：
- 把
vector改成链表。 - 不要用
bitset。、 - 循环展开
- ……（可以参考其他大佬的博客）
代码
//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;
int read() {
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch>='A'&&ch<='Z')
return ch-'A'+10;
ch=getchar();
}
if(ch>='0'&&ch<='9') {
return ch-'0';
}
}
const int MAXN=4e5+10;
typedef unsigned long long ull;
ull n,m,a1,a2;
int lastans;
bool s[MAXN][256];
int cnt[256*256],a[20],b[MAXN][20];
vector<int> v[17][256*256];
ull myRand(ull &k1, ull &k2) {
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= (k3 << 23);
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
void gen(int n, ull a1, ull a2) {
for (int i = 1; i <= n; i++)
for (int j = 0; j < 256; j++)
s[i][j] = (myRand(a1, a2) & (1ull << 32)) ? 1 : 0;
}
int popc(int x) {
int ret=0;
while(x) {
if(x&1) {
ret++;
}
x>>=1;
}
return ret;
}
void insert(int k) {
for(int i=1;i<=16;i++) {
int w=0;
for(int j=0;j<16;j++) {
w=w*2+(s[k][(i-1)*16+j]? 1:0);
}
b[k][i]=w;
v[i][w].push_back(k);
}
}
bool ok(int j,int k) {
for(int i=1;i<=16;i++) {
k-=cnt[b[j][i]^a[i]];
if(k<0) {
return 0;
}
}
return 1;
}
int check(int k) {
for(int i=1;i<=16;i++) {
int sz=v[i][a[i]].size();
for(int j=0;j<sz;j++) {
// puts("ohhhh");
if(ok(v[i][a[i]][j],k)) {
return 1;
}
}
}
return 0;
}
signed main() {
freopen("qi.in","r",stdin);
freopen("qi.out","w",stdout);
for(int i=0;i<256*256;i++) {
cnt[i]=popc(i);
}
cin>>n>>m>>a1>>a2;
gen(n,a1,a2);
for(int i=1;i<=n;i++) {
insert(i);
}
while(m--) {
for(int i=1;i<=16;i++) {
int x=read(),y=read(),z=read(),xx=read();
a[i]=x*16*16*16+y*16*16+z*16+xx;
if(lastans) {
a[i]=(256*256-1)^a[i];
}
}
int k;
scanf("%d",&k);
printf("%d
",lastans=check(k));
}
fclose(stdin);
fclose(stdout);
return 0;
}