暴力美学

· · 算法·理论

记录在集训期间自己认为有用的东西。

分块

莫队

珂朵莉树

反悔贪心

链表，并查集维护序列连通性

字符串hash

集合哈希（异或哈希）

三分

换根DP

单调栈

二分图最大匹配

trie 树

状压DP

根号分治

暴力要优化，枚举子区间 O(n^2/2)

优化得当，双 \log 过百万。

莫笑根号算法傻，莫队分块轻松卡。
区间问题难合并，暴力重构笑哈哈。
根号分治看似难，两个暴力拼一块。
区间覆盖难维护，珂朵莉树来救场。
组合计数难实现，暴力计数与状压。
枚举区间非n方，除二常数跑的快。
字符串题不要慌，hash二分来吊打。
后缀数组难实现，hash排序二分好。
树上并查暴力跳，树链剖分暴力切。
RMQ有st,O(1) lca 有dfn。
全源最短路一般般，Johnson替代Floyd。
bitset来优化，数据结构维护暴力查。
线性单 \log 难思考，根号两个 \log 跑得快。
搜索带上记忆化，DP 带上递归化。
直接爆搜太超霸，剪枝优化往上加。
双向广搜放上去，最优可行重叠叉。
trie 树时间很友好，三分二分顶呱呱。
换根DP化为 O(N)，单调栈维护贡献值。
拆位贡献非常好，倍增加速暴力跳。
时间回溯并查集，加上链表连通性。
区间调度用贪心，DP解决很多问题。