[LC周赛赛后发布会] Weekly Contest 360

本人也是被那个3 4 5 5的分数坑了，一开始认为是手速场。前两题秒杀，第三题做了10多分钟都做不出来，觉得自己完蛋了，后来一刷新看到没几个人过，于是就开始尝试数学推理，过了。第四题一开始找环找的头昏脑胀，最后一气之下binary lifting过了。过完一看名次全球50多名惊呆了。

hxu10 发表于 2023-8-28 00:47
本人也是被那个3 4 5 5的分数坑了，一开始认为是手速场。前两题秒杀，第三题做了10多分钟都做不出来，觉得 ...

WTF!!! 第四题什么binary lifting？

irgebtdd 发表于 2023-08-28 12:59:56
WTF!!! 第四题什么binary lifting？

就是倍增法，把每一个节点1，2，4，8......步之后的数据都储存起来，然后比如计算k=27步，就是1+2+8+16，这样时间复杂度是O(nlgk)。这个在ACM竞赛中比较常见，但是放到leetcode就有点超纲了，别说medium了，放在hard都算难度偏上的。

T4 倍增吧，完全没听过 https://oi-wiki.org/basic/binary-lifting/ 。。T3 找到规律了。。。写出来就还行

残酷群是啥？