UESTC 491 – Tricks in Bits [二进制+DFS]

Link

http://acm.uestc.edu.cn/#/problem/show/491

Mean

给N个整数,可以将其中几个数取反,然后在N个数两两之间插入“与或非”之一,求最终表达式的最小值。

Analysis

两个数“与”之后,1的数目一定小于原来的一半,如果不是,将数取反即可。

由于是64位整数,所以6次“与”后结果一定为0。

当N小于6时直接DFS暴力即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

#define dbg(x) cout << "\t" << #x " = " << (x) << endl

const int maxn = 110;
int N;
ll v[maxn], best;

void dfs(int d, ll cur) {
    if(d >= N) {
        best = min(best, cur);
        return;
    }
    dfs(d + 1, cur & v[d]);
    dfs(d + 1, cur & (~v[d]));
    dfs(d + 1, cur ^ v[d]);
    dfs(d + 1, cur ^ (~v[d]));
    dfs(d + 1, cur | v[d]);
    dfs(d + 1, cur | (~v[d]));
}

int main() {
    int T, kase = 0; cin >> T;
    while(T--) {
        cin >> N;
        for(int i = 0; i < N; ++i)
            cin >> v[i];
        if(N > 6) {
            cout << "Case #" << ++kase << ": " << 0 << endl;
            continue;
        }
        best = ULLONG_MAX;
        dfs(1, v[0]);
        dfs(1, ~v[0]);
        cout << "Case #" << ++kase << ": " << best << endl;
    }
    return 0;
}

欢迎留言