oi那些(小)技巧

## 面向普及+/提高+ 本题单主要由练习过程中遇到的具有技巧性的题目拼凑而成 欢迎补充点评！ P6323 逆序对如何dp转移方案数 P14362 最小生成树O(m)边优化O(n) P7868 求平均数大于k->预处理时全减去k P10102 随机向量以O(n2)->O(n)优化 P4065&P8819 哈希妙用(double exp P3587) P8321 序列 min/max 计数尝试排序后解决&序列匹配计数问题的 dp 套路&含固定辅助值的 dp 可以尝试寻找状态中变量关系来简化状态。 P4462 好像算莫队板题？不管了就当离线log优化/处理异或信息/莫队奇偶优化套路了 P10814 转化思想离线典题 P1763 神了，完美结合了数学和剪枝，迭代加深也好玩 P1367 普及组思维题，暂时没活不过这个好经典 P3870 依旧普及组，开开关经典问题 P2607 基环树处理，基环树入门，其实就是找环断边/kel P4147 单调队列优化决策板子。没什么好说但是有点思维含量在的 P2717 也是求连续段平均值套路，加一个树状数组优化技巧，俗称权值树状数组 P13673 折半搜索+随机化技巧，难死了这个 P2808 蓝色的dp，紫色的体验！见≤7识状态压缩 P6026 ~~计数毒题~~找规律好题，若式子不明显可以使用人类智慧技巧 P11870 因为奇数都在奇数位上，所以我们给每一个奇数加上 i，原问题可以转化成简单计数 P7334 区间次方信息维护技巧题 P4066 很好的诈骗题！很妙的思维转化！ P4224 技巧综合题，可以考虑在整除和值域限制上做文章 P10367 二分图经典trick P6499 ~~没想到吧博弈论也可以大剪枝~~,先将k<400思考剪枝变成k<19满足状压dp的条件，然后一个强思维的转移；做法二是剪枝随机化有点难想 P11189 树上区间调整，见到这种题是不是先想到差分？？又因操作顺序不会影响结果所以分开处理，贪心解决 P1861 丧心病狂的神仙题...因为答案仅与状态相关，所以可以计算每颗星的势能....然后就秒了！！？ P3978 考场猜结论专供题，~~注意到式子显然不是我们能力范围内的~~，所以我们需要主观理解题目，尽量往人类智慧去靠拢猜一个模棱两可的东西（卡特兰数 P10764 正难则反，对于这种明显单峰且两边不增/不降的东西拆成两个单调的贡献容斥求和 P5955 好题！思维转化：~~(常规想法)贪心/dp求极大值~~-->关注 向量和 这种东西自身性质，枚举最终答案向量方向，和方向向量同侧向量才选(duoble exp P10671) P4513 log n求区间最大连续子段，套路一下其实就是分类讨论区间对答案贡献情况，拆成维护四个值啦 P5071 质数trick:一个数最多只有一个大于$\sqrt{n}$的质因子。 但是这题小于$\sqrt{n}$的质数太多了,那就两个,有一个性质，一个数最多只有两个大于$\sqrt[3]{n}$的质因子。把小于$\sqrt[3]{n}$的质数先拿出来做前缀和,剩下的去莫队维护。 P6898 好的我们看看tag,黑题,2-SAT,~~欸不是这东西怎么放进来的~~，考虑简单贪心每次选择一个数，判断当前放 A 更优还是放 B 更优。众所周知错误的贪心加上**shuffle**就是神卡时限退一直跑就行了。~~随机化神力tql~~ P4593 trick:利用拉格朗日插值求$\sum_{i = 1}^{n} i^k$ P4834 小小的推斐波那契式子，爱来自o2优化 P8207 trick:转化思想，从u,v讨论gcd(u,v)转化成讨论gcd(u,v)枚举u,v优化建边 P4919 树状数组单调离线维护好题 P10238 trick:删边离线变加边 考虑倒着做变成加边，有经典结论：合并后新树的任意直径端点，必然是合并前某棵树中某条直径的端点。所以答案单调，上LCA求距离，并查集维护，做完了。 P14568 考虑一个排列是如何生成的，一个很经典的想法，认为一开始有一个空序列，我们依次向里面插入 1,2,3,…,n，那么会得到一个排名序列，其反排列就是我们要的排列。利用这个思想构造插入dp即可(篇幅限制详见题目) P12676 ad_hoc的trick，思考一下不难发现需要对n%2的结果分讨，看到2的分类则想到奇偶性，在数字奇偶做文章就好 P1306 见多识广题：首先我们有$gcd(feb[m],feb[n])==feb[gcd(m,n)]$，然后矩阵加速，就没了 P13525 trick:碰到区间包含类型的问题可以试图转换成树。