地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3603
题意：背景是手机游戏，给出一些字母猜单词。现在假设你猜不出，然后不停重新开始游戏，游戏就每次给你12个大写字母，由于正确字母以外的候选字母是随机给出的，所以两次游戏中发生改变的字母肯定不是答案，是可以去掉的。现在假设你试验了 N 次，给你每次得到的 12 个候选字母。要求按照字母顺序把去掉不可能的字符之后剩下的那些字符输出。
分析：一个比较简单的题目。但是题目描述中没有交代相同的字符是否可能出现多次，但是显然这是可能的。因为一个单词中可以出现重复字符，例如 see ，choose 等。所以如果你假定每个字符只有一个的话肯定 WA，所以这题有很大的 WA比例。只要你知道每个字符是可重复的，这个题目的求解就很简单了。就好比给你一串数字，输出其中最小的一个数字的问题相似，线性时间搞定。
字符候选是一个集合（由0到多个A~Z字符组成），我们假设初始集合是多个 A，多个 B，。。。多个 Z 组成，用 unsigned char flags[26] 来标记它们，flags [ i ] 表示的是字母（'A' + i ）的个数，把它初始化为一个明显很大的数字，255 就够了。然后对每一次游戏给出的 12 个候选字母，我们取它和现有的集合的交集。最后剩下的集合就是答案。
zoj3603_code
#define min(a,b) ((a)<(b)? (a):(b)) #include <stdio.h> #include <string.h> int main(int argc, char* argv[]) { char line[16]; unsigned char flags[26], tmp[26]; int T, N; int i, j, k; scanf("%ld", &T); for(i = 0; i < T; i++) { memset(flags, 0xff, sizeof(flags)); scanf("%d\n", &N); for(j = 0; j < N; j++) { gets(line); memset(tmp, 0, sizeof(tmp)); for(k = 0; k < 12; k++) { tmp[line[k] - 'A']++; } for(k = 0; k < 26; k++) { if(flags[k] > tmp[k]) flags[k] = tmp[k]; } } for(k = 0; k < 26; k++) { while(flags[k] > 0) { putchar('A' + k); --flags[k]; } } printf("\n"); } return 0; }
