Codeforces Round #170官方题解概述

277C - Game
假设我们决定在某一行上进行操作,而这一行上有k个未被划去的(单位长度)线段,那么我们的操作可以把未被划去的线段条数变成0到k-1之间的任何数.
还记得那个经典的Nim游戏么?
(n堆石子,每次操作从要从某堆里取任意数量的石子,不能不取,无法操作者负.)
是的,他们是等价的.
这里不加证明的给出结论,当且仅当n堆各自的石子数的xor和不为0,先手有必胜策略.
所以先手每一步都要试图通过操作把这个xor和变成0.
设第i堆石子的数量为a[i],目前所有石子数的xor和是u.
如果我们决定在第i堆拿一些石子,则剩下的石子个数一定要是u xor a[i];于是,当且仅当u xora[i] < a[i], 在第i堆拿石子是可行的.

277D - Google Code Jam
如果只是要最大化期望得分的话,这是一个普通的分组背包问题,所以要重点解决的是罚时,也即在最大化期望得分的同时,选择适当的方案,调整做题的顺序来得到更低的期望罚时.
由于小数据(包括probFail=0的大数据)一定会过,所以只要他们在方案中,将他们放在前面肯定不会错,所以需要我们好好研究顺序的是0<probFail<1的大数据.
考虑两个题目i和j的大数据,i在j前比j在i前更优,当且仅当f(i)<f(j),这里
f(i)=timeLarge[i]*probFail[i]/(1-probFail[i])
于是可以把所有的题目按照这个来排序.
然后dp,令z[i][j]为"在前i个题目上耗费了j分钟"的最大期望得分,同时记录最小期望罚时.
细节略去,参见官方题解的式子.