51Nod2526 最大异或和

Problem

给定??个数??1…????，请你选择n个数??1…????，使得??1<=??1,??2<=??2......，并且??1 ?????? ??2 ?????? ??3 … ????的值尽量大。问这个最大的异或和是多少。

??≤100 , 0≤????≤1e9

Solution

拆成二进制位，由于最小可以为0，每一位保持一个为1就可以，多的可以变成下面所有1。

从最高位开始扫，这一位出现1个1，ans这一位就为1，出现俩，后面所有的都为1。

Code

#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
#define mem(ss) memset(ss,0,sizeof(ss))
#define fo(d,s,t) for(int d=s;d<=t;d++)
#define fo0(d,s,t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;

const ll mod=1e9+7;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;}
int n,a[120];
int f[120][35];
int ans[35];
int main(){
    scanf("%d",&n);
    fo(i,1,n){
        scanf("%d",&a[i]);
    }
    fo(i,1,n){
        fo0(j,32,1){
            if(a[i]&1){
                f[i][j]=1;
            }
            a[i]>>=1;
        }
    }
    fo(i,1,32){
        int cnt=0;
        fo(j,1,n){
            if(f[j][i]){
                ans[i]=1;
                cnt++;
            }
        }
        if(cnt>=2){
            fo(j,i+1,32){
                ans[j]=1;
            }
            break;
        }
    }
    int anss=0;
    fo(i,1,32){
        anss<<=1;
        anss+=ans[i];
    }
    printf("%d\n",anss);
    return 0;
}

51Nod2526 最大异或和

原文：https://www.cnblogs.com/sz-wcc/p/11663818.html