专栏文章

XOR题解

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

文章操作

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

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

题目传送门

题目大意

定义Si,jS_{i,j}为i⊕(i+1)⊕……⊕ji\oplus(i+1)\oplus……\oplus j，其中⊕\oplus表示异或，给出多组数据，每组数据给出 l,r,k,xl,r,k,x，求一个数n∈[max(i,k),r]n\in[max(i,k),r]，满足Sk,n=xS_{k,n}=x，若没有则输出-1。

题目做法

思路

思路一

最简单的思路是，在[max(i,k),j][max(i,k),j]中枚举n。那么我们很容易有以下代码
CPP
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T,l,r,k,x;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&l,&r,&k,&x);
        bool b=1;
        for(int i=k,s=0;i<=r;++i)
        {
            s^=i;
            if(i>=l&&s==x)
            {
                printf("%d\n",i);
                b=0;
                break;
            }
        }
        if(b) printf("-1\n");
    }
}
结果喜提TLE TLE 所以我们应该换一种思路：

思路二

记CnC_n为1⊕2⊕...⊕n1\oplus2\oplus...\oplus n,那么Sk,n=Cn⊕Ck−1S_{k,n}=C_n\oplus C_{k-1} 即解Cn=x⊕Ck−1C_n=x\oplus C_{k-1}
这样我们就计算得出了CnC_n
再观察一下CnC_n,CnC_n的前128项：
CPP
1 3 0 4 1 7 0 8 1 11 0 12 1 15 0 16 1 19 0 20 1 23 0 24 1 27 0 28 1 31 0 32 1 35 0 36 1 39 0 40 1 43 0 44 1 47 0 48 1 51 0 52 1 55 0 56 1 59 0 60 1 63 0 64 1 67 0 68 1 71 0 72 1 75 0 76 1 79 0 80 1 83 0 84 1 87 0 88 1 91 0 92 1 95 0 96 1 99 0 100 1 103 0 104 1 107 0 108 1 111 0 112 1 115 0 116 1 119 0 120 1 123 0 124 1 127 0 128
归纳可知：
(n%4==1)(n\%4==1)时，Cn=1C_n=1；
(n%4==2)(n\%4==2)时，Cn=n+1C_n=n+1；
(n%4==3)(n\%4==3)时，Cn=0C_n=0；
(n%4==0)(n\%4==0)时，Cn=nC_n=n；
对计算出来的CnC_n进行逆运算，将nn在[max(l,k),r][max(l,k),r]中判断对应，就大功告成了！
错误代码（小细节写崩了，希望各位指正） 不过至少没有TLE了

评论

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

正在加载评论...