题意：
有2^n个奶酪，对应二进制的数，用清理机输入一个二进制数可以清理对应的奶酪，含有*的算成0和1两个，每次只能出现一个*，现在清理机自身感染细菌，它清理的奶酪都被感染，将清理机消毒后，问最少清理几次能把所有感染的奶酪清理干净。
要点：
这题比较复杂，题意就比较难看懂，算是一个有向图的最大匹配问题，因为带*的同时可以清理两个，所以就是求最多能有几个*，最后结果：总数-最大匹配数，将所有只差一位的二进制数建图，注意这个图是有向图，因为两个只差一位的数合并成一个，建图时是遍历所有的点，一个点用完后和它连接的点会再次出现，而我们要求只匹配一次即可，所以求出的ans/2。这题还有两个要注意的地方：
1.判重，所有的输入中会出现相同的数，所以最后如果直接用这个数-ans/2会失败，所以判重去除重复数。
2.判断二进制是否只差一位，首先设一个数C，C=A^B，根据异或判断，相同的为0，不同的为1，所以如果只差一位C!=0，但这样是不够的，可能出现差两位的情况，那么就判断(C&(C-1))==0，如果只差一位，C中只有第i位一个1，那么C-1就是i-1……0都是1，其余为0，可以看出是没有相同位的，如果差两位及以上，就会出现相同位，最后合并判断这个式子即可：c && ((c&(c - 1)) == 0)，注意这里的优先级比较混乱，最好一步一个括号。这种方法只能判断差一位的情形，不能同过-3，-2判断是否差3位或两位。
| 15491157 | Accepted | 16652K | 719MS | 1649B | 2016-05-11 07:25:35 |
#include#include #include #include using namespace std;#define maxn 2050int map[maxn][maxn], used[maxn], edge[maxn], girl[maxn];int n, m;bool find(int x){ int i; for (i = 0; i < maxn; i++) { if (map[x][i] && !used[i]) { used[i] = 1; if (girl[i] == -1 || find(girl[i])) { girl[i] = x; return true; } } } return false;}int main(){ int i,j, num,temp,count; char s[15]; while (scanf("%d%d", &n, &m), n + m) { memset(map, 0, sizeof(map)); memset(girl, -1, sizeof(girl)); count = 0; while (m--) { scanf("%s", s); num = 0; temp = -1; for (i = 0; i < strlen(s); i++) { if (s[i] == '*') temp = i; else num += (s[i] - '0')*(1 << strlen(s) - i - 1); } if (temp == -1) edge[count++] = num; else { edge[count++] = num; edge[count++] = num + (1 << strlen(s) - temp - 1); } } sort(edge, edge + count); int sum = 1; for (i = 1; i < count; i++) if (edge[i] != edge[i - 1]) edge[sum++] = edge[i];//count中有可能出现重复的，所以要判重 for (i = 0; i < sum; i++) for (j = 0; j < sum; j++)//这里算出的ans是两倍 { int c1 = edge[i]; int c2 = edge[j]; int c = c1^c2; if (c && ((c&(c - 1)) == 0))//注意这里的括号不能节省，优先度比较麻烦干脆全写括号 map[c1][c2] = 1; } int ans = 0; for (i = 0; i < maxn; i++) { memset(used, 0, sizeof(used)); if (find(i)) ans++; } printf("%d\n",sum-ans/2); } return 0;}