vijos1904 学姐的幸运数字

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

题目链接：vijos1904

正解：搜索

解题报告：

　　考虑&操作而言，与一个数的&，至少会导致$1$的个数减半，因为一个数和它的非的$1$显然分布在不同位置，而我可以选择把它和它的非操作的结果取个$min$，容易发现，因为有$64$位，最多$7$次操作就能使得答案为$0$.

　　所以其实$n>=7$的话就不用做了，那么只有$n<=6$的情况，就爆搜就好了。

//It is made by ljh2000

//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <vector>

#include <cstdio>

#include <string>

#include <queue>

#include <cmath>

#include <ctime>

#define lc root<<1

#define rc root<<1|1

#define reg(i,x) for(int i=first[x];i;i=nxt[i])

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const int MAXN = 150;

int n;

ULL a[MAXN],ans;

inline ULL getint(){

    ULL w=0; char c=getchar(); while(c<'0'||c>'9') c=getchar();

	while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return w;

}

inline void dfs(int x,ULL val){

	if(x==n+1) {

		if(val<ans) ans=val;

		return ;

	}

	dfs(x+1,val^a[x]);	dfs(x+1,val^(~a[x]));

	dfs(x+1,val&a[x]);	dfs(x+1,val&(~a[x]));

	dfs(x+1,val|a[x]);	dfs(x+1,val|(~a[x]));

}

inline void work(){

	int T=getint(),Case=0;

	while(T--) {

		n=getint(); for(int i=1;i<=n;i++) a[i]=getint();

		if(n>=7) { ans=0; }

		else {

			ans=0; ans=~ans;

			dfs(2,a[1]);

			dfs(2,~a[1]);//!!!

		}

		printf("Case #%d: %llu\n",++Case,ans);

	}

}

int main()

{

    work();

    return 0;

}

//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。