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