2020-2021:teams:hotpot:2020nowcoder2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder2 [2020/07/16 14:11] misakatao |
2020-2021:teams:hotpot:2020nowcoder2 [2020/07/17 17:11] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 35: | 行 35: | ||
| ===题解=== | ===题解=== | ||
| - | ====C - ==== | + | ====C - Cover the Tree==== |
| - | ===solved by === | + | ===solved by -,upsolved by lxh=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给你一棵树，用最少的点到点的路径覆盖整棵树上的所有边（可以重复覆盖） | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 点数 $n \le 100000$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 我们采取一种方案，即把 $cnt$ 个叶子结点按 $dfn$ 序从小到大排，令第 $i$ 个与 $cnt/2+i$ 个连边，奇数个时，在后面加上一个虚拟结点，并将没有连到点的第 $cnt/2$ 个点与根相连。 | ||
| + | |||
| + | 考虑这种方式的正确性，对于任意一颗子树的根向整个树连的一条边，考虑子树内部 $dfn$ 序是一个区间，则这种方式连边必然会与区间边界有交叉即覆盖了之前所描述的那条边。由这条边的任意性可知，方案正确。但是注意，应保证根的度数不为1。 | ||
| ====D - Duration==== | ====D - Duration==== | ||
| 行 60: | 行 68: | ||
| 直接算出秒数然后求出差的绝对值即可 | 直接算出秒数然后求出差的绝对值即可 | ||
| - | |||
| - | ====E - ==== | ||
| - | |||
| - | ===solved by === | ||
| - | |||
| - | ===题意=== | ||
| - | |||
| - | ===数据范围=== | ||
| - | |||
| - | ===题解=== | ||
| ====F - Fake Maxpooling==== | ====F - Fake Maxpooling==== | ||
| 行 97: | 行 95: | ||
| ===题解=== | ===题解=== | ||
| - | ====H - ==== | + | ====H - Happy Triangle==== |
| - | ===solved by === | + | ===solved by -,upsolved by lxh=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 按顺序在集合中加入或是删除一些边，在其中询问长为 $x$ 的边能否和还在集合中的边构成三角形。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 操作个数 $q \le 200000$，边长 $1 \le x \le 1e9$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 根据三角形的性质我们可以发现，对于一条在集合的边来说，最容易满足的一定是和前驱、后继组成的三角形，且第三条边满足的范围一定为 $ (t2-t1,t2+t1) $。根据这个性质，我们用平衡树维护前驱后继，并在插入时在线段树区间中进行加减，查询时判断是否有区间覆盖查询点即可。由于边长的范围较大，我们需要将用到的值进行离散化处理。$ps:$ 注意这样处理之后，线段树使用的空间是16倍点数。 | ||
| ====I - Interval==== | ====I - Interval==== | ||
| 行 113: | 行 117: | ||
| ===题意=== | ===题意=== | ||
| - | 有一个区间$[1,n]$，现在可以进行操作把区间$[l,r]$变成$[l-1,r],[l,r-1],[l+1,r]$或$[l,r+1]$，但是一旦区间变成$[l,l]$就不能再变，现在有$m$个选择，你可以花费$c$把某一个区间$[l,r]$向$[l-1,r]$或$[l,r-1]$的操作禁止，问能不能完全避免把区间变成$[l,l]$，如果能，最小化费是多少 | + | 有一个区间$[1,n]$，现在可以进行操作把区间$[l,r]$变成$[l-1,r],[l,r-1],[l+1,r]$或$[l,r+1]$，但是一旦区间变成$[l,l]$就不能再变，现在有$m$个选择，你可以花费$c$把某一个区间$[l,r]$向$[l-1,r]$或$[l,r-1]$的操作禁止，问能不能完全避免把区间变成$[l,l]$，如果能，最小花费是多少 |
| ===数据范围=== | ===数据范围=== | ||
| 行 132: | 行 136: | ||
| ===思路=== | ===思路=== | ||
| - | |||
| - | ====K - ==== | ||
| - | |||
| - | ===solved by === | ||
| - | |||
| - | ===题意=== | ||
| - | |||
| - | ===数据范围=== | ||
| - | |||
| - | ===题解=== | ||
| =====Replay===== | =====Replay===== | ||
| - | 第一小时： | + | 第一小时：tyx发现D是签到题随即A了D题，然后和lxh开始想C，gyp开始想K，但是两道题写的代码均没有通过 |
| - | 第二小时： | + | 第二小时：lxh在写C，gyp发现K题一直没有人过于是转而想B并通过，tyx开始想F发现比较简单但是超时 |
| - | 第三小时： | + | 第三小时：tyx将F中的队列修改成手动实现后MLE，随后gyp发现求gcd需要更快的方法，运用该方法并修改后F题通过，gyp开始想J |
| - | 第四小时： | + | 第四小时：tyx开始想I，gyp的J题一直超时，lxh修改了几次C但是依然没有通过，gyp发现代码中有一个循环里用了两次变量i，修改后通过 |
| - | 第五小时： | + | 第五小时：tyx想出了I题的正确做法但是没能建出对偶图，交了一个网络流但是WA，gyp重新思考K没有通过，lxh依然没能把C改对 |
| =====总结===== | =====总结===== | ||
| - | * | + | * 要注意循环中的变量问题 |
| + | * gcd除了可以用log的时间单独求以外还可以用$O(n^2)$的时间预处理1到$n$之间两两之间的gcd | ||
2020-2021/teams/hotpot/2020nowcoder2.1594879916.txt.gz · 最后更改: 2020/07/16 14:11 由 misakatao
