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