这题的首先就是贪心处理,相同则取相同,不同则取并集,并集就联想到了位运算,然后精髓就在分割l个字符,一位一位考虑,位运算到heap[1](模拟二叉树).
#include<cstdio> #include<cstring> char seq[1100][1100]; int n,l; int heap[2200]; int main() { while(scanf("%d%d",&n,&l)&&(n||l)) { int cost=0; for(int i=1;i<=n;i++) scanf("%s",seq[i]); for(int k=1;k<=l;k++) { for(int i=1;i<=n;i++) heap[n+i-1]=1<<(seq[i][k-1]-'A'); for(int i=n-1;i>=1;i--) { if(heap[i]=(heap[2*i]&heap[2*i+1])); else { heap[i]=heap[2*i]|heap[2*i+1]; cost++; } } int ch=0; while(!(heap[1]&1)) { ch++; heap[1]>>=1; } printf("%c",ch+'A'); } printf(" %d\n",cost); } return 0; }