Codeforces Global Round 22 ABC 3题 个人题解

题意：
给t组数据
每组数据描述一组技能，每个技能分为0或1两种类型，有各自初始的伤害数字。
要求随意排列这组技能，第一个技能伤害不变，往后的每个技能，如果与前面一个技能的类型不相同，这个技能伤害翻倍，如果相同则不变。
求能造成的最大伤害之和。

贪心题。
最优肯定是尽可能排出010101这样的类型排列，类型0和类型1技能的数量可能是不同的，那么伤害数字大的优先被排入能被翻倍的位置。

类型0和类型1分开存入两个数组，且从小到大排序。
假如某个类型比另一个多n个数，那么这个类型的前n个数是不翻倍的，其他所有数翻倍。
对于两个类型元素个数相同，那么最小的数排在第一个，不翻倍。

题意
定义一个数组的前缀和数组与此数组的长度是相同的，对于前缀和数组的第i个元素$a_i$，$a_i$的值等于原数组从第一个元素到第i个元素的和。
在这样条件下：
给出一个不递减的数组的长度为n，和它的前缀数组末尾k个数具体的值。
问存不存在任意一个数组能满足这样的条件。

结合给出的样例分析一番。
发现可以根据前缀数组末尾k个数具体的值，求出原数组末尾k-1个数具体的值。（求出的数要满足不递减的条件，不满足就输出NO。）
注意求出的是末尾k-1个数的值，前面有n-k+1个数的值是不知道的。
正好，题目给出了前缀数组末尾k个数具体的值，这组数第一个数的实际含义就是原数组前n-k+1个数的和，并且我们已经求出原数组末尾k-1个数具体的值，也就是原数组n-k+2个数的值是知道的，那么再加上不递减的条件。
前n-k+1个数，每个数的值都不能超过原数组第n-k+2个数的值。假如，原数组前n-k+1个数的和给的过大，前n-k+1个数每个数都取最大，和仍然较小，达不到要求，就输出NO。

题意
a和b从一组数中轮流一人一次任意取出一个数，a先手，数全部取完结束游戏，总结分数。
假如a取到的数的和是奇数，b赢，假如a取到的数的和是偶数，a赢。
给出这组数，问两个人玩游戏的时候选取的都是对己方最优的策略，在这组数的条件下，谁一定可以赢？

分析样例，并推导推导。
奇数加偶数是奇数，偶数加偶数仍然是偶数。
我个人做题时的感觉，奇数比偶数要更重点考虑。

对于全奇数的数组，它的长度是n，((n+1)/2)%2，除法是整除，结果是1，b赢，是0，a赢。
再把偶数存在的情况考虑进来。
分析偶数存在一个的情况，设n为奇数的个数。
a可以选择主不主动拿不拿走偶数，如果拿，b得在这轮回合里得拿走一个奇数，整个局面等价于n-1个全奇数。
不主动，那么这里由b做出对自己有利的选择，若b主动拿走，整个局面等价于n+1个全奇数。
b也不管，这个偶数就放在这里，无视，整个局面等价于n个全奇数。

再分析多个偶数的情况。前面说到，感觉偶数比奇数不那么重要。
大于等于两个偶数的情况，每两个偶数可以相消，经过处理，归为上面无偶数、有一个偶数两个情况其中之一。
可以进行这样一个逻辑推导：先把偶数消到0个或1个，这时胜负上文已经分析出来了。
输的一方想要改变，只能尝试做额外的选择，但拿一个偶数，赢方就直接跟着拿一个偶数，一对偶数被拿走，没有影响产生，不改变这个结果。