2021NOI同步赛

DAY1:

轻重边：
题目地址：https://www.luogu.com.cn/problem/P7735
树剖

DAY2:

量子通信：
题目地址：https://www.luogu.com.cn/problem/P7738
判断两个数在二进制下有多少位不同的方法：
将两数异或，这个异或后的数在二进制下有多少个1，就是答案。

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int N = 400000;
bool s[N+1][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;
    return ;
}

int n,m;
ull a1,a2;

int b1[65536];
vector<vector<vector<int> > > a;
int b2[N+1][16];
void yuchuli()
{
    for(int i=0;i<16;i++)
    {
        a.push_back({});
        for(int j=0;j<65536;j++)
        {
            a[i].push_back({});
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<256;j+=16)
        {
            int x=0;
            for(int k=0;k<=15;k++)
            {
                x*=2;
                if(s[i][j+k]==1)
                {
                    x++;
                }
            }
            a[j/16][x].push_back(i);
            b2[i][j/16]=x;
        }
    }
    for(int i=0;i<65536;i++)
    {
        int x=i;
        b1[i]=0;
        while(x>0)
        {
            if(x%2==1)    b1[i]++;
            x/=2;
        }
    }
    return ;
}

char p16[64];
int p2[256];
int p6[16];
int lastans=0;
void huan()
{
    for(int i=0;i<64;i++)
    {
        int x=0;
        if(p16[i]>='0'&&p16[i]<='9')
        {
            x+=p16[i]-'0';
        }
        else
        {
            x+=p16[i]-'A'+10;
        }
        for(int j=3;j>=0;j--)
        {
            p2[i*4+j]=(x%2)^lastans;
            x/=2;
        }
    }
    for(int i=0;i<256;i+=16)
    {
        int x=0;
        for(int j=0;j<16;j++)
        {
            x*=2;
            x+=p2[i+j];
        }
        p6[i/16]=x;
    }
    return ;
}

int hh[8]={0,1,2,3,4,5,6,7};
int main()
{
    scanf("%d%d%llu%llu",&n,&m,&a1,&a2);
    gen(n,a1,a2);
    yuchuli();
    while(m--)
    {
        int k;
        scanf("%s%d",p16,&k);
        huan();
        int f=0;
        for(int i=0;i<16;i++)
        {
            for(int j1=0;j1<8;j1++)
            {
                if(hh[j1]>=a[i][p6[i]].size())    break;
                int x=0;
                for(int j2=0;j2<16;j2++)
                {
                    x+=b1[b2[a[i][p6[i]][hh[j1]]][j2]^p6[j2]];
                    if(x>k)    break;
                }
                if(x<=k)
                {
                    f=1;
                    break;
                }
            }
            if(f==1)
            {
                break;
            }
        }
        printf("%d\n",f);
        lastans=f;
    }
    return 0;
}