D

给定n个序列
每个序列由数字 1-c 组成
每次操作将所有序列的所有数字替换为下一个数组 1->2 ... c->1

求任意一个操作次数x(0 <= x <= c-1)使得序列按字典序递增排列
不存在输出-1

序列的长度和不超过 1e6

贪心 暴力

对于相邻的两个序列我们可以求出一个有效的操作区间
然后用数组标记区间 [L,R],cnt[L]++ cnt[R+1]--
求序列的前缀和,每个位置的值k表示其被k个区间覆盖
输出一个 k = n-1 的位置即为答案

E

给n个数,每次取一段长度大于1的前缀和为得分
然后将其合并为一个数,放在第一个位置

二者轮流操作,问最优策略下先手得分-后手得分的值

dp 博弈

先处理成前缀和s
$d[i]$ 表示从第i个位置向后取时的最优得分
对于先后手都是希望 自己得分 - 对手得分 尽量高

$d[i] = max(s[j] - d[j]) \;\; (j > i)$

很明显下一个位置是对手会取的位置,所以当前位置最优得分即取一个最大值

复杂度$O(n)$