三途川的摆渡人

小红这天来到了三途川，发现这里有一个摆渡人，名字叫小町。小町的职责是将一些灵魂运送到冥界。每个灵魂有一个特性，用整数$a_i$表示。但小町非常喜欢偷懒，她只想运送尽可能少的灵魂然后摸鱼。

已知当船上所有灵魂特性的 位与运算 正好等于$0$时，船才可以开动。小町想让小红帮忙抛弃掉尽可能多的灵魂（但不能全抛弃），这样自己才能最大限度的偷懒。请你帮小红计算出可以抛弃的灵魂的最多数量。

输入描述

本题有多组数据，每组第一行一个整数$n$，表示灵魂数量；第二行$n$个整数$a_i$表示灵魂特性（$0\leq a_i\leq n$）。

输出描述

对于每组测试数据，输出一行一个整数表示答案。

如果无解，请输出-1。否则输出一个整数，代表小町可以抛弃的最多灵魂数量。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
输入
复制
2
5
7 3 3 2 5
5
2 14 6 30 10
输出
3
-1
说明
第一个测试数据，抛弃掉前三个灵魂，剩下的两个灵魂与运算恰好为0（2 & 5 = 0），因此船可以开动。
第二个测试数据，显然无论如何，船都是不能开动的。

解题思路

换句话说，要选择尽可能少的数，使得他们相与为0，即保证二进制的每一位至少包含1个0；

由于数据最大不超过127，令a[i] = 127 - a[i]，那么问题转化为选择尽可能少的数，使得1能覆盖整个二进制所有数位。

可以通过DFS暴力枚举所有数字选和不选，但是显然可以进行很多剪枝优化：

  • IDA*： 限制搜索深度，并且设计估价函数计算至少还需要选几个数；

  • 每次枚举每一列选择最少的情况

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 2e5 + 10,M = 1 << 7;

int n,t;
int a[N];
vector<vector<int>> col(7); //记录每一位都有哪些选择
int log2[M];    //预处理计算log2，用于确定列数/数位

int lowbit(int x) {
    return x & -x;
}

//估价函数，每次将给数位所有选择选上，以保证最小待选次数
int h(int state) {
    int res = 0;
    for(int i = (1 << 7) - 1 - state; i ;i -= lowbit(i)) {
        int c = log2[lowbit(i)];
        ++ res;
        for(auto row : col[c]) i &= ~row;
    }
    return res;
}

bool dfs(int depth,int state) {
    if(!depth || h(state) > depth) return state == (1 << 7) - 1;    //depth为0或者估价大于depth，返回
    int t = -1;
    for(int i = (1 << 7) - 1 - state; i; i -= lowbit(i)) {
        int c = log2[lowbit(i)];
        if(t == -1 || col[c].size() < col[t].size()) t = c; //选择选择最小的数位
    }
    for(auto row : col[t]) 
        if(dfs(depth - 1,state | row))
            return true;
    return false;
}

int main() {
    scanf("%d", &t);
    for(int i = 0; i < 7; ++ i) log2[1 << i] = i;
    while(t--) {
        for(int i = 0; i < 7; ++ i)
            col[i].clear();
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i) {
            scanf("%d", &a[i]);
            a[i] = (1 << 7) - 1 - a[i];
            for(int j = 0; j < 7; ++ j)
                if(a[i] >> j & 1) col[j].push_back(a[i]);
        }
        for(int i = 0; i < 7; ++ i) {
            sort(col[i].begin(),col[i].end());
            col[i].erase(unique(col[i].begin(),col[i].end()),col[i].end());
        }
        int depth = 0;
        while(depth <= n && !dfs(depth,0)) ++depth;
        int ans = n - depth;
        if(depth > n) ans = -1;
        printf("%d\n",ans);
    }
    return 0;
}