题解：P11798 【MX-X9-T2】『GROI-R3』XOR

DiaoHantong · 2025-02-24 19:24:17 · 题解

题目传送门

思路

1.异或和的性质：

从 1 到 n 的异或和 f(n) 可以通过模 4 的结果快速计算：

2.目标值的计算

从 k 到 n 的异或和可以转换为 f(n)\bigoplus f(k-1)，因此我们需要找到 n 使得 f(n)=x\bigoplus f(k-1)。

3.四种情况处理

情况一：

目标值 target 为 0，找到 n \equiv 3 \pmod 4 且在区间内。

情况二：

目标值 target 为 1，找到 n \equiv 1 \pmod 4 且在区间内。

情况三：

目标值 target \equiv 0 \pmod 4，检查 target 是否在区间内。

情况四：

目标值 target\equiv3 \pmod 4，检查 target-1 是否在区间内。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int yihuo(int n){
    if(n%4==0){
        return n;
    }else if(n%4==1){
        return 1;
    }else if(n%4==2){
        return n+1;
    }else{
        return 0;
    }
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        int l,r,k,x;
        cin>>l>>r>>k>>x;
        int y=yihuo(k-1);
        int cnt=y^x;
        int ans=-1;
        if(cnt%4==0){
            if(l<=cnt&&cnt<=r)ans=cnt;
        }
        if(ans==-1&&cnt%4==3){
            if(l<=cnt-1&&cnt-1<=r)ans=cnt-1;
        }
        if(ans==-1&&cnt==0){
            if(l+(3-l%4+4)%4<=r)ans=l+(3-l%4+4)%4;
        }
        if(ans==-1&&cnt==1){
            if(l+(1-l%4+4)%4<=r)ans=l+(1-l%4+4)%4;
        }
        if(ans!=-1)cout<<ans<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}