一些 tips

在本博客中，一般写题解的题都是我认为比较有价值的题，然而我还做过一些有一定价值，但并没有达到值得写一篇题解的程度，故将这些题目总结出的套路用一句话概括在这里：

当然如果看到我太久不更请在评论区里催我一下

计数题里碰到平方可以尝试把它们拆成每对符合要求元素各自产生贡献（upd on 2021.9.13，CF1187F）
概率题一定要注意随机变量是否独立，只有它们独立它们的贡献才能直接相乘（upd on 2021.9.13，CF1187F）
看到序列上的线性变换（指操作可以写成线性变换的形式）可以尝试用线段树维护矩阵乘法维护，如果涉及常数那么矩阵上可以额外维护一个常数维存储这些常量（upd on 2021.9.14，P7453）
看到 \(c_i\leftarrow c_{i-1}+c_{i+1}-c_i\) 这种形式的东西，应知道这东西等价于对 \(c_i-c_{i-1}\) 的置换（upd on 2021.9.15，CF1110E）
看到要求 \(x-y=v\) 的数的对数，并且值域不算太大，可以想到差卷积（upd on 2021.9.15，P3760）
对于某些数论中的题目，关于质因子的状压可以转化为原数的约数，因为每个数的质因子组成的集合本身就可以表示一个状态（不过一般状压质因子复杂度也可以被证明是调和级数或者类似的东西？）（upd on 2021.9.18，NFLSOJ 12429）
有的最优化问题有时也可以转化为计数问题，通过模上一个或几个大质数并判断余数是否为 0 来求解（upd on 2021.9.18，NFLSOJ 12429）
unordered_map 常数大约是数组的两倍，所以以后状压 dp 之类的题目能删减状态就删减状态（upd on 2021.9.19，NFLSOJ 10131）
对于质数 \(p\)，必然有 \(\forall n\ge p,n!\bmod p=0\)，利用这个性质可以使得很多 \(n\) 很大（比方说 \(10^{18}\)）的情况变成诈骗题（upd on 2021.9.19，NFLSOJ 10131）
分块打表有时是一个不错的技巧（upd on 2021.9.19，NFLSOJ 10131）
看到斜率优化的形式的式子要想起来是斜率优化啊！！！（upd on 2021.9.20，CF643C）
对于 \(\sum\limits_{i=1}^ma_i=n\) 的数列 \(a\)，其中包含的不同数的个数只有 \(\mathcal O(\sqrt{n})\) 种（upd on 2021.9.21，CF1574F，利用这个性质可以不用分治 FFT/求逆）
线段树维护信息的本质是合并两个区间的信息，因此如果发现一些信息满足可合并性（如链上的一些信息，或者一些有关树的直径/虚树的信息），可以想到线段树（upd on 2021.9.21，CF1083C）
一个数 \(\bmod\) 完一个比它小的数后大小减半，这有时是一个非常重要的性质（upd on 2021.9.21，AGC003E）
two pointers 是均摊数据结构（雾），不支持撤销（upd on 2021.9.21，NFLSOJ 12430）
矩阵乘法可以通过“先枚举 \(i,k\) 再枚举 \(j\)，并且当 \(k\bmod 16=0\) 时再取模”的套路减少取模常数（upd on 2021.9.22，NFLSOJ 10127）
对于矩阵乘法的题目，能把矩阵改成向量就改成向量，减少常数（upd on 2021.9.23，NFLSOJ 10127）
删除操作非常棘手，不妨考虑线段树分治（upd on 2021.9.24，CF678F），也可以倒立（
看到保证最短路径的前提下，求 xxx 的最值/计数的问题可以考虑建出最短路径 DAG，这样最短路径可以转化为最短路径 DAG 上的路径（upd on 2021.9.25，LOJ 2769）
区间 DP 的转移一般可以考虑“最后一次进行的操作”，然后将序列分成两个部分并计算贡献（upd on 2021.9.26，P4766）
看到“每个点的度数 \(\ge k\) 的题目”可以考虑按将所有点及其度压入一个 set 中并动态删点（upd on 2021.9.28，NFLSOJ 12448）
在构造题中看到下取整可以往抽屉原理的方向思考（upd on 2021.9.28，CF1450C2）
碰到 LIS/LDS 的题目不要只拘泥地想“\(dp_i\) 表示 \(i\) 结尾的 LIS/LDS 的最长长度”，也可以交换定义域&值域，变成“长度为 \(i\) 的 LDS/LIS 的最大/小结尾元素”（upd on 2021.9.28，NFLSOJ 12449）
树剖求 LCA 常数非常小，\(\log n\) 跑起来和 \(\mathcal O(1)\) 差不多快，不过会被满二叉树卡（upd on 2021.9.29，NFLSOJ 12456）
碰到从开头删除/结尾插入，全局插入，并且合并复杂度很高，但插入复杂度不高的题目，可以考虑双栈模拟队列（upd on 2021.9.29，NFLSOJ 12458）
使用莫队二次离线可以将一些 \(n\sqrt{n}\log n\) 将为 \(n\sqrt{n}\)。（upd on 2021.10.1，NFLSOJ 10175）
看到 DAG 的计数可以想到枚举度为 0 的点然后容斥（upd on 2021.10.4，洛谷 P6295，更多 trick 可见那题题解）
有的概率题会让你保留成小数形式 instead of 取模，这时候你就可以考虑重复某个过程直到精度符合要求 instead of 推无穷级数（upd on 2021.10.4，CF623D）
对于计数题，如果发现等价表达不太好找，可以尝试容斥（upd on 2021.10.11，NFLSOJ 12473）
对于一些带修的数据结构题，可以考虑离线扫描线并以时间为下标（upd on 2021.10.15，NFLSOJ 12461）
对于区间查询所有还活着的位置并将这些活着的位置全部删去的模型，可以考虑使用并查集维护，这样可以做到 \(\Theta O(n\alpha(n))\)（upd on 2021.11.2，NFLSOJ 12554）

巴特西

一些 tips

最新文章

热门文章