XOR题解

FUUSA · 2025-02-23 17:04:27 · 题解

[题目传送门]()

题目大意

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

题目做法

思路

思路一

最简单的思路是，在[max(i,k),j]中枚举n。那么我们很容易有以下代码

#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 所以我们应该换一种思路：

思路二

记C_n为1\oplus2\oplus...\oplus n,那么S_{k,n}=C_n\oplus C_{k-1} 即解C_n=x\oplus C_{k-1}

这样我们就计算得出了C_n

再观察一下C_n,C_n的前128项：

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

归纳可知：