2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2 [2020/07/31 13:44] 2sozx 创建 |
2020-2021:teams:farmer_john:2sozx:codeforces_round_660_div._2 [2020/07/31 14:05] (当前版本) 2sozx [E] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| * 题解:先 $dfs$ 一遍记录一下子树的 $p$ 和。注意到一棵子树的根节点的好情绪的人一定大于其儿子的好情绪的人的和，再 $dfs$ 一遍判断即可。注意判断 $abs(h)>p$ 的情况即可。 | * 题解:先 $dfs$ 一遍记录一下子树的 $p$ 和。注意到一棵子树的根节点的好情绪的人一定大于其儿子的好情绪的人的和，再 $dfs$ 一遍判断即可。注意判断 $abs(h)>p$ 的情况即可。 | ||
| =====D===== | =====D===== | ||
| - | * 题意: | + | * 题意:给定两个序列 $a_n,b_n(n\le2\cdot10^5)$ ，定义一种操作选择一个点 $i$ ,将 $a_i$ 加入答案中，如果 $b_i\not =-1$ 则$a_{b_i}+=a_i$ ，每个点恰好被选择一次，问最后答案最大值为多少。$b_i$ 不构成环。 |
| - | * 题解: | + | * 题解:题目显然是一个多棵树的情况。如果一个点的儿子能够通过一系列的操作使得自己的值 $>0$，那么这个儿子的操作一定在父亲的前面会更优，否则则在父亲的后面，通过 $topo$ 序输出方案即可。 |
| =====E===== | =====E===== | ||
| - | * 题意: | + | * 题意:给定 $n$ 条平行与 $x$ 轴的线段并且 $y_i>0$ ，现在选择一个向量，将这些线段沿着向量平移到 $x$ 轴，期间线段不能有相交，顶点相交除外，问最后平移到 $x$ 轴后左右端点距离最小值是多少。$(n\le2000,-10^6\le xl_i<xr_i\le10^6,1\le y_i\le10^6)$ |
| - | + | ||
| - | * 题解: | + | |
| + | * 题解:有个很显然的结论，如果要达到最小值必然会有两条线段顶点相交，因此我们可以枚举两条线段相交，记录相交时的向量，显然对于两条的线段，如果此时向量位于顶点相交的向量内部，则这两条线段最后会相交，因此我们可以通过扫描线来判断什么向量是可行的。\\ \\ 对于一个向量我们要快速判断通过这个向量移动后 $x$ 坐标的最大值和最小值是多少，考虑一个点 $x_i,y_i$ 通过向量移动会到什么位置。令向量为 $v=(a,b),b<0$ ，这个点最后会到 $(x_i-y_i*a/b,0)$ ，横坐标为关于 $x_i,y_i$ 的一次函数，将一个线段看作两个点，因此可以构造出两个凸壳，然后对于每个可行的向量在上面二分查找即可。注意答案会很大，极大值要开够。 | ||
2020-2021/teams/farmer_john/2sozx/codeforces_round_660_div._2.1596174289.txt.gz · 最后更改: 2020/07/31 13:44 由 2sozx
