2020-2021:teams:no_morning_training:fayuanyu:cf_r639d1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:fayuanyu:cf_r639d1 [2020/05/15 12:53] 发源于 |
2020-2021:teams:no_morning_training:fayuanyu:cf_r639d1 [2020/05/17 17:34] (当前版本) 发源于 [E] |
||
|---|---|---|---|
| 行 31: | 行 31: | ||
| 据说可以WQS，没想清楚怎么做 \\ | 据说可以WQS，没想清楚怎么做 \\ | ||
| 还有离谱一点的，对整个式子做拉格朗日乘子 \\ | 还有离谱一点的，对整个式子做拉格朗日乘子 \\ | ||
| - | 解出来 $$\lambda=3 \frac 1 {{\Sigma \frac 1 {\sqrt a_i}}^2}$$ | + | 解出来 $$\lambda=3 \frac k {{\Sigma \frac 1 {\sqrt a_i}}^2}$$ |
| $$b_i=\sqrt{\frac \lambda {3 a_i}}$$ \\ | $$b_i=\sqrt{\frac \lambda {3 a_i}}$$ \\ | ||
| 然后对所有 $b_i$ 向下取整，计算 $k-\Sigma b_i$ ，用上面的贪心填满这个差值 \\ | 然后对所有 $b_i$ 向下取整，计算 $k-\Sigma b_i$ ，用上面的贪心填满这个差值 \\ | ||
| 行 38: | 行 38: | ||
| =====E===== | =====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===== | =====F===== | ||
| 题意： | 题意： | ||
| 解： | 解： | ||
2020-2021/teams/no_morning_training/fayuanyu/cf_r639d1.1589518415.txt.gz · 最后更改: 2020/05/15 12:53 由 发源于
