500pt FiveHundredEleven
給出N(N<=50)個(gè)不小于0且不大于511的整數(shù). 開始時(shí)寄存器為0, 兩人輪流選取一個(gè)數(shù), 與寄存器的值OR, 把結(jié)果覆蓋寫入寄存器. 數(shù)不能重復(fù)使用. 如果某人操作之后寄存器的值為511, 或者輪到某人時(shí)數(shù)都取完了, 那么這個(gè)人就算負(fù). 問先手是否有必勝策略.
容易想到2^9這一維, 記錄當(dāng)前每一位的0/1狀態(tài). 實(shí)際上, 不需要記錄當(dāng)前已經(jīng)選過哪些數(shù), 而只用記錄已經(jīng)選了幾個(gè)數(shù), 再由當(dāng)前的0/1態(tài), 就能推算出哪些數(shù)沒選過. 有些數(shù)x滿足x|now != x, 這些數(shù)肯定沒選過. 而對那些x|now == x的數(shù), 不必知道它具體的值, 因?yàn)樗鼘罄m(xù)操作的影響都一樣, 就是延緩一步, 把局面原封不動地丟給對方. 所以只需知道當(dāng)前還有多少個(gè)這樣的x沒被使用過, 這個(gè)值也能由上面的信息得到.
這樣就是一個(gè)類似極大極小的必勝必?cái)B(tài)記憶化搜索.
狀態(tài)為dp[1<<9][N], 轉(zhuǎn)移為N.

[狀態(tài)DP]

1000pt GameOfLifeDivOne
一個(gè)長為N(N<=50)的串(環(huán)狀, 首尾相連, 即x[N-1]與x[0]相連), 由'0', '1' 和'?'組成, 其中'?' 處可以填上'0'或'1'. 從T=0開始, 每過1單位時(shí)間, 整個(gè)串會更新一次: 某一位, 如果上一時(shí)刻, 它, 以及與它相鄰的兩位, 一共有至少2個(gè)'1', 那么這一時(shí)刻它變成'1', 否則它變成'0'. 問共有多少種填'?'的方法, 使得在經(jīng)過T(T<=1000)時(shí)間后, 還有不少于K(K<=N)個(gè)'1'. 比如'101010'->'010101'->'101010'->...; '11010'->'11101'->'11111'->...

首先容易觀察到, 兩個(gè)或兩個(gè)以上連續(xù)相同的位是永遠(yuǎn)不會變的. 只有01交替的子串才會發(fā)生變化. 所以任意一個(gè)串都可以看成是若干個(gè)形如 xpy的子串首尾連接而成, 而且兩串的首尾要相同才能連起來, 就像[xp1y][yp2x][xp3x][xp4y].... 其中pk是01交替序列, x和y都是一位, 可能是'0'或'1'. 特別的,連續(xù)3個(gè)相同字符可以看成是xx和xx粘起來(有1位重疊). 對于一個(gè)首尾字符固定不變的01交替串, 它在T時(shí)間后有多少個(gè)'1'是很容易算的. 兩頭都是0的話, 如0101010->0010100->0001000, 每時(shí)間減少一個(gè)1; 兩頭都是1的話類似, 每時(shí)間增加一個(gè)1. 一頭是0一頭1, 則0和1的個(gè)數(shù)都不變, 如010101->001011->000111. 
這樣就有個(gè)算法的雛形, 類似背包: dp[pos][bit][one]表示: 從0到pos-1的子段, 以bit結(jié)尾, 且T時(shí)間后包含one個(gè)1的方法數(shù). 如果從pos到某一位pos2-1, 能構(gòu)造出以bit起始, 以bit2結(jié)束的交替串, 那么從狀態(tài)dp[pos][bit][one]就能擴(kuò)展到dp[pos2][bit2][one+one2], 則把前者加到后者上去, 其中one2是pos到pos2-1這個(gè)子串T時(shí)間后1的個(gè)數(shù). 把原始串復(fù)制兩遍, 就能比較方便地處理環(huán). 
枚舉在原串中首次出現(xiàn)連續(xù)2個(gè)相同字符的位置startpos, 對每個(gè)startpos做一次上述DP. 把所有one>=K的方法數(shù)加起來即可. 此外要先預(yù)處理出任意edg[i][b1][j][b2], 即從i到j(luò)-1能否構(gòu)造出以b1開始, b2結(jié)尾的交替串, 如果能, T時(shí)間后有多少個(gè)'1'. 
其實(shí)整個(gè)題就是一道背包DP, 求用若干個(gè)短棍子, 拼出一個(gè)權(quán)值>=K的長棍子的方法數(shù). 只是模型隱藏得很巧妙. orz...

[背包DP]