2526 最大异或和（思维题，“异或和最大”）_51nod2526最大异或和给定

题目描述：

2526 最大异或和

给定nn个数x1…xnx1…xn，请你选择n个数p1…pnp1…pn，

使得p1<=x1,p2<=x2......p1<=x1,p2<=x2......，并且p1xorp2…pnp1xorp2…pn的

值尽量大。问这个最大的异或和是多少。

n≤100,0≤xi≤109n≤100,0≤xi≤109

 收起

输入

第一行一个正整数 n 。
第二行 n 个非负整数表示 x[1...n] 。

输出

一行一个数表示答案。

输入样例

3
2 2 2

输出样例

3

思路：

          从每个数的高位开始考虑，如果为1，且答案ans当前该位置为0，

则一定可以得到一个答案等于ans|该位置，若ans该位置已经为1，那么

ans后面的位置可以被全部置为1，继续考虑下一个数。详情见代码。

代码实现：

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<set>
#include<algorithm>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e5+100;
const int M=4e5+100;
int arr[N];
int main(){
	int n;
	int ans=0;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>arr[i];
		}
		for(int i=1;i<=n;i++){
			for(int j=31;j>=0;j--){
				if(arr[i]>>j&1){
					if(ans>>j&1){
						ans|=1<<j-1;
						break;
					}else{
						ans|=1<<j;
					}
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
	
} 

THE END；