trick & tips

Day_Tao · 2024-09-06 21:41:20 · 算法·理论

遇到了就加，慢慢积累。人比较奶，所以总结的 trick 也比较奶。

比较幽默，以前写过的 trick and tips 都有些忘了，之后碰到了可能又写了一遍，所以有些重复的（

• 设计 DP 数组的时候，若一维过大而答案很小可以考虑交换这两者—— 2024.9.5 tyr 模拟赛 T2

• 对于一些区间问题，可以考虑离线下来进行扫描线处理——2024.9.5 tyr 模拟赛 T3。

• 注意一些 conner case，整场写完之后记得回去检查一下，在样例很唐的情况下可能挂的很惨（。（虽然这样出题人多半要被锕）——Fe1 模拟赛 T1。

• 注意要算取模之后的答案的题，一定要记得随时取模，算完就取，若原数比模数要大的话也要记得取模！——CF1925D

• 一些涉及到整除 + 取模的题，可以枚举除数，用除数的倍数去分块计算答案，时间复杂度 O(n\ln n)——紊莫模拟赛 T3、2024.9.12 模拟赛 T1、CF484B

• 自然根号的应用：对于 \sum\limits_{i=1}^k a_i\le n，则 a_i 的种类不会出现超过 \sqrt{n} 次。证明易证，感觉运用比较巧妙，可以把 O(n^2) 的（DP）优化成 O(n\sqrt{n}) 的。——广州实验中学模拟赛 T2、CF1481F

• 如果是对方案数的某个贡献求积，那么可以考虑将贡献转化为组合意义，将问题转化为总的方案数去做——Lanos 模拟赛 T3

• 正难则反，感觉很容易想到吧，但是很多时候真的要用到了总是想不到（。——CF1037E Trips

• 找一个全集的所有子集的所有子集，只要 O(3^n)，证明——AT_dp_u

• 大模拟可以考虑多设几个函数，思路清晰，然后也可以用分治等手段解决，这样会更加简洁清楚。——P11186 三目运算

• 如果猜到结论了就要大胆去实现，不然后悔就来不及了。时间总是够的（吗）。写完了之后应该会对这个结论有一些更深的理解，说不定就会证明了。

• 一些带修改的、只与相邻位置有关的题都可以考虑维护一个 cnt 记录当前符合/不符合条件的数量，然后再修改的时候更新。

• 当发现贪心有后效性，并且后效性还有一定单调性的时候，考虑用某种顺序去做然后使其无后效性。

• 如果局部状态确定可以确定整体状态，即固定一个点可以确定整体的状态，那么不妨用哈希去做。——CF1977D

• 学会/想到势能分析，有些问题看起来时间复杂度不对，但是稍微转化一下就对了。例如有效的开根号下取整操作上限是 \log\log n，有效的取模操作上限是 \log n ——SPOJ-GSS4 P4145 上帝造题的七分钟 2 / 花神游历各国 CF438D

• bitset 优化，在 O(n^2) 的 DP 在 10^{10} 级别的时候不要忘了可以 bitset 优化，当然前提是要对于一个类似于 bitset 功能的 DP 数组进行转移。——CF1855D

• 在考虑转移能够到达的状态，并且所有状态都要相应转移的时候，可以考虑用 bitset 去记录。——CF1855D

• 异或值最大的题可以考虑用 0-1 Trie，感觉每次遇到都不太想的到啊 /fn。

• 异或利用好相同两个数异或为 0 的性质，对于区间异或问题在交集中的异或就等价于不异或。

• 注意 1<<i 与 1ll<<i。

• 反诈能力有待提高，诈骗题司马。——CF1391D

• 对于那些所谓对原序列进行操作之后求本质不同的序列，不妨考虑最终所谓本质不同的序列的样子。

• 一定要注意数组开的范围啊啊啊。

• 部分分不要特判范围，万一数据较水能多过几个点呢。

• 考虑一些感觉不太好转移的东西可以建图去尝试跑最短路什么的，这样也是一种 DP 转移。——CF2023B

• Think twice, code once. 别把 m 写 n；别把有向边建成无向边；不要随机写码，自己写的啥心里要清楚；注意读题注意读题注意读题！！！；。/oh

• 在 DP 等不强制需要知道当前状态的东西，并且转移或者操作到的是一个区间，不妨考虑记录一下差分，然后在转移完之后/处理完之后再进行前缀和，可以有效降低时间复杂度。——P10282 [USACO24OPEN] Smaller Averages G

• DP 不全都是 O(n) 及以上的，不要存在这样的刻板印象，矩阵优化之后是 O(\log n) 的。这样想到之后可能和上面一种设的状态都不一样。——[ABC256G] Black and White Stones

• qpow 之前记得给底数取模。

• 1<< 和 1ll<< ！！！（虽然前面写过了但是再写一遍（）

• 做 DP 题的时候可以尝试多设几个状态，都尝试进行转移，这样就可以有效降低由于 DP 状态设假导致的奶氏错误。然后可以在此基础上尝试寻找更优的状态及转移。

• 一些类似于“跳一段合法的”的问题可以利用倍增。——[ABC370F] Cake Division

• 区间问题考虑给弄到二维笛卡尔坐标系中，转化为矩形取点这样的问题去扫描线做。——[ABC360F] InterSections

• 乘积过大且只要求比较数值大小时可以考虑转化为 \log 之和的比较。——CF1510D Digits

• 不带修的题可以考虑离线处理把询问挂在点上去处理。——CF1585E Frequency Queries

• 关于线段树优化 DP：考虑将转移方程实实在在地列出来，不要因为状态过大根本没列出转移方程就放弃了，这样之后可能就会发现可以用线段树去维护 DP 状态。——CF1585F Non-equal Neighbours

• 有两种或多种限制的考虑如何操作可以分开考虑几个限制，比方说这个题就是对坐标系进行一个线性变换然后分开 x 轴和 y 轴的限制的。——CF538G

• DP 时在原有状态上很难修改的时候不妨开一个辅助状态去转移当前这一步的贡献，然后再修改原有状态。——CF1498D

• 有若干限制的题考虑能否删除一些一定合法的条件然后变为一个类似的子问题，然后发现可以拓扑解决？！——CF1369E

• 虚点。

• 边权和点权同时存在的时候可以考虑将点权化为边权，可行的方法有比方说建一个虚点。——CF1245D

• 完全图上跑 MST 考虑 Prim。——CF1245D

• （前面有）部分分不要特判范围，万一数据较水能多过几个点呢。对于那些要刻意卡才能卡满的题更是如此，总不会每个点都是极限数据，这样的话可能会多很多分！！再加上 CCF 数据【】也不是一天两天了，这样得分真的可能会莫名其妙多很多！！——11.8 联考模拟赛 T4 70->20

• 对于推出来的柿子中限制比较大的部分可以考虑消除。对于这个题来讲先对两边同时对 2^k 取模，然后发现可以倍增模数去做。太牛了。人类智慧。——CF1844G

• 有用状态很少的时候考虑把无用状态压缩，只保留有用状态，这样做做就很方便了。

• 可以考虑将一个大问题转化为一个子问题和一段贡献去求解。——P7207 [COCI2019-2020#3] Sob

• 注意发现一些隐含的单调性。

• 状态比较多的时候考虑能不能找到等价的状态去替代优化。——[ABC228G] Digits on Grid

• 贡献不太好计算的时候考虑能不能提前计算贡献并与原问题等价。——P10537 [APIO2024] 九月

• 一些回文题注意回文的性质，比方说求数组划分为若干段每段和构成一个回文，这个就可以考虑一段对应的前后缀的和相同，并且也带有嵌套性。——CF2004F

• 考虑一些比较不好做的 DP 问题，即转移过程中限制会变化，不妨考虑当前贡献能转移到的不合法的点先做差分减去当前的贡献。——CF1225E

• 区间问题可以考虑用扫描线去刻画。

• DP 状态要大胆设，不要感觉很不对就不去想了，这可能会给你一些启发。

• 滚动数组记得清空。—— 11.19 qdez 模拟赛 T2 没清空以为转移假了改了一万年遗憾保单离场。

• 二分 check 贪心地时候可以考虑在每一步决策合法的情况下选择能让后面决策限制更松的情况。

• 求若干个点的 \operatorname{LCA} 就等价于求这些点中 dfn 最小的点和 dfn 最大的点的 \operatorname{LCA}。

• 跑边权只有两种的最短路考虑 \texttt{ab bfs}，做到时间复杂度 \mathcal{O}(n)。具体的，开两个队列维护上一次松弛边权的种类，每次取两个队列中队首最小的那个进行更新，这样可以保证队列中点的 dis 单调不降，原因其实可以感性理解（？。有点不好描述。

• vector 清空考虑 vector<int>().swap(vec)，直接 vec.clear() 的时间复杂度是 \mathcal{O}(n) 的。

• 注意一些奇奇怪怪的单调性，特别是像这种有双重单调性的东西，用单调栈扫描线维护。——P10656 「ROI 2017 Day 2」学习轨迹、[ARC063F] すぬけ君の塗り絵 2

• 注意一些比较神秘的“中点”性质，比方说这两个题，一个是选出的矩形一定过中线，一个是一定会选某一个序列中前缀和恰好大于总和的一半的位置的那个数。这样的性质往往是突破题目的关键。——P10656 「ROI 2017 Day 2」学习轨迹、[ARC063F] すぬけ君の塗り絵 2

• 勤查 UB。到了新的环境新的机子上一定要在编译选项中加上 -std=c++14 -O2 -Wall -Wl,--stack=1000000000，不要一上来就急着打缺省源开题！！！—— 11.23 小野花模拟赛换位置 T2 int 函数没有返回值导致 linux 环境下测评 TLE 70->0。

• 不要懒得写对拍。

• 写题的时候要想清楚再写，写的每一个字符都是要自己心里明明白白证明是正确的，不要模模糊糊感觉比较对就写上去让后样例过了，样例很弱的时候真的可能大样例都过了交上去 0pts。OI 赛制不缺这点时间。——P11323 【MX-S7-T1】「SMOI-R2」Happy Card 赛后 3 发罚时。

• 需要学会 cerr<<(&bg-&ed)*1.0/1024/1024<<endl; 测空间。——11.27 148MB/128MB 100->0

• 有些问题考虑拆成子问题去 DP 转移。

• 用宏定义 #define F(i,l,r) #define F_(i,r,l) 的时候注意逆序枚举的时候不要写成 F(i,r,l) 了！

2025 回归。

• 似马的 sqrt，别用 sqrt，哪怕保留到整数也别用！精度误差害死人！用 sqrtl。sqrt vs sqrtl，真神人了，AT 一个 C 调了几乎一整场。

• 当你调不出来的时候，请大声朗读代码。尤其是自己平时写的很多的地方，也不能掉以轻心，有的时候真的手一滑脑子一唐就写错了。

• 随机模数哈希，CF 哈希题必备：

mod=4;while(!chk_p(mod))mod=rnd()%((int)2e8)+8e8;

• 注意 INF 的值。——跳楼机，INF 应该开到 2^{63}。

• 排列问题可以考虑其逆排列去做，可能更方便，或者就是正解的一部分。

• 曼哈顿距离和切比雪夫距离的转换。曼哈顿距离 (x,y)\rightarrow 切比雪夫距离 (x-y,x+y)。证明：先转化为 (d\cos\theta,d\sin\theta)，然后将坐标系逆时针旋转 45 度，并将 d\leftarrow\sqrt{2}d，展开两角和公式，然后得证。

• 处理数组和坐标问题的时候不要以 (1,1) 为原点，以横向为 x 方向建系。请正常建系做。纯玩原。

• 注意检查数据范围，以及代码过程中存的东西会不会爆 long long，此时需要 __int128。

• 上一条也警示我们有时候拍子根本拍不到挂的数据形状的东西，需要静态查错。

• “往后跳”问题考虑倍增。

• 拆分数：\sum p_i=n,p_i\le p_{i+1}。拆分数还是比较小的，在 n=30 时只有 6000 不到。可以用于搜索的剪枝。

• 求值域为 V，长度为 n 的单调不减（增）的序列的方案数：考虑这等价于每个数字出现了几次，于是就插板，\binom{n+V-1}{V-1}=\binom{n+V-1}{n}。

• 往一个方向思考时不能浅尝辄止，不然可能对的东西没挖掘就认为时错的了。

• 在观察全局无果时，不妨去微观地看看一些比较小的关系。

• 可撤销背包：

void insert(int v){
    F_(i,n,m){
        add(f[i],f[i-v]);
    }
}

void erase(int v){
    F(i,v,m){
        add(f[i],-f[i-v]);
    }
}

单次修改时间复杂度 O(m)。

• DP 的时候注意边界，不要从不合法的地方转移。

• DP 的时候可以考虑分步转移，一步一步转移会比一下转移很多东西时间复杂度和写法上要好很多。