题目大意：看了别人的题意： 给出m串长度为n的01串，如果某个串中包含‘＊‘号的，那么这个串就可以变成两个串(因为‘＊‘既可以表示0或者1) 比如字符串*01就可以表示成001，或者101 现在的任务是消除所有的串，给出消除串的规则如下： 1一次消灭一个串。 2如果两个串的差别只有一位的话可以同时消灭这两个串。 问至少需要多少次才能消灭这些串
解题思路：先将这些串去重，化成整数，，这样就可以得到两个点集了，点集之间的关系就是一个操作能否消除掉两个串，如果可以的话，则这两个串就存在关系了
;const int N = 2100;int n, m, t_num, num[N],link[N], vis[N];vector<int> g[N];char str[15];int bitcount(int x) {return x == 0 ? 0 : bitcount(x >> 1) + (x & 1);}void init() {num[0] = -1;int cnt = 1;for(int i = 0; i < m; i++) {scanf(“%s”, str);num[cnt] = 0;for(int j = n – 1; j >= 0; j–)num[cnt] = 2 * num[cnt] + (str[j] != ‘0’);cnt++;for(int j = 0; j < n; j++)if(str[j] == ‘*’) {num[cnt] = num[cnt – 1];num[cnt] ^= (1 << j);cnt++;}}sort(num, num + cnt);t_num = 1;for(int i = 1; i < cnt; i++)if(num[i] != num[i-1])num[t_num++] = num[i];for(int i = 1; i < t_num; i++) {g[i].clear();for(int j = 1; j < i; j++)if(bitcount(num[i] ^ num[j]) <= 1) {g[i].push_back(j);g[j].push_back(i);}}memset(link, 0, sizeof(link));}bool dfs(int u) {for(int i = 0; i < g[u].size(); i++) {int v = g[u][i];if(vis[v])continue;vis[v] = 1;if(!link[v] || dfs(link[v])) {link[v] = u;return true;}}return false;}void hungary() {int ans = 0;for(int i = 1; i < t_num; i++) {memset(vis, 0, sizeof(vis));if(dfs(i))ans++;}printf(“%d\n”, t_num – ans / 2 – 1);}int main() {while(scanf(“%d%d”, &n, &m) != EOF && n + m) {init();hungary();}return 0;}
父母养我不容易，我在学校争口气。
