该题解题过程非常优美,通过位操作来维护一个可选字符集合.并且完成求并集和交集.
详见代码:
#include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> using namespace std; /* 花了大半个小时看懂了这题题意:给定N个字符串,N为2的幂,每个字符串长度为L,这N个字符串 是一棵完全二叉树的叶子节点,现在问树的内部在同样要填入长度为L的字符串的情况下,最少 的花费是多少,根节点是什么. 花费是这样计算的:一条边两端的不同字符串在L个位置上的 不同位置的数目. 如果已知某叶子节点为 AGA,那么我们考虑其双亲节点为AGG的话,那么这个 花费为1,当然我们还要考虑AGG和另外一个孩子的差值以及和其双亲的差值 解法: 这题由于空间上的原因,我们最好对每一位进行一个单独的处理,而不是用多维的数组来表示 状态. 那么对于每一位上面的字符,我们需要统计两个叶子节点推到双亲节点的状态,显然我 们无法一次得到一个最优的双亲状态,而只能够去生成双亲的各个状态. 即双亲在子孩子不同 的情况下可以选择哪些字符来填充该位 例如: 左孩子: AAG 右孩子: ATA 那么其双亲节点的首位只有一个选择,就是A,这个是可以用贪心证明的. 第二位则有两种选择(A, T), 我们需要把这两种选择保存下来来证明来和未来的 兄弟一起再一起推上去 同理第三位也有两种选择,我们同样要保留(G, A) 由于只有大写字母,我们完全可以状态压缩进行保留处理 总之,此题的解法可以说是相当的精妙 */ int N, L, T[2050]; char code[2050][1050]; int main() { int ret, lim; while (scanf("%d %d", &N, &L), N|L) { ret = 0; // 用来记录花费 lim = N << 1; for (int i = N; i < lim; i++) { scanf("%s", code[i]); } for (int p = 0; p < L; ++p) { for (int i = N; i < lim; ++i) { T[i] = 1 << (code[i][p]-'A'); // 这里对每个字符的这一位进行一次二进制压缩 } for (int i = N-1; i > 0; --i) { int lch = i << 1, rch = i << 1 | 1; T[i] = T[lch] & T[rch]; // 先对两个字符集做一个交集 if (T[i] == 0) { // 说明没有相同的可选集合,通过一次花费换取更大的集合 T[i] = T[lch] | T[rch]; ++ret; } } for (int i = 0; i < 26; ++i) { if (T[1] & (1 << i)) { putchar('A' + i); break; } } } printf(" %d\n", ret); } return 0; }