2015
04-15

Magic Bitwise And Operation

Given n integers, your task is to pick k out of them so that the picked number are minimum when do bitwise “AND” among all of them.
For example, there are three integers 5, 6 and 7. You are asked to pick two of them. Your possible strategy is (5, 6), (5, 7) or (6, 7). The values when do bitwise and all the picked numbers together are as follows:
5 and 6 = 4
5 and 7 = 5
6 and 7 = 6
The smallest one is 4.

There are multiple test cases for this problem. The first line of the input contains an integer denoting the number of test cases.
For each test case, there are two integers in the first line: n and k, denoting the number of given integers and the number of integers you are asked to pick out. n <= 40
The second line contains the n integers. You may assume that all integers are small than 2^60.

Notes: There are about one thousand randomly generated test cases. Fortunately 90% of them are relatively small.

There are multiple test cases for this problem. The first line of the input contains an integer denoting the number of test cases.
For each test case, there are two integers in the first line: n and k, denoting the number of given integers and the number of integers you are asked to pick out. n <= 40
The second line contains the n integers. You may assume that all integers are small than 2^60.

Notes: There are about one thousand randomly generated test cases. Fortunately 90% of them are relatively small.

3
3 2
5 6 7
8 2
238 153 223 247 111 252 253 247
40 10
1143632830316675007 558164877202423550 1152356080752164603 1143911006781551605 1132655005501751263
1152919305583327167 1141662230660382702 862439259920596463 1151777428397603327 1008771132016295871
855666336963428351 1151795583225167807 1152634943314572791 1071856693060561407 1132650872803426303
1124211056982081471 1152917106425982911 1152815392070041535 1080863910568853481 288230371856350975
1080720560532488126 864686455262281727 576460673919991167 574191342855241589 1152233760050118651
1152921504605798263 1152912708241186815 1079738008506187487 1075796261476483027 1080854478820730879
1152885219917823999 1151725162940854259 1147529498501577715 571956602920235519 1134545630643616248
1152921218991521790 1152921496000052703 1142788250826440703 1151654831778151421 1152780747522637695

Case #1: 4
Case #2: 9
Case #3: 36028797086245424

/********************************************************************************
剪个枝就过了～比赛的时候没什么人做，主要是因为位运算的威慑力太大了～
********************************************************************************/
#include <iostream>
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <bitset>
#include <cstdio>
#include <memory>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

#define lowbit(x) ( (x) & ( (x) ^ (x - 1) ) )

//typedef long long LL;
//typedef unsigned long long ULL;
typedef __int64 LL;
typedef unsigned __int64 ULL;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;

typedef map<int, int>::iterator MI;
typedef vector<int>::iterator VI;
typedef list<LL>::iterator LI;
typedef set<int>::iterator SI;

const int INF_INT = 0x3f3f3f3f;
const LL INF_LL = 0x7fffffffffffffff;
const double oo = 10e9;
const double eps = 10e-7;
const double PI = acos(-1.0);

const int MAXN = 44;

int test, n, m;
LL ans, arr[MAXN];

bool check(int id, LL buf)
{
for (int i = id + 1; i < n; ++i)
{
buf &= arr[i];
}
return buf < ans;
}
void dfs(int crt, int step, LL buf)
{
ans = min(ans, buf);
if (step >= m)
{
return ;
}
for (int nxt = crt + 1; nxt < n; ++nxt)
{
LL tmp = buf & arr[nxt];
if (!check(nxt, tmp))
{
continue ;
}
dfs(nxt, step + 1, tmp);
}
return ;
}
void ace()
{
int cas = 1;
for (scanf("%d", &test); test--; ++cas)
{
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i)
{
scanf("%I64d", arr + i);
}
sort(arr, arr + n);
ans = INF_LL;
for (int i = 0; i < n; ++i)
{
dfs(i, 1, arr[i]);
}
printf("Case #%d: %I64d\n", cas, ans);
}
return ;
}
int main()
{
ace();
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。