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