本解题报告版权归 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 (1
end;
if n-p+1+ans