【置顶】套路集锦

套路集锦

傻逼错误

  1. cmp函数不能在结构体内部
  2. 对于一道题意不裸的题,都应该手玩样例检验没有看错题、想出来算法的基本正确性,再去code
  3. 标准差是方差的算术平方根,所以说所谓方差是不需要开根的
  4. 不等式的移项 一定要分析正负性
  5. stl的比较重载不能随便搞,一定要满足传递性和大小情况单一性(stl用<和>推导出=)
  6. fft得答案时要round
  7. 带取模计数,判无解不能用答案=0,因为答案可能是模数的倍数
  8. 注意!
    multiset的count复杂度和对应元素数量相关注意!
    set等非随机访问结构的lower_bound,必须调用结构内部的,用stl的那个函数会线性
  9. 注意 s&bin[i] 和 (s&bin[i])>0
  10. 用指针a[]表示数组的时候,sizeof a只会得到单位大小,而不是整个数组的大小
  11. 取模题最后转正很容易忘记,养成中途转正的习惯
  12. map等stl在结构体内的时候memset会gg
  13. 在无c++11的时候,queue系列的swap是o(n)的
  14. 如果一个东西的插入复杂度是通过势能分析保证的
    那么通常不能支持删除操作,因为可以多次进行高复杂度的操作
  15. 在CF上,任何自选模数的题都应该rand或者双模数,例如路径关键点、hash

奇妙结论

  1. 一个1到n的集合,选若干个不互质的数,要求和最大
    结论:每个数最多两个不同的质因子,且一个在根号内,一个在根号n外
    bzoj3308
  2. 让拓扑序的逆字典序最小,应建反向边跑大根堆;只会感性理解正确性

搜索

  1. 搜索去掉次序性的套路:强行限制大小关系
    举例:poj1011 Sticks
  2. 常见优化:优化搜索顺序、排除等效的决策和物体、可行性、最优性、记忆化
  3. 对于一个序列,拆分成多个序列的问题,有两种不同的方向:给每个元素分配组、通过组找元素
    最好能仔细根据题目斟酌一下策略,本人多次用2各种剪枝,也比不过裸的1……
    举例:SticksMissile Defence SystemZebras
  4. 50的整数拆分约为1e6,挺有用的;举例:[JLOI2012]时间流逝,有题解

数论

  1. 数论分块
    当出现连续的$\lfloor \frac{n}{i} \rfloor$时,值一定是单调不递增的,同值的区间可以合起来计算
    复杂度:$O(\sqrt n)$
    ① 当$i \leq \sqrt n$,分母只有$\sqrt n$种
    ② 当$i > \sqrt n$,$\lfloor \frac{n}{i} \rfloor < \sqrt n$
    $last=\lfloor \frac{n}{ \lfloor \frac{n}{i} \rfloor } \rfloor$
    举例:CQOI2007 余数求和、非常多数论题
  2. 由调和级数,1+1/2+1/3…1/n=logn
  3. 对于一个素数P,任何P以内的x,其倍数在模P意义下可以表示出所有P以内的数
  4. x不断对【<x】的数取模,只会进行 $O(logn)$ 次,讨论一下就知道了
  5. 【任意模数下存在逆元的数,其逆元互不相同】的证明: $ax=1(\%p)$,那么把其一作为未知数,根据裴蜀定理另一个与p互质

  1. 点分树上,点对的LCA一定也在原树两点路径上
  2. 在一棵边权非负的树上,与该点最远的一定是直径的某个端点
    两棵树合并起来,新的直径端点一定在两边直径端点中产生
    直径的中心唯一
    每个点的最远点,都一定经过直径的中心
  3. 一棵树上点集的连通块个数=点-边
  4. 很多模型能转化为树形
    例如互不重叠只包含的区间(最近一个包含作为fa)、某个变量只有单一指向(作为fa)
    举例:跳跳棋
  5. 图的dfs树不会有横叉边
  6. 虚树上如何找到原树某个点的第一个祖先(强制在线):
    $dfn_A \leq dfn_B \leq dfn_A+siz-1$
    我们先找到$dfn_A \leq dfn_B$的区间,然后就是这段区间能覆盖B的最右边的点
    这个可以在线段树上二分实现
  7. 用可重路径覆盖一棵树,最小数量:$\lceil \frac{度=1的点数量}{2} \rceil$

字符串

  1. 串的计数,枚举长度,建立间隔为长度的关键点(调和级数),然后每个串会经过一个关键点,枚举关键点算贡献
    举例:【NOI2016】优秀的拆分股市的预测
  2. 如果一个串是双回文串,一定存在一种分割,满足前面是最长回文前缀或者后面是最长回文后缀
  3. 一个串重复多次的最长回文子串,如果不是无限长,则最多是两个合并起来

决策算法

  1. 找前k优的区间,固定一个点后,左边的优秀情况是极值问题
    可以用堆维护左边,取出一个位置后把左边区间拆成两半放回去
    举例:超级钢琴树上的路径
    当然非区间一般也是用堆维护
    做法:堆维护,堆顶为最差元素
    举例:K远点对Supermarket
  2. max n个数的环上相邻差
    最小化这个,可以递增奇数+递减偶数
  3. 对于一些求大小为k最优集合的题目,不妨尝试猜测k一定为k-1的增量,感觉一般都不太好证明,不过可以画一画有没有反例:D

解题思路

  1. 有些题可以从简单情况着手、然后拓展到复杂情况(数学归纳法或者总结经验、模仿)
    或者先考虑普通情况,再考虑改进来解决特殊情况
    举例:noi2015 荷马史诗、poj2442 Sequence
  2. 对于比较陌生的题目操作形式,可以多造几组数据来模拟,找到一些性质,用这些性质转化题目
  3. 目前碰到处理棘手的删除问题的方法主要有两个,基本都需要离线
    一个是倒着做,这个对题目的要求较高;
    另一个是贪心,离线后按出现时间处理,然后按结束时间贪心
    举例:【bzoj4644】经典傻逼题【集训队互测2015】最大异或和【bzoj5040】航线规划【bzoj4229】选择
  4. 平方形式,可以转为为数点对,或者是进行两次然后相同的情况
    又或者可以处理其差分1,3,5,7,9,11……
    举例:NOI2009 管道取珠. 蔬菜. 学习小组
  5. 有关区间问题并用到区间最值,求出l[i]和r[i]表示第一个比a[i]大的位置,则l[i]+1~r[i]-1中间,用到的最大值都是a[i]
    不过要小心最大值相等而重复的情况,可以强行把左边界改严格来限制
    举例:洛谷18年7月月赛T4
  6. 需求:最大化最小值、最小化最大值
    做法:二分答案
    举例:一抓一大把
  7. 很多计数问题要求排列,可以时刻保证排列性,然后插入一个数,将比它大的数+1
    举例:51nod1296 有限制的排列、以及一些比较经典的树上dp
  8. 跟极值有关的区间问题,考虑一下已知某个极值贴着区间所带来的影响
    举例:hnoi2016序列、hnoi2017影魔、ioi2018会议、noi2019机器人的50分部分分(都有题解)
  9. 问从状态A操作到B,考虑倒着操作

其他

  1. 设cnt(x)为x二进制下1的数量,$cnt(a \oplus b)$ 为奇,当且仅当一个cnt为奇,另一个是偶
    因为两个1在一起是偶,不在一起也是偶
  2. 有时候矩乘的矩阵有特殊性,可以舍弃许多可推导信息来减少规模
    举例:弱题
  3. 权值总和为S的背包,可以 $O(S \sqrt S)$ 完成,即考虑大块小块有根号级别的不同权值,每种权值单调队列优化多组背包即可
  4. 取模题对拍时可以改小模数检验

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/80c8.html
转载请注明出处,谢谢!