专栏文章

P11651 [COCI 2024/2025 #4] Xor 题解

hhuangleyi0129暴力出奇迹
P11651题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqd1vg1
此快照首次捕获于
2025/12/04 02:48
3 个月前
此快照最后确认于
2025/12/04 02:48
3 个月前
查看原文
结果为一堆数异或，故考虑逐位确定。
对于第 ww 位，只需要考虑 aia_i 第 ww 位为 11 的数量（需要乘上 nn 或 n−1n-1，视其部分意义而定）和 ai+aja_i+a_j 在第 ww 位产生进位的数量。
由于是异或运算，只需关注此数量的奇偶性，故直接加起来即可。
具体地，对于第二项，在有序数组中双指针即可计算。
枚举位的同时做一个按位的基数排序即可做到 O(nw)O(nw)，其中 ww 取 3030。
代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=500005,W=30;
int a[N],b[N],n,ans;
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	int u,j;
	long long cnt;
	for(int w=0;w<=W;++w)
	{
		u=(1<<w)-1,j=n+1,cnt=0;
		for(int i=1;i<n;++i)
		{
			while(j-1>i&&(a[j-1]&u)+(a[i]&u)>u)
				--j;
			if(j<=i)
				j=i+1;
			cnt+=n-j+1;
		}
		j=0;
		for(int i=1;i<=n;++i)
			if((a[i]>>w)&1)
				cnt+=n-1;
			else
				b[++j]=a[i];
		if(cnt&1)
			ans|=1<<w;
		for(int i=1;i<=n;++i)
			if((a[i]>>w)&1)
				b[++j]=a[i];
		memcpy(a,b,sizeof a);
	}
	for(int i=1;i<=n;++i)
		ans^=(a[i]+a[i]);
	cout<<ans;
	return 0;
}

评论

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

正在加载评论...