Codeforces Round #616 (Div. 2)

A. Even But Not Even
题意：给你一个长度为n的数字串，问能否删除数字串中某些数字，使得数字串表示的数是奇数且该数字串的每一位加的总和是偶数
思路:只需check一下n位的数字串中，是否有两个奇数
AC代码

B. Array Sharpening
题意：给你n个非负整数，对于每一次操作，可以选择一个数 $a_{i} （ a_{i} > 0 ）$ ，令其减少1。问是否可以出现 $1 \leq k \leq n, a 1 < a 2 < \dots < a k, a k > a_{k + 1} > \dots > a n$
思路：抓住特征：峰顶是关键元素、切入点
通过例子，分析求解步骤

6
100 11 15 9 7 8
以100为峰顶
峰顶左边：空
峰顶右边：11、15、9、7、8贪心改变即为11、10、9、7、6
以11为峰顶
峰顶左边：100->10
峰顶右边：15、9、7、8 -------10、9、7、6

考虑一个问题，枚举n个峰顶，暴力check可能复杂度爆炸。我们就需要考虑一个问题，是否可以通过峰顶左右边的一个代表元就可以判断该峰顶是否符合

l[i]表示以i为峰顶的左峰顶最小值
r[i]表示以i为峰顶的右峰顶最小值
如果l[i] >= 0 && r[i]>=0那么以i为峰顶可行
否则，不行

$l [i] = m i n (l [i - 1], a [i] - (i - 1)), r [i] = m i n (r [i + 1], a [i] - (n - i));$

解释
比如l[i]已经确定，且保证通过题目操作一定可以达到
$a_{1}, a_{2}, a_{3}, a_{4}, . . ., a_{i}, a_{i + 1}$
$l [i] = a_{1} < a_{2} < a_{3} < a_{4} < . . . < a_{i}$
枚举第(i+1)个为峰顶时
如果 $a_{i} < a_{i + 1}$ ,最优策略是直接把 $a_{i + 1}$ 追加在后面
如果 $a_{i} > = a_{i + 1}$ ,num = $a_{i}$ - ( $a_{i + 1} - 1)$ 最优策略是令 $a_{i}$ = $a_{i + 1}$ - 1，然后依次递减，只需要检查更新后的 $a_{1}$ 与l[i]大小。由于l[i]是最优情况，即最大值。所以l[i + 1] = min(l[i], $a_{1}$ (更新后的));

AC代码

C. Mind Control
题意：n个人，A处于第m个位置（第1个…第n个位置），容许操作k次。一个长度为n的数组，从第一个人开始，每个人要么从数组的头，要么从数组的尾，拿走元素，数组长度减1。每个人随机选择，问不管其他人怎么选，获得的最大值是多少？（容许操作是，A可以命令一个人选择数组头或者尾）
思路：考虑A可以获得的所有答案区间

6 4 2
2 9 2 3 8 5
到A选择是，剩下的数
(1)2 9 2 ----opt = 2
(2)9 2 3 ----opt = 9
(3)2 3 8 ----opt = 8
(4)3 8 5 ----opt = 5
如果k >= m - 1 那么答案按照贪心考虑，一定是9
否则就需要分析k不够的情况
k = m - 2时，即有一个人不被A控制，那我们假设就是第3个人
2 9 2
前3个人拿走的是5 8 3，第三个人不确定，那么就有两种拿走方式
5 8 3 / 5 8 2 也即是min((1), (2))标号指的是上面
9 2 3
前3个人拿走的是5 8 2 或 5 2 8，第三个人不确定，那么就有两种拿走方式
5 8 2 / 5 8 3 或 5 2 8 / 5 2 9 也即min( (2) , (1) ) 或 min( (2) , (3) )标号指的是上面

规律
设A选择后，剩下的数的集合记为B
len = ((m - 1) - k) < 0 ? 0 : ((m - 1) - k);也就是上面例子有多少人不受A控制
在集合B中，以长度（len + 1）为单位枚举，取此区间的最小值。对于所有区间求最大值。（多画几个就可以发现这个规律）

具体实现可参考下面代码
AC代码