https://codeforces.com/gym/102129/problem/E 题目大意：初始有 n n n堆石子，每堆石子有 a i a_{i} ai个( a i > = 2 a_{i}>=2 ai>=2)，两个人轮流进行操作，一个人每次可以选取一堆石子将其分成两堆石子，并把其中一堆石子染成黑色、另一堆石子染成白色，这两堆石子的个数没有限制，但不能为 0 0 0(也即只有 1 1 1个石子的堆是不能被划分的)。当所有堆都只含有 1 1 1个石子时，游戏结束。此时 A l i c e Alice Alice的得分为白色的石子个数， B o b Bob Bob的得分为黑色的石子个数，问两人同等聪明的情况下 A l i c e Alice Alice先手能获得的分数。 注：染过色的石子是可以再被染色的。
思路：读懂题的话感觉这道题并不是很难。关键点是只有 1 1 1个石子的堆是不能被划分的，仔细想想，每次划分只有把 a i a_{i} ai分成 a i − 1 a_{i}-1 ai−1和 1 1 1并把 1 1 1的那堆染成对自己有利的颜色才能获得贡献。更进一步，如果 a i a_{i} ai是偶数，那么 1 1 1和 a i − 1 a_{i}-1 ai−1均为奇数，你的贡献多了 1 1 1，别人下次操作 a i − 1 a_{i}-1 ai−1，他的贡献也会多 1 1 1，并得到一堆偶数个数的石子，因此偶数个石子个数是莫得贡献的。那么当 a i a_{i} ai为奇数时，分成了一堆偶数的和一堆只有 1 1 1个的，只有你的贡献会多 1 1 1。综上，两个人都会优先处理奇数个石子的堆，因此只有初始时这样的堆有奇数个， A l i c e Alice Alice的得分才会比 B o b Bob Bob的得分多 1 1 1，否则两人得分一样。
#include<bits/stdc++.h> #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int main() { int sum=0,tmp,n; scanf("%d",&n); while(n--) scanf("%d",&tmp),sum+=tmp; printf("%d\n",(sum+1)/2); return 0; }