Useful Tricks（可能？）

zimujun · 2021-10-19 18:34:34 · 个人记录

RT

感觉现在加上的都没啥营养……欢迎大家投稿，最好附上例题，万分感谢！希望能够让它真的变得像这个标题一样……

启发式合并拯救复杂度于时间限制之内

当合并的两个数据结构的复杂度与其中的一个相关时，可以考虑启发式合并，即想办法将这个合并的复杂度加到 size 小的数据结构上，这样就一般可以把一个 n 砍成一个 \log。

E.g：600E Lomsat gelral（*2300，树上启发式合并），WC2021 T1 括号路径（并查集，哈希表或 std::map 启发式合并）

使用直接倍增或直接在数据结构上的处理向直接二分和它带来的一只 \log 说再见

有些本身就存储了多一个 \log 级别的信息的算法或数据结构，或者存储信息具有某些优秀性质的数据结构，如树状数组、树上倍增等，在求解某些具有单调性的问题上，可以考虑直接倍增或在数据结构上操作总构上的处理代替先二分再查询。从而砍掉一个二分的 \log。

E.g：联合省选 2020 A 卷 D1T1 冰火战士（线段树二分/树状数组倍增），NOIp2017 提高组 D2T3 列队，NOIp2012 提高组 D2T3 疫情控制（树上倍增）

看似暴力的算法，竟分析出带根号的复杂度

用人话说：自然根号性质 和 根号分治算法。

一个很普遍的应用是对字符串的长度有总限制时的复杂度分析：长度大于 \sqrt n 的串只有 O(\sqrt n) 个，长度不大于 \sqrt n 的串本身长度就是 O(\sqrt n) 的，总长也仍然是 \sum|S_i| = n 级别。

其余类似的情况，有些模型上需要将两种串分开处理，有些则可以直接用同一个看似暴力的算法然后用这个性质保证复杂度。

此外这个性质并非仅局限于字符串，凡是对总长有保证的都有可能能应用这个性质，算是更较为有用的 trick。

E.g 914F Substrings in a String （*3000，根据询问串是哪种选择使用后缀数据结构还是暴力匹配），677D （*2300，这个不是字符串了，两种处理方式分开以保证复杂度）

我的构造不符合条件？管他呢，反正最优的答案一定是对的。

有的时候我们能够很容易构造一组解，这个解不一定是正确的，但是如果这个构造方法能保证最优解一定正确，那么带着错解做也没关系。

这个我讲不清楚，直接看个题吧。

E.g 1622E Math test