考前思考

junee · 2024-11-29 22:46:22 · 个人记录

一些 trick：

考虑将原问题转化为图论求解。
考虑按大小顺序添加元素或者节点消除某些题目限制。
dp 可能是一种暴力，不一定 dp 就是正解。
考虑存在性问题时可以用 bitset 处理。
看不出来规律可以先写点暴力例如爆搜看看答案。
没有直接解体想法先手玩样例得出，研究题目性质部分分。
没有想法时可以思考答案的单调性，从这入手。
乘法太大不好维护要求实际值比大小，考虑转为对数做会好很多。
正难则反，反向思考问题，不会做合法方案，试试不合法方案好求吗。
时间回溯，删除不好维护，可以考虑先做出最后的情况，维护添加过程。
最大值，网格图，匹配，只能走一次类似的关键词可以考虑用网络流做。
log 做法想不到，可以试试根号分治和分块等根号复杂度的做法。
正常数列不好做，可以转化为 01 序列，-1 0 1 序列等，可以通过二分或者扫描线来实现。
不会做题可以打个表。
没有想法想想背包？
不会算期望概率，可以暴力算出合法方案除以总方案数。
题中出现时间限制，一些限制持续一段时间，可以通过扫描线来处理，在 l 处+1，r+1 处 -1。
发现可取的方案太多不好计算最值，思考最值的产生是什么，去除掉无关方案，减少数量。
看不懂原题别死看，写一个简化题意，翻译成人话。
题目数据范围很小说不定爆搜就是正解。
不会做时先想二分！再 dp！最后贪心！
不会做题，搓点数据，研究答案规律说不定就是对的。
树上问题不会做，转化为数列问题，dfs 序有很好的性质。
有时候问最值可以先二分，然后转化为可不可以的问题。
直接算贡献不会算，不妨计算这个位置的贡献会在什么情况出现，直接计算每个位置的贡献乘以它的出现次数。
想想二分+dp check。
如果每次暴力枚举复杂度是 n^2 的，可以通过两个指针一起维护，每次处理到一个位置把前面所有限制一起处理了，这样复杂度就是 n+m 的了。
算总方案不会算可以用总方案数减去不合法方案数。
想想折半搜索。
中位数等一些东西，可以选择枚举中心的是什么然后分左右两端处理。
依赖的背包可以转化为树形背包。
01 分数规划一般都是二分后改变每个值的范围做贪心或者 dp。

一些注意事项：

注意做运算时，先改变符号类型。
注意检查循环范围，以防越界。
注意二分区间范围，不要开小。
注意题目数据范围和实现，当数据较大时，考虑减小循环次数，减小常熟。
注意题目精度问题，如果直接维护浮点数不好维护，不如维护整形最后在变成小数。
注意数组大小，尤其在一些网络流的题目，拆点和算边尤其重要。
注意符号优先级，位运算符号最好都打括号。
注意数据范围要不要开 longlong。
不要死磕一道题注意时间分配，一题不能超过 2h。
树形背包复杂度为 O(n^2)，要先合并子树信息再合并子树大小。