Posted on 2011-07-03 02:09
Mato_No1 閱讀(531)
評論(0) 編輯 收藏 引用 所屬分類:
_____Topcoder_____
My first SRM……紀念一下
這次總體感覺還不是太差，也算正常發揮了——雖然最后還是米有搞定1000。250和500兩道水題的速度應該還可以（從最終名次來看）。
另外，DIV2全場只有2位神犇搞定了1000……
Orz AHdoc等神犇
————————————————————————————————————
以下為1000題解（看別的神犇的代碼搞懂的）：
設F[i][j]為第i輪開始時（還未出牌時），面對的狀態（內存）為j，是否必勝。這里設一開始的那一輪為第0輪。
逆推i。根據or運算的性質可以得到，若目前內存為j，某張已經出過的牌的值為K，則K的二進制的所有1位在j中對應的位也都是1（也就是j | K = j），這樣，掃描每張牌，若其值K | j的值不等于j，則該牌不可能出過。因此，可以在第i輪出這張牌，若至少有一個F[i + 1][K | j]為必敗狀態則F[i][j]為必勝狀態。
對于K | j的值等于j的牌，統計它們的張數，設為cnt。易知，前i輪出過的i張牌必然都是這種牌，因此若cnt>i，且F[i + 1][j]是必敗狀態，則可以在第i輪出一張這樣的牌，必勝。
如果上面沒有發現一個可以使F[i][j]為必勝狀態的，則F[i][j]為必敗狀態。
邊界：F[i][511]為必勝狀態(0<=i<=N），F[N][j]為必敗狀態（0<=j<511，因為第N輪時已經木有牌了）。
最后，若F[0][0]（初始狀態）為必勝狀態則先手必勝，否則先手必敗。