String 解题报告

本解题报告版权归 Ceeji，转载请注明出处并保留本注释。 题目描述 有N个字符串，只包含大写字母‘A’-‘Z’，要求从中找到若干个字符串，使得这些字符串包含的每个字母的个数和都为偶数，即，这些选出的字符串包含偶数个‘A’，偶数个‘B’，偶数个‘C’……且选出的字符串个数最多。 输入： 第一行，一个整数N（N<=22） 以下N行，每行一个字符串，满足每个字母在同一个字符串中不重复出现 输出： 一个整数，表示最多能选出的字符串个数 输入样例： 6 ABD EG GE ABE AC BCD 输出样例： 5 解释：选择第1，2，3，5，6个字符串即可满足题意。

思路分析 本解题报告版权归 Ceeji，转载请注明出处并保留本注释。 　　由于题目的数据范围很小（N<=22），想到用搜索解决。使用搜索的时间复杂度为2的n次方，但在搜索内部，每次都需要判断本次搜索时26个字母的个数是否均为偶数。这个浪费了26次的常数时间。26倍不是一个短时间，怎么去除26的系数呢？ 　　这时候我们想到了位运算。位运算是速度最快的运算。而 xor 运算正适合本题。因为：

　　1 xor 1 = 0; 　　0 xor 0 = 0; 　　1 xor 0 = 1; 　　0 xor 1 = 1;

　　1 xor 1 = 0;
　　0 xor 0 = 0;
　　1 xor 0 = 1;
　　0 xor 1 = 1;
　　我们让26个字母分别代表二进制上的每一位。比如A用1表示，B用2表示（二进制的10），C用4表示（100），D用8小时（1000）等。这样，每次选择一个字符串，就把状态整数 xor 这个字符串的每个字母转化成二进制的表示的和，如果结果为0，说明每一位都是 0 xor 0　或 1 xor 1。0 xor 0 说明两者均没有这一位上代表的字母，而 1 xor 1 表示均有这一位上代表的字母。这两种情况均符合题意。因此，判断26个字母是否均为偶数个就成了一个O(1)的任务(检查状态整数是否为0)了。

完整代码

//By Ceeji //Date: 2009-4-7 //HAOI test 6 - Problem 2 : string //Type: Search //State: Accepted Program str; Const inf=‘string.in’; ouf=‘string.out’; maxn=22; Var n,ans,ansmax,maxl:longint; a:array[1..maxn,1..26]of boolean; zs:array[1..26,1..2]of longint; no:array[1..maxn]of boolean; ss:array[1..maxn]of longint; zm:array[1..26]of longint; Procedure getZm; var i:longint; begin for i:=1 to 26 do zm[i]:=1«(i-1); end; Procedure init; var i,j,l,p:longint; s:string; begin assign(input,inf); reset(input); assign(output,ouf); rewrite(output); readln(n); fillchar(zs,sizeof(zs),0); fillchar(no,sizeof(no),0); getZm; for i:=1 to n do begin readln(s); p:=0; l:=length(s); for j:=1 to l do begin a[i,ord(s[j])-64]:=true; inc(p,zm[ord(s[j])-64]); if (ord(s[j])-64>maxl)and (1ansmax then ansmax:=ans; end; if n-p+1+ans