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

XCDRF_ · 2025-02-23 18:43:05 · 题解

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

原题传送门

更好的阅读体验

解题思路

题目要求求区间异或和，先转化成前缀异或和。

但是本题的数据范围有点大，如果每个都算出来不仅会 TLE 还会 MLE。

此时，我们打表发现，从 0 到 n 的异或和是有规律的。

令 F(n)=0\oplus1\oplus\cdots\oplus n，则有：

这样一来，我们就能很方便的算出前缀异或和。剩下的事就简单了。

题目要求 F(n)\oplus F(k-1)=x，可转化为 F(n)=x\oplus F(k-1)。令 t=x\oplus F(k-1)，也就是说我们要找到一个 n\in[l,r]，使得 F(n)=t。

下面我们分类讨论：

• 当 n\equiv 0\pmod4 时：F(n)=n \Rightarrow n=T(T\equiv 0\pmod4)。
• 当 n\equiv 1\pmod4 时：F(n)=1 \Rightarrow T=1。
• 当 n\equiv 2\pmod4 时：F(n)=n+1 \Rightarrow n=T-1(T\equiv 3\pmod4)。
• 当 n\equiv 3\pmod4 时：F(n)=0 \Rightarrow T=0。

因此：

1. 如果 T=1，则只要在区间内存在 n\equiv1\pmod4 的数即可。我们可以选区间内最小的 n\equiv1\pmod4。
2. 如果 T=0，则必须选 n\equiv3\pmod4，选区间内最小的 n\equiv3\pmod4。
3. 如果 T\not\in\{0,1\}：
   • 若 T\equiv0\pmod4，则必须有 n=T，检查 T\in[l,r]；
   • 若 T\equiv3\pmod4，则必须有 n=T-1，检查 T-1\in[l,r]；
   • 其他情况无解。

参考代码

#include<iostream>
using namespace std;
int T,l,r,k,x;
int get(int x){
    if(x%4==0) return x;
    if(x%4==1) return 1;
    if(x%4==2) return x+1;
    if(x%4==3) return 0;
}
void solve(){
    cin>>l>>r>>k>>x;
    int a=get(k-1);
    int t=a^x;
    if(t==1){
        for(int i=l;i<=r;i++)
            if(i%4==1){
                cout<<i<<'\n';
                return;
            } 
        cout<<-1<<'\n';
        return;
    }
    if(t==0){
        for(int i=l;i<=r;i++)
            if(i%4==3){
                cout<<i<<'\n';
                return;
            } 
        cout<<-1<<'\n';
        return;
    }
    if(t%4==0&&t>=l&&t<=r){
        cout<<t<<'\n';
        return;
    }
    if(t%4==3&&t-1>=l&&t-1<=r){
        cout<<t-1<<'\n';
        return;
    }
    cout<<"-1\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}

AC 记录