<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4072">點選打開連結uva 1326</a>
題意:給定n個由大寫字母組成的字元串,選擇盡量多的串使得每個大寫字母都能出現偶數次
分析:
1 在一個字元串中每個字元出現的次數是無關的,重要的是隻是這些次數的奇偶性。那麼我們用一個二進制來表示這個字元串,那麼題目就變成求盡量多的字元串,使得他們的異或值為0
2 題目給了18s,那麼我們可以考慮暴力法。n最大24那麼O(2^24)在18s之内是可以接受的,是以我麼利用遞歸求二進制的方法求ans
3 另外一種方法是利用中途相遇法“先計算出前n/2個字元串的所有可能的異或子集,然後在去求後n/2個字元串的所有異或子集并且在前n/2個中去比對,求ans”
代碼:
<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4072"></a>