cdoj 491 Tricks in Bits

//无脑爆居然能过！！！！！

解：其实正解也是暴力，但是可以证明在n>6时答案一定为零。

第一步：对于任意两个数他们的二进制数要么有一半+的位是相同的，要么有一半+的位是不同的，于是首先使用与运算和异或运算一定能使一半以上的位数变成0。

那么设第一步得到的数字为x，接下来我们对x与下一个数c做与运算，x上已经为0的位数一定仍为0。

对于剩下x中为1的位数，如果c中也为1的个数比较多，那么我们首先取反再做运算，如果c中为0的位数比较多那么直接做与运算，如此一定可使x中为1的位数中一半以上的位数变为0

即每部都可以使1的个数减少一半以上，因此对于64位二进制数，最多只需要7步就可以让所以的位数全部变为0.

所以对于n>6直接输出0.对于n<=6,dfs求解

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<queue>

 #include<vector>

 #include<map>

 #include<stack>

 #include<string>

 #define LL long long

 #define ULL unsigned long long

 const int MAXN=;

 const int MAXM=;

 const int INF=;//careful because of floyed and so on

 const int MOD=;

 const unsigned long long UINF=;

 using namespace std;

 int n,T;

 ULL a[];

 ULL ans;

 void dfs(int t,ULL num){

     if (t>n){

             ans=min(ans,num);

             return;

     }

     if (ans==) return;

     if (num==){

             ans=;

             return;

     }

     dfs(t+,num&(a[t]));

     dfs(t+,num&(~a[t]));

     dfs(t+,num^(a[t]));

     dfs(t+,num^(~a[t]));

     dfs(t+,num|(a[t]));

     dfs(t+,num|(~a[t]));

 }

 int main(){

     scanf("%d",&T);

     for (int cas=;cas<=T;cas++){

             scanf("%d",&n);

             ans=UINF;

             for (int i=;i<=n;i++) scanf("%llu",&a[i]);

             if (n>){

                     ans=;

             }

             else{

                     dfs(,a[]);

                     dfs(,~a[]);

             }

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

     }

     return ;

 }

 /*

 2

 3

 1 2 3

 2

 3 6

 */

巴特西

cdoj 491 Tricks in Bits

最新文章

热门文章