2019 ICPC 徐州区域赛 - A Cat（异或性质）

题目链接

题目大意

有$[1,10^{18}$个物品每个物品的价值为$i$，给出一个区间$[L,R]$的物品，只能买连续的东西其总价值为这几个连续的物品价值异或结果，问$S$最多能买多少物品。

解题思路

关于本题最重要的结论是：每个偶数和与它相邻且大于它的那个奇数异或之后结果一定为1。此外还需要知道异或运算具有交换律和结合律，任何数和它本身异或之后为$0$，任何数和$0$异或值不变。

然后这道题就差不多是模拟了，当区间长度超过$4$之后一定能把$4k$的数异或成$0$。然后就是分情况考虑，区间长度小于$4$直接暴力，大于四了，按左区间和右区间奇偶性分四个情况讨论。（写的代码略啰嗦）需要注意的地方是位运算的优先性比四则运算甚至比较运算符都低，防止错误的话在每次位运算时加上括号。

代码：

#include <iostream>

using namespace std;
typedef long long ll;
ll solve(ll l,ll r,ll s){
    ll p=r-l+1;
    if(p<5){
        if(p==1){
            if(l<=s) return 1;
            else return 0;
        }else if(p==2){
            if( (l^r)<=s) return 2;
            else if(l<=s) return 1;
            else return 0;
        }else if(p==3){
            ll t=l^(l+1)^r;
            if(t<=s) return 3;
            else if( (l^(l+1))<=s || (r^(l+1))<=s) return 2;
            else if(l<=s) return 1;
            else return 0;
        }else if(p==4){
            ll t=l^(l+1)^(l+2)^r;
            if(t<=s) return 4;
            else if( (t^r)<=s || (t^l)<=s) return 3;
            else if( (l^(l+1))<=s || ((l+1)^(l+2))<=s || ((l+2)^r)<=s) return 2;
            else if(l<=s) return 1;
            else return 0;
        }
    }else{
        ll d=p/4;
        if( (l&1) && !(r&1)){
            if(p%4){
                ll q=4*d;
                if( (l^r)<=s) return q+2;
                else if(l<=s) return q+1;
                else return q;
            }else{
                d--; ///这个有可能会漏
                ll q=4*d;
                if( (l^1^r)<=s) return q+4;
                else if( (l^1)<=s || (1^r)<=s) return q+3;
                else if(1<=s) return q+2;
                else if(l<=s) return q+1;
                else return q;
            }
        }else if( (l&1) && (r&1) ){
            ll t=p%4;
            ll q=4*d;
            if(t==1){
                if(l<=s) return q+1;
                else return q;
            }else if(t==3){
                if((l^1)<=s) return q+3;
                if(1<=s) return q+2;
                else if(l<=s) return q+1;
                else return q;
            }
        }else if( !(l&1) && (r&1) ){
            ll t=p%4;
            ll q=4*d;
            if(t){
                if(1<=s) return q+2;
                else return q;
            }else{
                return q;
            }
        }else if( !(l&1) && !(r&1) ){
            ll t=p%4;
            ll q=4*d;
            if(t==1){
                if(r<=s) return q+1;
                else return q;
            }else if(t==3){
                if((1^r)<=s) return q+3;
                else if(1<=s) return q+2;
                else return q;
            }
        }
    }
}
int main(){
    ll T,l,r,s;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld",&l,&r,&s);
        ll ans=solve(l,r,s);
        if(!ans) printf("-1\n");
        else printf("%lld\n",ans);
    }
    return 0;
}