萌新求助卡常
查看原帖
萌新求助卡常
126582
Scintilla楼主2021/7/28 20:29

快读是蒯来的,孩子卡了好久了还是过不了,求哪位好心人告诉孩子怎么卡常 /kk

除了循环展开和不用 bitset 并把给定的二进制串也压成 1616 位,有没有更好写的卡法啊 kk

#include <bits/stdc++.h>

using namespace std;

#define il inline
#define re register
#define rep(i, s, e) for (re int i = s; i <= e; ++i)
#define drep(i, s, e) for (re int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)

using ull = unsigned long long;

const int N = 400000 + 10;
const int L = 256;
const int B = 16;
const int T = L / B;

namespace FastIO{
	 char nc(){
		static char buf[100000],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
	}
	 int read(){
		char t;int u=0,k=1;t=getchar();
		while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
		while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
		return u*k;
	}
	template <typename T>
	 void read(T &u){
		char t;T k=1;u=0;t=getchar();
		while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
		while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
		if(t=='.'){
			T mass=0.1;t=getchar();
			while(t>='0'&&t<='9'){u+=mass*(t-'0');mass/=10;t=getchar();}
		}u*=k;
	}
	 int read(char asd[]){
		char t=getchar();int u=0;
		while(t==' '||t=='\n'||t=='\r')t=getchar();
		while(t!=' '&&t!='\n'&&t!=EOF&&t!='\r')asd[u++]=t,t=getchar();
		asd[u]='\0';return u;
	}
	char sr[1<<23],z[23];int C=-1,Z;
	 void wer(int x,char T){
		int y=0;if(x<0)y=1,x=-x;
		while(z[++Z]=x%10+'0',x/=10);if(y)z[++Z]='-';
		while(sr[++C]=z[Z],--Z);sr[++C]=T;
	}
	 void wer(char T[],char QWQ){
		for(int i=0;T[i]!='\0';i++)sr[++C]=T[i];
		sr[++C]=QWQ;
	}
	 void out(){fwrite(sr,1,C+1,stdout);C=-1;}
}
using namespace FastIO;

bool s[N][L];

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 n, m, lastans;
ull a1, a2;
char str[L];
map <char, int> to;
bitset <L> bit[N], ask;
vector <int> bel[T][1 << B];

int main() {
    rep(i, 0, 9) to[i + '0'] = i;
    rep(i, 0, 5) to[i + 'A'] = i + 10;
//    file(data);
    read(n), read(m), read(a1), read(a2);
    gen(n, a1, a2);
    rep(i, 1, n) {
        rep(j, 0, L - 1) bit[i][j] = s[i][j];
        rep(j, 0, T - 1) {
            int val = 0;
            rep(k, 0, B - 1) val |= (bit[i][j * B + k] << k);
            bel[j][val].push_back(i);
        }
    }
    while (m --) {
    	int k;
        read(str), read(k);
        rep(i, 0, (L >> 2) - 1) {
            int val = to[str[i]];
            drep(j, 3, 0) ask[(i << 2) + j] = val & 1, val >>= 1;
        }
        if (lastans) ask.flip();
        vector <int> psb;
        rep(i, 0, T - 1) {
            int val = 0;
			rep(j, 0, B - 1) val |= (ask[i * B + j] << j);
            for (int x : bel[i][val]) psb.push_back(x);
        }
        bool flag = false;
        for (int i : psb) {
            bitset <L> tmp = ask ^ bit[i];
            if (tmp.count() <= k) { flag = true; break; }
        }
        lastans = flag, putchar('0' + flag), putchar('\n');
    }
    return 0;
}
2021/7/28 20:29
加载中...