太棒了!这题我会做!
思路:1·异或操作只会改变某一位而不互相影响
2·要让结果最大就用贪心
所以,将x从大到小排序,记结果为ans,对于每一个x,从高位到低位依次看一看能不能让ans的一位由0变成1并且不超过x,把ans每一位都检查过去,即使高位填补了1,低位能增大ans的就尽可能增大,这是贪心嘛。
代码:
#include<bits/stdc++.h>
using namespace std;
int const N=53;
int a[N];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int n,i,ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1,cmp);
ans=a[1];
for(i=2;i<=n;i++)
{
int k=-1,m=ans;
while(m)
{
m>>=1;
k++;
}//找到ans最高位
for(;k>=0;k--)
{
if((ans&(1<<k))==0&&(1<<k)<=a[i])
{
ans|=(1<<k);
a[i]-=(1<<k);
}
}//依次比较ans和x的每一位
}
printf("%d",ans);
return 0;
}