C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 2526 最大异或和

Problem

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

𝑛≤100 , 0≤𝑥𝑖≤1e9

Solution

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/44945/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!