美妙的数字(number.c/.cpp/.pas)
题目描述
黄巨大认为非负整数是美妙的，并且它的数值越小就越美妙。当然0是最美妙的啦。
现在他得到一串非负整数，对于每个数都可以选择先对它做二进制非运算（模二意义下0、1互换，注意前导0也要交换），然后在任意相邻的两个数之间插入二进制与、二进制或，或者二进制异或。现在他想知道这样计算完产生的最美妙的数字是多少。
一共T组数据。对于每组数据，第一行一个n，表示这组数据中一串数有多少个。下面n个非负整数，表示这串数。
样例输入
2
2
3 6
3
1 2 3
样例输出
1
0
样例解释：
3 & (! 6) = 1
1 & 2 ^ 3 = 0
数据规模
对于50%数据，1<=N<=6,1<=a[i]<=2^20-1
对于100%数据，1<=N<=100,1<=T<=10,1<=a[i]<=2^63-1
原题vijos1904学姐的幸运数字
此题有一个很厉害的结论：对于n>=8的情况，一定有一种方案使得答案为0
所以剩下的直接爆搜就好了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define inf 9223372036854775807ll
#define LL long long
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
inline LL min(LL a,LL b){return a<b?a:b;}
int n;
LL ans;
LL a[100010];
LL b[100010];
inline LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void dfs(int x,LL now)
{
if (x==n+1)
{
ans=min(ans,now);
return;
}
LL test=now;
test=now&a[x];dfs(x+1,test);
test=now&b[x];dfs(x+1,test);
test=now^a[x];dfs(x+1,test);
test=now^b[x];dfs(x+1,test);
test=now|a[x];dfs(x+1,test);
test=now|b[x];dfs(x+1,test);
}
inline void work(int rnk)
{
n=read();
for(int i=1;i<=n;i++)cin>>a[i];
if (n>=8)
{
printf("0\n");
return;
}
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
b[i]=inf-a[i];
}
ans=min(a[1],b[1]);
dfs(2,a[1]);
dfs(2,b[1]);
cout<<ans<<endl;
}
int main()
{
int T=read();
for (int i=1;i<=T;i++)work(i);
return 0;
}