题解：P17731 [ICPC 2019 Xuzhou R] Cat

· · 题解

题目大意

给你三个数，L、R、S，求 [L,R] 里任意一段区间的异或和不超过 S 的最大值。

数据范围：1\le T\le 5\times 10^5，1\le L\le R\le 10^{18}

思路

数据范围很大，不能一个一个去枚举，下面给出一些数，找找规律：

0\oplus 1\oplus 2\oplus 3=0 4\oplus 5\oplus 6\oplus 7=0 8\oplus 9\oplus 10\oplus 11=0 \ldots\ldots

发现每 4 个数的异或和都是 0，原因也很简单，相邻两个数（偶小奇大）的异或和为 1，连续两组这样的数就是 1\oplus 1=0。

那也就是说不需要全部都枚举完，中间的都是 0，不用管，只用看两边的数异或完是否符合要求，如果小于等于 S，那就存入答案。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
uint8_t buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
ll rd(){
    ll x=0,f=1,ch=gc();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=gc();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=gc();
    }
    return x*f;
}
void write(ll x){
    if(x<0){
        x*=-1;
        putchar('-');
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
ll check(ll x,ll y){
    ll xors=0;
    if(x>y||x<0||y<0){//不符合要求的去掉
        xors=LLONG_MAX;
    }else{//剩下的直接枚举两边
        for(ll i=x;i<=x+3-x%4;i++){
            xors^=i;
        }
        for(ll i=y;i>=y-y%4;i--){
            xors^=i;
        }
    }
    return xors;
}
ll t,ans,l,r,s,L,R;
int main(){
    t=rd();
    while(t--){
        ans=0;
        l=rd();
        r=rd();
        s=rd();
        L=(l%4==0?0:4-l%4);
        R=r%4+1;
        for(ll i=0;i<=L;i++){
            for(ll j=0;j<=R;j++){
                ll x=l+i,y=r-j;
                if(check(x,y)<=s){
                    ans=max(ans,y-x+1);
                }
            }
        }
        if(ans==0){//如果没有能买的，就输出-1
            ans=-1;
        }
        write(ans);
        putchar('\n');
    }
    return 0;
}