自动搬运

查看原文

来自洛谷，原作者为

	XCDRF_ May you,the beauty of this world,always shine.

搬运于2025-08-24 23:10:20，当前版本为作者最后更新于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)=\begin{cases} n,&n\equiv 0\pmod4,\\ 1,&n\equiv 1\pmod4,\\ n+1,&n\equiv 2\pmod4,\\ 0,&n\equiv 3\pmod4. \end{cases} $$

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

题目要求 $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 记录