这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:hotpot:2020nowcoder2 [2020/07/16 17:14] lotk |
2020-2021:teams:hotpot:2020nowcoder2 [2020/07/17 17:11] (当前版本) misakatao 更新 |
||
---|---|---|---|
行 37: | 行 37: | ||
====C - Cover the Tree==== | ====C - Cover the Tree==== | ||
- | ===solved by ,upsolved by lxh=== | + | ===solved by -,upsolved by lxh=== |
===题意=== | ===题意=== | ||
行 68: | 行 68: | ||
直接算出秒数然后求出差的绝对值即可 | 直接算出秒数然后求出差的绝对值即可 | ||
- | |||
- | ====E - ==== | ||
- | |||
- | ===solved by === | ||
- | |||
- | ===题意=== | ||
- | |||
- | ===数据范围=== | ||
- | |||
- | ===题解=== | ||
====F - Fake Maxpooling==== | ====F - Fake Maxpooling==== | ||
行 105: | 行 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==== | ||
行 121: | 行 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]$,如果能,最小花费是多少 |
===数据范围=== | ===数据范围=== | ||
行 140: | 行 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 |