UESTC 491 Tricks in Bits

Description

Given $N$ unsigned $64$-bit integers, you can ​

​bitwise NOT​

​​ each or not. Then you need to add operations selected from ​

​bitwise XOR​

​​,​

​bitwise OR​

​​ and ​

​bitwise AND​

​, between any two successive integers and calculate the result. Your job is to make the result as small as possible.

Input

The first line of the input is $T$ (no more than $1000$), which stands for the number of test cases you need to solve.

Then $T$ blocks follow. The first line of each block contains a single number $N$ ($1 \leq N \leq 100$) indicating the number of unsigned $64$-bit integers. Then $n$ integers follow in the next line.

Output

For every test case, you should output ​

​Case #k:​

​ first, where $k$ indicates the case number and counts from $1$. Then output the answer.

Sample Input

2 

3 

1 2 3 

2 

3 6

Sample Output

Case #1: 0 

Case #2: 1

Hint

• Case #$1$: ​

  ​1|2^3 = 0​

  ​
• Case #$2$: ​

  ​3&(~6) = 1​

  ​

The ​

​bitwise NOT​

​, is a unary operation that performs logical negation on each bit, forming the ones' complement of the given binary value. Digits which were $0$ become $1$, and vice versa.

The ​

​bitwise OR​

​ takes two bit patterns of equal length, and produces another one of the same length by matching up corresponding bits (the first of each; the second of each; and so on) and performing the logical inclusive or operation on each pair of corresponding bits. In each pair, the result is $1$ if the first bit is $1$ or the second bit is $1$ or both bits are $1$; otherwise, the result is $0$.

The ​

​bitwise XOR​

​​ takes two bit patterns of equal length and performs the ​

​logical XOR​

​ operation on each pair of corresponding bits. The result in each position is $1$ if the two bits are different, and $0$ if they are the same.

可以证明，用x^y>x&(~y) 所以运算符号其实只有&，然后就是每个数取不取反的问题，

而这意味着每次操作必然会使1的数目减少一半以上，所以64位，最多6次操作就会只剩一个1

#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
const LL INF = ((LL)1 << 64) - 1;
LL a[maxn];
int n, T, t = 0;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%llu", &a[i]);
    if (n > 6) printf("Case #%d: 0\n", ++t);
    else
    {
      LL ans = INF;
      for (int i = 0; i < (1 << n); i++)
      {
        LL res = INF;
        for (int j = 0; j < n; j++) 
          if (i&(1 << j)) res &= a[j]; else res &= a[j] ^ INF;
        ans = min(ans, res);
      }
      printf("Case #%d: %llu\n", ++t, ans);
    }
  }
  return 0;
}