Warning: session_start(): open(/tmp/sess_a6b1d3d9eeade11a125498dad7f70227, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
======codeforces round 639 div 1======
链接： [[https://codeforces.com/contest/1344]]
=====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=====
题意：
解：