TCO2017 Final 部分题解

TCO2017 Final

RabbitAndTable

从大到小枚举桌子大小，这样所有可选的兔子就是等价的了。

记 fi f i 为已经用了 i i 只兔子的方案数，那么我们只需要枚举当前桌子大小和个数即可转移，时间复杂度O(n2logn)O(n2log⁡n)

Code

GameOfTokens

不公平博弈的模板题。

考虑Alice必胜的条件，如果我们能够计算出Alice能比Bob多走多少步，那么最后如果步数 > > 0则必胜。

考虑怎么计算， 我们现在对某一个确定方案计算步数。 倒着做，维护一个类似后缀和的东西。遇到空格就加进答案里，遇到 A A 就 1 1 并 和 0 0 取maxmax，遇到 B B 就−1−1并和 0 0 取minmin。

用DP来记录以上信息即可，时间复杂度 O(n4) O ( n 4 ) 。

Code