当前位置：网站首页>P5514 [MtOI2019]永夜的报应(位运算)

P5514 [MtOI2019]永夜的报应(位运算)

2022-07-29 17:25:00 【.Ashy.】

大意：

给出 n 个非负整数，这 n 个非负整数可以被分为任意组，定义每组的权值为每组的所有数的异或和，求出最小的所有组的权值和；

思路：

我们需要一个异或的一个非常重要的性质

a ^ b ≤ a + b

当我们把 n 个数分为 n 组的时候权值就是所有数的加和，这时权值最大，我们每找两个数做一次异或操作权值和就小一点，显而易见，所有组权值和最小的时候就是一次把所有数分为一组，所有数做异或操作，这时就不会有组与组之间的加和操作，取而代之的是异或操作，保证了权值和最小；

#include<bits/stdc++.h>
using namespace std;
      
#define fi first
#define se second 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e4+10;
const int NN = 1e6+10;
const int pp = 1e9+9;
typedef pair<int,int>PII;

ll n,ans,t;

signed main()
{
    
	cin>>n;
	cin>>ans;
	for(int i=2;i<=n;i++)
	{
    
		cin>>t;
		ans^=t;
	}
	cout<<ans;
	
}