假如 CSP 寄了,这就是死亡回放
没有简单题,不要总是想很快签。
即使是黄也需要想一会,想不出来别慌,再不过先把暴力打出来。
注意打特殊性质的分,复杂度不对也应该接着想,\(\mathbb{T}\) 总比爆零好。
容易忘的
状压
(数据范围较小时,也可以打部分分。)
连通问题可以压与上一位是否连接。
差分
区间(树上问题)区间修改单点查询可以直接用差分,也可以和扫描线结合。
根号
发现不能 log,开始尝试根号,根号重构跑暴力。
相乘如果有上界,那么就能变成根号做。
Trie
即可以处理字符串(可以维护很多信息,如前缀串出现次数),
一般也会和差分结合维护区间异或最大值。
如果需要分治就 trie 合并。
DP
要想到多开几维,然后用一些压维小技巧,如前缀和减去部分和。
图上 dp 转化生成树,断环,处理基环树或仙人掌。
敢于打复杂度高的 dp。别怕麻烦。
线段树
除了一些高级线段树和最简单的维护和,还有区间满足结合律的信息都可以维护。
要看出来线段树维护信息裸题。
势能线段树
发现有一些操作不可重复(比如死),那么一共只有 \(m\) 次操作。暴力维护。
距离
切比雪夫转曼哈顿
处理 max 转 |x|。
所以真的会考吗?oi-wiki
同余
不仅在数学里出现,还可以处理周期问题。
标签:总结,暴力,线段,根号,区间,维护,dp From: https://www.cnblogs.com/ppllxx-9G/p/18490294