Codeforces Round 860 (Div. 2)

C

• 对一个物品来说，可能的价格是 $b[i] \times d[i]$，其中 $b[i] \mid a[i]$

• 考虑一串能以同一个价格表示的性质，发现价格应该是所有物品 $b[i]$ 的最小公倍数的倍数，还需满足能整除任意 $a[i] \times b[i]$，转化一下即是需满足能整除所有物品 $a[i] \times b[i]$ 的最大公因数

  即能整除任意，即是能整除最大公因数，是所有倍数，则是最小公倍数的倍数

• 第一想法是 DP，维护一个指针表示最前面一个能与当前物品形成一个价格的序列，从前一个位置转移即可，因为如果往后移，必然不会更优

  但如果能想到这个转移，就应更能想到这题的贪心性质，直接从前往后算即可（如果结尾是在转折点之前，则必然不会更优）

D

• 区间和联想到前缀和

• 翻译过来即是寻找一种排列使得最大区间和最小

  但是如果单纯这样，就没有利用好题目给的另外两个条件，一个是和为 0，另一个是是小于最大值减去最小值

• 再联系第一个 tip，我们只要使前缀和最大不超过最大值，最小不小于最小值（其中一个不能取等于）

• 所以想到一种构造方法，前缀和小于等于 0 时，就加入正数，大于 0 时，就加入负数

  考虑到和为 0，总是能找到这样一个数

• 但是上面解法没有考虑 0，若是全为 0，则不存在；若是存在部分 0，则将 0 提前，则对上述解法没有影响

E

• 很容易想到从前往后考虑，且答案小于等于 2

• 考虑答案为 0 的情况，即后面能正确划分，而这个状态很容易能 DP 出来

• 考虑答案为 1 的情况，发现要么是改变当前的数，这就需要满足下一位及以后能正确划分，能由上一种情况正确 DP 出来；要么是改变后面的数，这也是本题的难点

• 改变后面的数，即是需要后面改变一位数，使之能成为 a[i] 个。发现答案具有单调性质（这里的单调性质是指如果满足一个较大的答案，那么较小的答案也一定满足）

  这种性质还挺常见，下次注意

• 所以由上一条就变成了维护一个改变一位数最大能有多少个，对于 f[i]，如果要是改变当前数，则为 max(step[i + 1...n - 1])，如果不是改变当前数，则是 f[i + step[i] + 1]

F

• Erdos Ginzburg Ziv 定理：给定 $n \in Z^*$，则在任意 $2 \times n - 1$ 个数中必然存在 n 个数，其和为 $n$ 的倍数
• 有了上面的定理，就可以先处理小的数，这样总是有解的，而对于最后一个数选择一个数也是总是有解的
• 剩下就是输出方案的背包 DP，注意如果当前物品被用了，也要转移，不能直接 continue
• 输出方案不需要记录路径，可以倒推！！第一个不满足当前条件的即代表是被选择的物品！！
• 注意减的模数 (a - b % MOD + MOD) % MOD
• 学习 jiangly 大佬对 vector 的灵活应用以及下标从 0 开始的 DP https://codeforces.com/contest/1798/submission/199278827
• iota(a.begin(), a.end(), 0) accumalate(a.begin(), a.end(), 0)