cf刷题笔记: 1738C. Even Number Addicts

题目地址:

https://codeforces.com/problemset/problem/1738/C

题目的内容如下:

Alice and Bob are playing a game on a sequence a1,a2,…,ana1,a2,…,an of length nn. They move in turns and Alice moves first.

In the turn of each player, he or she should select an integer and remove it from the sequence. The game ends when there is no integer left in the sequence.

Alice wins if the sum of her selected integers is even; otherwise, Bob wins.

Your task is to determine who will win the game, if both players play optimally.

大概意思是给定一个序列, Alice和Bob轮流从中取数直到取完所有数结束, 如果Alice取的数之和为偶数则胜出，否则Bob胜出，其中Alice先取。

思路

一开始以为是博弈论(直接放弃), 看了题解后才发现是个动态规划问题。动态规划的思路是先将一个问题转化为子问题， 当然这个问题我们无需构造子问题最优解，我们只需要找出各个子问题间的递推关系即可。

首先我们要知道奇数和偶数的一些性质(将偶数看作为2n, 奇数看作为2n+1很好证明):

奇数 + 奇数 = 偶数 (偶数个奇数相加为偶数)

偶数 + 偶数 = 偶数 (无论有多少个偶数相加结果仍为偶数)

因此我们先来考虑一些特殊情况: 

证明: 当序列全是偶数时, 那么 Alice 必胜。

无论序列的长度是奇数还是偶数, Alice最后取得的数的和一定为偶数, 因此Bob必输。

证明: 当序列全是奇数时, 如果 Alice 最后能取出偶数个奇数, 那么 Alice 必胜, 否则 Bob 胜出。

根据上述给出的奇数偶数的性质很任意证明这个问题，由于 Alice 先取数, 因此 Alice 最后能否取出偶数个奇数是由序列的长度决定的。该问题的解是由奇数和偶数的个数决定的，我们无无需知道具体的数字，我们只需要知道奇数偶数的个数即可。 特例想好了， 那么我们就开始定义dp数组了:

注意dp数组的含义, 这是一个bool类型的数组,  而dpEven[i][j] 就代表有 i 个奇数和 j 个偶数情况下先手能否通过最优策略得到偶数和, dp[i][j] 代表有 i 个奇数和 j 个偶数情况下先手能否通过最优策略得到奇数和。

由于数据量较小，我们干脆用"打表"的方式实现dp 的 base case.

接下来我们来找递推关系, 尝试把所有个数的奇数和偶数情况下都遍历出来。

如何进行递推呢, 假设当前为第 n 轮, 我们要分析 Alice 的胜负态, 我们要把问题转化为第 n - 1 轮 Alice 和 Bob 的胜负态。

我们先来考虑 第 n 轮 Alice 赢的情况， 如果奇数的个数是偶数个,  在当前无论 Alice 拿奇数或偶数, 在第 n - 1 轮 Bob 想赢必须要先拿到奇数和胜出。

如果奇数的个数为奇数个, 那么序列总和为奇数，第一轮 Alice 先拿一定能拿到偶数个数，那么 Bob就要逼迫 Alice 拿到奇数和了(想一想例子 [1, 4, 6]，第二种证明方法: 如果 Bob先拿到奇数和， 那么最后 Alice 一定会拿到偶数和，所以想赢只有换一种策略: 拿偶数和)。 在当前无论 Alice 拿奇数或偶数, 在第 n - 1 轮 Bob 想赢就要逼迫 Alice 拿到奇数和, 所以在第 n - 1 轮必须要拿到偶数和胜出。

终于解决了，但还是有一个问题说是否会出现平局的情况呢? 也就是Alice用最优策略取得的数的和永远为偶数, Bob用最优策略取得的数的和永远为奇数? 实际上是有的, 比如说[0, 1]就是平局的例子, 只是本题降低了难度, 结果输出 Bob 而已。