思路见此

目前工作：

• 将 while(m--) 循环里的操作分离成函数
• 把 sb 位运算改成 popcnt
• 把 vector 改成数组

洛谷上从 60 卡到了 72。

LOJ 上一直是 80，而且会谜之 WA 2个点。

代码函数解释：

• Tr_rea 是把 16 进制串变成 2 进制
• Tr_sol 是处理强制在线
• Tr_num 是把二进制分成 $16$ 段转换成 int
• Dif_bet 是判断 $a,b$ 之间不同的位数
• popcnt_16 和 pre 是计算 popcnt
• pc[] 是存储数的 popcnt 值

代码：

#include <cstdio>
//#include <vector>
#include <cstring>

#define ull unsigned long long
#define N 400000
#define mod 23333
#define T 65536
using namespace std;
struct node{
	int val, ind;
};
bool r[300], s[N + 1][300];
int pc[N];
int popcnt_16(int x){
	int cnt = 0;
	for(int i = 0 ; i < 16 ; i++){
		cnt += x & 1;
		x >>= 1;
	}
	return cnt;
}
void pre(){
	for(int i = 0 ; i < T ; i++)
	    pc[i] = popcnt_16(i);
}
int Pre_work(char c){
	if(c >= '0' && c <= '9') return c - '0';
	else return 10 + c - 'A';
}
void Tr_rea(char p[]){
	for(int i = 0 ; i < 64 ; i++){
		int x = Pre_work(p[i]);
		for(int j = 0 ; j < 4 ; j++)
		    r[i * 4 + 4 - j - 1] = x % 2, x /= 2;
	}
}
void Tr_sol(int op){
	for(int i = 0 ; i < 256 ; i++)
		r[i] ^= op;
}
int Tr_num(bool r[], int l){
	int ans = 0;
	int base = 1;
	for(int i = l + 15 ; i >= l ; i--){
		ans += base * r[i];
		base *= 2;
	}
	return ans;
}
int Dif_bet(int a, int b){
	int c = a ^ b;
	return pc[c];
}
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;
}
char c[300];
ull a1, a2;
int n, m, k, ans = 0, in;
int len[20][mod];
node h[20][mod][8];
//vector <node> h[20][mod];
void Sol(){
	scanf("%s", c);
	scanf("%d", &k);
	Tr_rea(c);
	Tr_sol(ans);
	for(int i = 0 ; i < 256 ; i += 16){
		int x = Tr_num(r, i), nu = i / 16;
		//int siz = h[nu][x % mod].size();
		int siz = len[nu][x % mod];
		for(int j = 0 ; j < siz ; j++){
			if(h[nu][x % mod][j].val == x){
				in = h[nu][x % mod][j].ind;
				int cnt = 0;
				for(int o = 0 ; o < 256 ; o += 16){
				    int y = Tr_num(s[in], o);
				    int z = Tr_num(r, o);
					cnt += Dif_bet(z, y);
				}
				if(cnt <= k){
				    ans = 1;
					puts("1");
					return;
				}
			}
		}
	}
	ans = 0;
	puts("0");
}
int main(){
	freopen("qi.in", "r", stdin);
	freopen("qi.out", "w", stdout);
	scanf("%d%d", &n, &m);
	scanf("%llu%llu", &a1, &a2);
	gen(n, a1, a2);
	pre();
	for(int i = 1 ; i <= n ; i++){
		for(int j = 0 ; j < 256 ; j += 16){
			int x = Tr_num(s[i], j);
			node tmp;
			tmp.val = x, tmp.ind = i;
			h[j / 16][x % mod][len[j / 16][x % mod]++] = tmp;
			//h[j / 16][x % mod].push_back(tmp);
		}
	}
	while(m--)
		Sol();
	return 0;
}

还能怎么卡 /kel