Part2
No.8 糖果传递
是一道很老的题目了，但是一直不太理解结论的正确性。
这位大佬的讲解很到位，记录一下。
最优情况下，一定存在一种方案，使得每个人只会往一个方向传递（转一圈又回来了）。
不妨设向左净支出为xi。
ave=a1+x2−x1
ave=a2+x3−x2
……
ave=an+x1−xn
保留x1，其他全部消去，可得x2=x1+ave−a1,x3=x2+ave−a2=2ave+x1−a1−a2
继续x4=x3+ave−a3=3ave+x1−a1−a2−a3
规律逐渐浮出水面，xk=(k−1)ave+x1−i=1∑k−1ai
接下来的问题就是一条线上找费马点，显然是中位数最优，代码也很好写，注意环状处理。
No.9 P3572
这个题是单调队列变种，二维关键字版本。
考虑到Fi若不同一定取较小的，若相同则关注ai大小，尽量取ai大的一定不劣。
这样魔改一下单调队列即可，very easy
No.10 绝世好题P1973
这个题题解写得太清楚了，其余除了状态设计都是平凡，关键在于转移优化。
f(x,y)在x递增时y的最优决策点单调不增，这很好证，但很难想，所以不枚举y而是双指针扫出最优决策点，O(n4)→O(n3)，太绝了！
No.11 [OJ4900]
这个题一眼想到二分答案，然而不会写Check函数。
一直在考虑每次取度数最大的点，然后就卡住了，直到看了yxy大神的做法才豁然开朗，可以每次暴力松弛，显然最多松弛n次，然后每次是n2暴力枚举，总复杂度就是O(n3log2n)。
然而直接这样写会TLE成60pts，被卡常了，考虑到如果一次松弛没有效果，那么再松弛就没有任何意义了，不如直接结束。
这个优化力度相当大，直接飞起。
No.12 [OJ4899]
这个题比上一个题要难不少，考察了反推的思维能力。
首先这个题直接做没法做，考虑反过来，已知ai求pi，那就是一个经典的Trie上贪心的过程。
那么我们反着做，如果对某一位（Trie上一个节点）进行考虑，选0/1会导致两种情况的出现，如果这两部分的pi出现了交叉，那么最优决策出现重复，那么这个点一定只有一个子树，否则不能确定往左还是往右，ans变为2倍。
判断无解：如果只有一个子树但是前后两部分，两两对应决策有差异，还是无法满足
ps吐槽:题解写的什么√8
No.13 [OJ3220]
这个题考察了容斥思想，由于满足任意两个二维偏序就能满足第三个，所以画出维恩图，三个圆圈只有一个交集部分。
设二维偏序分别为x,y,z,那么ans = \frac{x + y + z - \binom{n}{2}}{2}
No.14 [OJ3753]
首先写出朴素的DP方程式，发现相邻两项差最多为1，用平衡树维护差分序列，然后就非常shaber.
