天天看點

uva 1326 - Jurassic Remains

<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=460&amp;page=show_problem&amp;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&amp;Itemid=8&amp;category=460&amp;page=show_problem&amp;problem=4072"></a>