[COCI 2024/2025 #4] Xor

1

Hansang1 LV 9 MOD @ 2026-8-10 14:54:38

更好的阅读体验：https://blog.csdn.net/tenkuo/article/details/163628003

三种做法

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 5e5 + 10;
LL a[N], aa[N];
int n;
 
LL get_(LL x) {
	int j = n;
	LL res = 0;
	aa[0] = 0;
	for (int i = 1; i <= n; i ++) {
		j = max(j, i);
		while (aa[i] + aa[j] >= x && j >= i) {
			j --;
		}
		res = res + n - j;
	}
	return res;
}
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	
	LL ans = 0;
	for (int i = 0; i <= 30; i ++) {
		LL t = (1ll << (i + 1)) - 1;
		for (int j = 1; j <= n; j ++) {
			aa[j] = a[j] & t;
		}
		sort (aa + 1, aa + n + 1);
		
		LL sum1 = get_(1ll << i);
		LL sum2 = get_(1ll << (i + 1));
		LL sum3 = get_((1ll << i) + (1ll << (i + 1)));
		
		LL sum = sum1 + sum3 - sum2;
		if (sum & 1) {
			ans += (1ll << i);
		}
	}
	cout << ans << "\n";
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 5e5 + 10;
LL a[N], aa[N], b[N], c[N], d[N];
int n;
 
LL get_(LL x) {
	int j = n;
	LL res = 0;
	aa[0] = 0;
	for (int i = 1; i <= n; i ++) {
		j = max(j, i);
		while (aa[i] + aa[j] >= x && j >= i) {
			j --;
		}
		res = res + n - j;
	}
	return res;
}
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	
	LL ans = 0;
	for (int i = 0; i <= 30; i ++) {
		LL t = (1ll << (i + 1)) - 1;
		
		int bl = 0, cl = 0;
		for (int j = 1; j <= n; j ++) { 
		// 根据 a_i 的第 i 位是否为 1 分组
		// 为 1 的肯定不为 0 的大，统一排到后面去 
			if (a[j] & (1ll << i)) {   // 如果 a_i 的第 i 位为 1 
				cl ++;
				c[cl] = j; 
			}
			else {                  // 如果 a_i 的第 i 位为 0
				bl ++;
				b[bl] = j;
			}
		}
		// 注意这里 b 和 c 数组存的都是 a 的下标 
		// 基数排序是稳定的，如果两个数的第 i 位相同
		// 并不会改变它们的相对位置，即按照上一轮排序的相对位置
		// 而上一轮就是根据前 i - 1 位的大小 
		for (int j = 1; j <= bl; j ++) {
			d[j] = a[b[j]];   // 选已经分好的下标 
		}
		for (int j = 1; j <= cl; j ++) {
			d[bl + j] = a[c[j]];
		}
		for (int j = 1; j <= n; j ++) {
			a[j] = d[j];    // 复制回 a 数组 
		}
		
		for (int j = 1; j <= n; j ++) {
			aa[j] = a[j] & t;    // 取前 i 位 
		}
		
		LL sum1 = get_(1ll << i);
		LL sum2 = get_(1ll << (i + 1));
		LL sum3 = get_((1ll << i) + (1ll << (i + 1)));
		
		LL sum = sum1 + sum3 - sum2;
		if (sum & 1) {
			ans += (1ll << i);
		}
	}
	cout << ans << "\n";
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 5e5 + 10;
LL a[N], aa[N], b[N];
int n;
 
LL get_(LL x) {
	int j = n;
	LL res = 0;
	aa[0] = 0;
	for (int i = 1; i <= n; i ++) {
		j = max(j, i);
		while (aa[i] + aa[j] >= x && j > i) { // 这里要改下，保证 j != i - 1
		// 即对应下标不会取到 i 
			j --;
		}
		res = res + n - j;
	}
	return res;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	
	LL ans = 0;
	for (int i = 0; i <= 30; i ++) {
		LL t = (1 << i) - 1, sum = 0;
		
		for (int j = 1; j <= n; j ++) {
			aa[j] = a[j] & t;
		}
		
		sum += get_(1ll << i);
		
		int bl = 0;
		for (int j = 1; j <= n; j ++) {
			if (a[j] & (1ll << i)) {
				sum += (n - 1);
			}
			else {
				bl ++;
				b[bl] = a[j];
			}
		}
				
		if (sum & 1) {
			ans += (1ll << i);
		}
			
		for (int j = 1; j <= n; j ++) {
			if (a[j] & (1ll << i)) {
				bl ++;
				b[bl] = a[j];
			}
		}
				
		memcpy(a, b, sizeof(a));
	}
	
	for (int i = 1; i <= n; i ++) {
		ans = ans ^ (a[i] + a[i]);
	}
		
	cout << ans << "\n";
	return 0;
}

1

Raoxuanrui01 LV 8 @ 2026-8-10 10:00:03

考虑拆位，思考第 $i$ 位什么情况下会在 $a_j+a_k$ 中出现。

首先更高位肯定是没用的，所以将所有的 $a_j$ 对 $2^{i+1}$ 取模，记取模后的数为 $b_j$ ，发现 $b_j+b_k$ 的结果中第 $i$ 位为一当且仅当 $2^{i}\le b_j+b_k <2^{i+1}$ 或 $2^{i+1}+2^{i}\le b_j+b_k$ （注意到 $b_j+b_k$ 必定 $<2^{i+2}$ ）。问题就转化成了求满足上述式子的 $(j,k)$ 的对数的奇偶性。

对 $b$ 数组进行排序，那么对于一个递增数组中从前往后的每一个数，满足某个数加上它小于等于某个定值的数一定是存在于一个 $b_1$ 开头的区间且右端点不断向左移动，所以考虑用一个变量存储一下就行。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[500005];
long long b[500005];
long long mx;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	long long ans=0;
	b[0]=0;
	for(int i=0;i<31;i++){
		long long s1=(1LL<<i),s2=(1LL<<(i+1)),s3=((1LL<<i)+(1LL<<(i+1)));
		for(int j=1;j<=n;j++){
			b[j]=a[j]%(1LL<<(i+1));
		}
		sort(b+1,b+n+1);
		int w1=-1,w2=-1,w3=-1,l1,l2,l3;
		//w1即以前的数满足+bj后<s1，所以不能取
		//w2即以前的数满足+bj后<s2，所以可以取
		//w3即以前的数满足+bj后<s3，所以不能取（考虑>=2^i+2^{i+1}）
		for(int j=1;j<=n;j++){
			if(w1==-1 && b[j]+b[j]>=s1){
				w1=j;
			}
			while(b[w1]+b[j]>=s1 && w1){
				w1--;
			}
			if(w2==-1 && b[j]+b[j]>=s2){
				w2=j;
			}
			while(b[w2]+b[j]>=s2 && w2){
				w2--;
			}
			if(w3==-1 && b[j]+b[j]>=s3){
				w3=j;
			}
			while(b[w3]+b[j]>=s3 && w3){
				w3--;
			}
			if(w1==-1){
				l1=j;
			}
			else{
				l1=w1;
			}
			if(w2==-1){
				l2=j;
			}
			else{
				l2=w2;
			}
			if(w3==-1){
				l3=j;
			}
			else{
				l3=w3;
			}
			ans^=(j-l3+l2-l1)%2*(1<<i);
		}
	}
	cout<<ans;
	return 0;
}

1

Benny LV 10 MOD @ 2026-8-10 9:46:50

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
int n,a[500010];
int q0[500010],q1[500010],q0i,q1i;//基数排序用的 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int ans=0;
	for(int i=0;i<=30;i++){
		q0i=q1i=0;
		for(int j=1;j<=n;j++){//由于前i-1位已经排好了，所以只需要根据第i位的大小进行排序 
			if((a[j]>>i)&1)q1[++q1i]=a[j];
			else q0[++q0i]=a[j];
		}
		for(int j=1;j<=q0i;j++){//第i位为0的放前面 
			a[j]=q0[j];
		}
		for(int j=1;j<=q1i;j++){//第i位为1的放后面 
			a[j+q0i]=q1[j];
		}
		//注意排序必须是稳定的，保持前i-1位的顺序 
		int l=n+1,r=n,k=n+1;
		//l~r:和a[j]的和在2^i~2^(i+1)-1的数，由于a[j]是递增的，所以l和r是递减的
		//k~n:和a[j]的和大于等于2^i+2^(i+1)的数，k也是递减的 
		ll cnt=0;
		for(int j=1;j<=n;j++){
			while(l>1&&a[l-1]%(1ll<<i+1)>=(1ll<<i)-a[j]%(1ll<<i+1))l--;//双指针 
			while(r>=1&&a[r]%(1ll<<i+1)>(1ll<<i+1)-1-a[j]%(1ll<<i+1))r--;
			while(k>1&&a[k-1]%(1ll<<i+1)>=(1ll<<i+1)+(1ll<<i)-a[j]%(1ll<<i+1))k--;
			cnt+=r-l+1+n-k+1;
		}
		for(int j=1;j<=n;j++)if(((a[j]<<1)>>i)&1)cnt++;//特判一个数自己加自己，由于自己加自己只会加一次，还有一次要补上 
		cnt>>=1;
		if(cnt&1)ans^=1<<i;
	}
	cout<<ans;
	return 0;
}

1

Yangzhichao LV 10 @ 2026-8-10 9:14:51

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 500010
int n;
int a[N];
int num[N];
int fac[35];
int getnum(int x){
	int l=1,r=n;
	int cnt=0;
	num[0]=0;
	while(l<=n){
		while(l<=r&&num[l]+num[r]>=x)r--;
		cnt+=min(n-l+1,n-r);
		l++;
	}
	return cnt;
}
signed main(){
	fac[0]=1;for(int i=1;i<=31;i++)fac[i]=fac[i-1]*2;
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	int ans=0;
	for(int j=0;j<=30;j++){
		int cnt=0;
		for(int i=1;i<=n;i++){
			num[i]=a[i]%fac[j+1];
		}
		sort(num+1,num+n+1);
		cnt+=getnum(fac[j]);
		cnt-=getnum(fac[j+1]);
		cnt+=getnum(fac[j]+fac[j+1]);
		if(cnt&1)ans+=fac[j];
	}
	
	cout<<ans<<'\n';
	
	return 0;
}

1

yanchengyi2024 LV 9 @ 2026-8-10 8:56:06

正常的码风

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,a[N],b[N],c[N],d[N],c1,c2,ans;
bool bit(int s,int i){return s>>i&1;}
int mod(int s,int i){return s&((1<<i)-1);}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int k=0;k<=30;k++)
	{
		bool res=0;
		if(n+1&1)for(int i=1;i<=n;i++)res^=bit(a[i],k);
		if(k)
		{
			c1=c2=0;
			for(int i=1;i<=n;i++)
			{
				if(mod(a[i],k)<1<<k-1)b[++c1]=i;
				else c[++c2]=i; 
			}
			for(int i=1;i<=c1;i++)d[i]=a[b[i]];
			for(int i=1;i<=c2;i++)d[c1+i]=a[c[i]];
			for(int i=1;i<=n;i++)a[i]=d[i];
			for(int i=1,j=n+1;i<=n;i++)
			{
				while(j>i&&mod(a[i],k)+mod(a[j-1],k)>=1<<k)j--;
				j=max(j,i);
				if(n-j+1&1)res^=1;
			}
		}
		if(res)ans^=1<<k;
	}
	printf("%d\n",ans);
	return 0;
}

dengyanzhi2024 @ 2026-8-10 9:08:57

请问bit和mod有什么用？

1

admin LV 10 SU @ 2026-8-6 15:55:14

我们按位计算答案。

设当前枚举到了第 $k$ 位，下文计 $b_i$ 表示 $a_i$ 在第 $k$ 位的值， $c_i$ 表示 $a_i$ 前 $k-1$ 位的值（当 $k=1$ 时 $c_i=0$ ）。

$a_i+a_j$ 的第 $k$ 位为 $1$ ，当且仅当 $[b_i=1] \operatorname{xor} [b_j=1] \operatorname{xor} [c_i+c_j\ge 2^k]=1$（其实就是一个不考虑进位的加法），易得答案的第 $k$ 位为 $$\displaystyle\bigoplus _{1\le i\le j\le n}[b_i=1] \operatorname{xor} [b_j=1] \operatorname{xor} [c_i+c_j\ge 2^k]$$。

我们讲这三个贡献分开算，前两个是容易的，做第三个时，考虑讲 $c_i$ 排序，然后用双指针维护。排序的复杂度为 $O(\log n)$ ，再加上枚举 $k$ 的复杂度，总复杂度为 $O(n\log n \log maxa)$ ，可以拿到五十二分。

瓶颈在于排序，我们考虑用类似于基数排序的方法来实现这个排序，在从小到大枚举 $k$ 时，若 $c_i=1$ ，就将 $i$ 放到序列的后面，若 $c_i=0$ ，就将 $i$ 放到序列的前面，相等的 $c$ 之间的相对位置不改变，这样总复杂度就由 $O(n\log n \log maxa)$ 降为 $O(n\log maxa)$ 了。

代码：

#include<bits/stdc++.h>
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
#define per(i, j, k) for(int i=(j); i>=(k); --i)
#define print(a, len) cout<<#a<<"= "; rep(i, 0, len-1) cout<<(a)[i]<<' '; cout<<endl;
using namespace std;

const int N=5e5+7;
int n, a[N], b[N], c[N], d[N], c1, c2, ans;
int buc[N];
inline bool bit(int s, int i){return s>>i&1;}
inline int mod(int s, int k){return s&((1<<k)-1);}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	rep(i, 1, n) cin>>a[i];
	rep(k, 0, 30){
		auto bit=[&](int i){return a[i]>>k&1;};
		auto mod=[&](int i){return a[i]&((1<<k)-1);};
		bool res=0;
		if(n+1&1) rep(i, 1, n) res^=bit(i);
		if(k){
			c1=c2=0;
			rep(i, 1, n) if(mod(i)<1<<k-1) b[++c1]=i; else c[++c2]=i;
			rep(i, 1, c1) d[i]=a[b[i]];
			rep(i, 1, c2) d[c1+i]=a[c[i]];
			rep(i, 1, n) a[i]=d[i];
			int pos=n+1;
			rep(i, 1, n){
				while(pos>i && mod(i)+mod(pos-1)>=1<<k) --pos;
				pos=max(pos, i);
				if(n-pos+1&1) res^=1;
			}
		}
		if(res) ans^=1<<k;
	}
	cout<<ans;
}

6 条题解

三种做法

信息

状态

开发

支持

关于

6 条题解

三种做法

[COCI 2024/2025 #4] Xor

信息

状态

开发

支持

关于

还没有账户？

登录