专栏文章

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

DDiaoHantong
P11798题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq5fn28
此快照首次捕获于
2025/12/03 23:15
3 个月前
此快照最后确认于
2025/12/03 23:15
3 个月前
查看原文

题目传送门

思路

1.异或和的性质：

从 11 到 nn 的异或和 f(n)f(n) 可以通过模 44 的结果快速计算：
f(n)={nn mod 4=0，1n%4==1n+1n%4==20n%4==3f(n)=\begin{cases}n& n \bmod 4 = 0，\\ 1 & n\%4==1 \\ n+1&n\%4==2 \\ 0& n\%4==3 \end{cases}

2.目标值的计算

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

3.四种情况处理

情况一：

目标值 targettarget 为 00，找到 n≡3(mod4)n \equiv 3 \pmod 4 且在区间内。

情况二：

目标值 targettarget 为 11，找到 n≡1(mod4)n \equiv 1 \pmod 4 且在区间内。

情况三：

目标值 target≡0(mod4)target \equiv 0 \pmod 4，检查 targettarget 是否在区间内。

情况四：

目标值 target≡3(mod4)target\equiv3 \pmod 4，检查 target−1target-1 是否在区间内。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...