Posted on 2011-07-03 02:09
Mato_No1 阅读(499)
评论(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]（初始状态）为必胜状态则先手必胜，否则先手必败。