Greedy Change

做题笔记：

直观思路：让最大值的零散剩余尽量多。

性质分析：求的是最小值，那么最小值前贪心都是最优构造，但是后面也有可能是，不能用二分。

容易构造，这个函数峰值很多，所以模拟退火必定超时，再考虑，发现最小反例时贪心解与最优解的非零位集合无交，不然有更小的反例，就此，我们发现枚举最优解最小和最大的非零位，那么贪心解大于等于最小非零位前一个 $c_{i-1}$，并且减去任意一个它取了的数，都会小于等于 $c_{i-1}$，枚举即可。

最优解第一位可以从 $2$（次大） 开始，最大没有反例，这只是剪枝，不影响正确性。

Emotional Fishermen

做题笔记：

计数题，转二维发现毫无思路，发现顺序任意，想到先贪心排序，

然后发现，如果有 $a_{n-1} > a_n / 2$ 的就无解，那么我们只需要用 $DP$ 就可以递推，系数是组合数。

Little Elephant and Broken Sorting

做题笔记：

设充要条件为$DP$对象，有限次，简单题。

Serious Business

做题笔记：

解决中间这一块很有难度，考虑用线段树优化。

Weighted Increasing Subsequences

计数题，算每个序列的贡献和是不好算的，可以算每个位置有贡献的次数。

进一步用容斥优化。

Cipher

有一个熟为人知地结论：对于一个序列，如果允许相邻两个数交换，我们就可以类似地，通过这种方法，让任意两个数交换。这道题也一样，可以类似的推出这样一个结论：对于一个序列，如果允许相邻两个数一个加一一个减一，我们就可以类似于传递，让任意两个数一个数加一一个数减一。

所以等于 给定总和 s，求将其分成 n 个 1~26 的整数之和的方案数。

可以 $DP$ 求解，但询问有点多，要预处理所有字母的情况。

但是 xyf007 有一个更好的做法，这道题还是一个容斥，发现没有 1~26 的限制，那么可以用隔板法，所以我们用容斥思想去计算 $n$ 个数中不满足的情况即可。