codeforces round 639 div 1
A
题意：对所有整数 i ，给定 a[] ， n， 令 i=i+a[i%n]。 问是否有两个不同整数变换后的结果相同
解：比较显然的，对 0…n 的所有i，变换后取模即可
B
题意：略
解：只要空行和空列同时出现，并且同行（列）两黑格的连线经过的格都是黑的即有答案。答案位连通块个数，证明略去
C
题意：
解：还在想
D
题意：$f(b_1,…,b_n)=\Sigma_{i=1}^n{b_i(a_i-b_i^2)}$ ，且$\Sigma b_i=k$ ，最大化f
解：
$\frac {\partial^2 f} {\partial b_i^2} < 0$
所以 $\frac {\partial f} {\partial b_i}=a_i-3b_i^2$ 递减
可以贪心，每次令最大的 $\frac {\partial f} {\partial b_i}$ 对应的 $b_i=b_i+1$
复杂度 $O(n*k)$
接下来有正常做法：
显然每次 $b_i=b_i+1$ 时所有的 $\max (\frac {\partial f} {\partial b_j})$ 是递减的
可以二分取了k次后的 $\max (\frac {\partial f} {\partial b_j})$
然后一步到位， 复杂度 $O(n*\log_2 k)$
据说可以WQS，没想清楚怎么做
还有离谱一点的，对整个式子做拉格朗日乘子
解出来 $$\lambda=3 \frac k {{\Sigma \frac 1 {\sqrt a_i}}^2}$$
$$b_i=\sqrt{\frac \lambda {3 a_i}}$$
然后对所有 $b_i$ 向下取整，计算 $k-\Sigma b_i$ ，用上面的贪心填满这个差值
显然 $k-\Sigma b_i \le n$ ，用堆维护 $\frac {\partial f} {\partial b_j}$
复杂度 $O(n \log n)$ ，没有实际去写不知道精度够不够
E
题意：一棵有根树，n辆火车。t[i] 时刻有火车i到达根，终点是点 s[i] ，火车每单位时间向终点移动1。每个点可以选择一个儿子，火车到达该点时，下一时间会去往儿子。每一单位时间最多可以改变一个点指向的儿子，然后火车移动。求最早的火车进入错误子树的时间
解：先按 t[i] 排序。由于火车不能超车，所以可以按顺序考虑火车。显然，火车 i 将路径 (1,s[i]) 上所有边都置为被指向的边。这和lct是一致的。那么，对于每辆火车，执行 access(s[i])， 每经过一条虚边 (u,v)时， u 需要改变一次方向。
实际上，u需要在 上次改变方向的时间 到 这次火车经过的时间 (t[i]+depth[i]-1) 这个时间区间内改变一次方向。用一个链表存每次改变方向的截至时间。
贪心，每个单位时间取所有点中下一个截止时间最近的，改变它的指向。使用堆维护，每次将一个时间弹出堆，将对应点的下个截止时间压入堆。如果堆顶已经来不及了，就输出答案。
复杂度由lct保证，$O(n\log n)$
F
题意：
解：
