「置顶」套路集锦

错误总结、套路集锦

带公式的项目前面编号会显示不出来,并不会修

常识

  1. 标准差是方差的算术平方根,所以说所谓方差是不需要开根的
  2. cmp函数不能在结构体内部
  3. 注意!multiset的count复杂度和对应元素数量相关
  4. 注意!set等非随机访问结构的lower_bound,必须调用结构内部的,用stl的那个函数会一次O(n)
  5. 在无c++11的时候,queue系列的swap是o(n)的

错误总结

  1. 不等式的移项 一定要分析正负性
  2. stl的比较重载不能随便搞,一定要满足传递性和大小情况单一性(stl用<和>推导出=)
  3. fft得答案时要round
  4. 带取模计数,判无解不能用答案=0,因为答案可能是模数的倍数
  5. 注意 s&bin[i] 和 (s&bin[i])>0 的不同(惯犯
  6. 用指针a[]表示数组的时候,sizeof a只会得到单位大小,而不是整个数组的大小
  7. 如果一个东西的插入复杂度是通过势能分析保证的(如sam、朴素pam、ac自动机)
    那么通常不能支持删除操作,因为可以多次进行再回撤高复杂度的操作
  8. 在CF上,任何自选模数的题都应该rand或者双模数,例如路径关键点、hash
  9. 线段树如果值域int,求mid的时候可能爆int
  10. 我习惯定义的循环宏fo,注意循环变量是ll的情况
  11. 感觉自己经常在想题过程中把题意扭曲了……以后如果卡住了要再三检查前面的题意转化是否出问题

做数论题的常用姿势

  1. 调和级数,$\sum_{i=1}^n n/i=O(n*ln(n))$,所以像$g(n)=\sum_{d\mid n}f(d)$这类较简单狄利克雷卷积无脑做是一个log的,但可以更快,类似高维前缀和的思想做。复杂度$=O( \sum \frac{n}{prm_i}=所有数的质因子个数和 )=O(n*log_2(log_2 n))$

    1
    fo(i,1,prn) fo(j,1,N/prm[i]) f[j*prm[i]]+=f[j];
  2. 关于约数,一个数num的约数可以$O(\sqrt{num})$枚举,可见约数个数上界为$2\sqrt{num}$;如果枚举一个数的倍数就是调和级数的复杂度,可见M内所有数的约数个数和上界为$O(n*ln(n))$;有时可以分析一个数的不同质因子数量(通过$2*3*5…>num$),典型题目

  3. phi小性质:「对于n>1,1~n中与n互质的数的和为$n \times \varphi(n)/2$ ,证明:$gcd(n,x)=gcd(n,n-x)$」、「深度为log级别。考虑n为偶数,则$\varphi(n)\le n/2$;若n为奇数,$\varphi(n)$一定是偶数」;一个显然正确的式子:$\varphi(ab)=\frac{\varphi(a)\varphi(b)d}{\varphi(d)}(d=gcd(a,b))$

  4. 关于整除:「$当x \le \sqrt n,\left \lfloor \frac{n}{\left \lfloor \frac{n}{x} \right \rfloor} \right \rfloor=x$」、「$\forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$」、「数论分块,将$\lfloor \frac{n}{i} \rfloor$相同的i合并起来计算,不同个数是$O(\sqrt n)$的,因为当值比根号大时,分母一定在根号内」

    第二条的证明:
    $$
    \begin{split}
    &\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\ \Rightarrow \\ &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\
    \end{split}
    $$

  5. $\sum_{i=1}^n d(i)^2约为nlog^2n$(毫无数学依据)

  6. 对于一个素数P,任何P以内的x,其倍数在模P意义下可以表示出所有P以内的数

  7. x不断对「<x」的数取模,只会进行$O(logn)$ 次,讨论一下就知道了

  8. 对于$\prod_{\sum x_i=S} x_i或\prod_{\sum x_i=S} x_i^k$这样的东西,不管在树上还是序列上,可以考虑其组合意义:每个块内恰放k个球。于是可以边走边放,记录当前所在的块内有多少个球,然后在位置上看要不要放,在间隔看要不要放隔板。

    举例:「集训队互测2018R4」青春猪头少年不会梦到兔女郎学姐「WC2019」数树

数学

  1. 期望有个套路的转化,恰好到达的状态的概率*步数之和,等价于所有未到达的状态的概率之和,这个你可以通过「把当前概率推到上面的步数个祖先上」理解
  2. 若$H*W且gcd(H,W)=1$的网格左下角射出$(0,0)\to(1,1)$的光线,则$\forall x,y \in N,(x+y)\%2=0,(x,y)会被经过$,其中不在边框上的点会被经过多次,且上述结论是充要的
  3. 一个1到n的集合,选若干个不互质的数,要求和最大;bzoj3308
    结论:选出的每个数最多两个不同的质因子,且一个在根号n内,一个在根号n外
  4. 思维僵化如我,$O(n)$求n个数的逆元,类似递推求阶乘逆元一样,求出$\prod a_i$的逆元再还原出前缀逆元,配合前缀积求出单个逆元

树形结构

  1. 点分的本质:点分树上点对的LCA一定也在原树两点路径上,可以从这个LCA统计这个路径的信息;然后点分有个小trick,如果处理一个块的复杂度通过根号分治达到$O(B\sqrt B)$,总复杂度为$n*\sum (n/2^i)^{1/2}=n \sqrt n*\sum \frac{1}{2^i}=n\sqrt n$

  2. 直径的性质(在一棵边权非负的树上):「与该点最远的一定是直径的某个端点」、「直径的中心唯一」、
    「每个点的最远点,都一定经过直径的中心」、「改一条边,端点最多变化一个」

  3. 重心和直径有个类似的结论:在一个点权为0/1的树上考虑带权直径、带权重心,「记下两个不重点集各自的任意一条直径端点,点集并的直径的端点一定能在这四个点中产生」,「记下两个不重点集各自的任意一个重心,点集并的所有重心一定都在这两个重心的路径上」

  4. 树上点集的连通块个数=点-边,将点集搞起来的最小虚树边数=「dfs序排序后成环,相邻两个求路径长度」/2

  5. 很多模型能转化为树形:

    A: 互不重叠只包含的区间(最近一个包含作为fa),例如析合树、一些性质题

    B: 某个变量只有单一指向(作为fa),这个其实是最常见的就不举例了

    C: 入栈出栈序列也是可以表示为树形结构的,节点x的子树大小为k,则表示x先入栈,然后子树内的元素为[x,x+k-1]且都更晚入栈更早出栈,举例:HDU5181 numbers

    D: 其他,举例:跳跳棋

  6. 虚树上(或者说给定点集)找到原树某个点的第一个祖先:第一个祖先肯定是第一个dfs序能包含的节点,且所有祖先的dfs序区间是包含的,等价于找到$dfn_y \leq dfn_x$的y中$dfn_y+siz_y-1$最小的那个,如果能离线最简单的写法是按照dfs序从小大大回答询问,用个int维护合法y中最小右端点来自哪里,这样是线性的;如果强制在线可以线段树上询问$[1,dfn_x]$上最小右端点来自哪里

  7. 用可重路径覆盖一棵树的每条边,最小数量为度=1的点数量,向上取整地除2。构造很简单,见下面经典问题2,那么就是要找到一个点作为根,各个子树叶子数$mx*2 \le sum$,这就是个带权重心,构造直接用堆模拟没毛病,多出来那货随便连一个点就是对的;例题:「BalticOI 2015」网络

  8. 用路径交可以判断是否存在一条路径包含某节点,求交的话,路径$(a,b)与(c,d)$如果有交,一定是$lca(a,c),lca(a,d),lca(b,c),lca(b,d)$中深度最大的两个点间路径

  9. 给定一棵树结构,每个点标号成排列,要求每个点的编号比子树其他点小,合法方案个数=$\frac{n!}{\prod siz_i}$,这个还是比较显然的,等价于

  10. 随机序列的笛卡尔树深度为log(每次期望为分成两半),即上升序列长度为log;笛卡尔树的期望子树大小也是log级别的

图论-其他

  1. 对于无向图,一个点双内如果有奇环,那么内部每条边都至少在一个奇环中;点双内有奇环的充要条件是在dfs搜索树上存在一个「一条非树边+若干树边」组成的奇环
  2. 让拓扑序的逆字典序最小,应建反向边跑大根堆
  3. 无向图的dfs树不会有横叉边,这种边很恶心所以一般随便找个生成树的时候都会选择dfs
  4. 一个图如果只有奇环,那么只会有简单环,因为两个奇环相交会产生偶环

字符串

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

决策算法

  1. 找前k优的区间,固定一个点后,左边的优秀情况是极值问题。可以用堆维护左边,取出一个位置后把左边区间拆成两半放回去,举例:超级钢琴树上的路径

  2. 对于一些求大小为k最优集合的题目,不妨尝试猜测k一定为k-1的增量,感觉一般都不太好证明,不过可以画一画感受一下有没有反例:D

解题思路

  1. 目前碰到处理棘手的删除问题的方法主要有两个,基本都需要离线
    一个是倒着做,这个对题目的要求较高;另一个是贪心,离线后按出现时间处理,然后按结束时间贪心
    举例:「bzoj4644」经典傻逼题「集训队互测2015」最大异或和「bzoj5040」航线规划「bzoj4229」选择

  2. 平方形式,可以转为为数点对,或者是进行两次然后相同的情况,又或者可以处理其差分1,3,5,7,9,11……
    举例:NOI2009 管道取珠, 蔬菜学习小组

  3. 很多计数问题要求排列,可以时刻保证排列性,然后插入一个数,将比它大的数+1
    举例:51nod1296 有限制的排列、以及一些比较经典的树上dp

  4. 跟极值有关的区间问题,考虑一下已知存在某个极值贴着区间外所带来的影响(笛卡尔树dp之类的)
    举例:hnoi2016序列、hnoi2017影魔、ioi2018会议、noi2019机器人的50分部分分(都有题解)

  5. 问从状态A操作到B,可以考虑倒着操作,适用于做某种操作可达性、构造

  6. 表格图上行和列两侧成二分图,$(i,j)有棋子则i到n+j连边$

  7. 求只包含一点、只不包含一点的信息的一类问题

    套路大概是分治,大概没法直接说懂,给出两道题,选一道题看,然后大概就能理解并做出另一道题了

    一个是这里,一个是XSY2469

  8. 假如在序列上有很多区间,但这些区间长度都是L,那么可以对序列按L分块,于是每个区间一定是「某个块一段后缀」+「某个块一段前缀」组成,举例:「LR11」Misaka Network 与 Accelerator

技巧

  1. 取模题对拍时,如果暴力能做范围很小,可以改小模数检验
  2. 对于比较陌生的题目操作形式,可以多造几组数据来模拟,找到一些性质,用这些性质转化题目

经典问题

  1. 权值总和为S的背包,可以$O(S \sqrt S)$ 完成,和根号分治类似有根号级别的不同权值,每种权值单调队列优化多组背包即可
  2. 若干个不同的集合,要求选最多对数满足来自不同的集合;当$mx>sum-mx$,显然答案为$sum-mx$,否则考虑在一个堆中每次取最大的两个集合拿出一对数再塞回去,答案为$\lfloor \frac{sum}{2} \rfloor$;如果每次要k元组,那应该只能用堆模拟了?不过有一个不错的式子,反过来对于一个答案W,有哪些k可以至少取到W:$kW \le \sum min(count_{num},W)$,这个的必要性显然,构造证明式子是紧的:大于W的那些给W组都丢一个,小的那些选一部分丢一个进去,最后肯定能搞出W个(看起来很废话
  3. max n个数的环上相邻差;最小化这个,可以递增奇数+递减偶数
  4. 两个凸函数f和g,做$(max,+)卷积,即h_{i+j}=max\ f_i+g_j$,得到的h也是凸函数,证明显然;$h_{i+j+1}的(i,j)构成,与h_{i+j}的(i,j)构成$,一定能只改变一个,于是可以双指针线性合并
  5. 01分数规划,例如最大化平均数,二分判断是否存在$sum-ln*T \ge 0,\sum (val-T) \ge 0$

其他

  1. 设cnt(x)为x二进制下1的数量,$cnt(a \oplus b)$ 为奇,当且仅当一个cnt为奇,另一个是偶
    因为两个1在一起是偶,不在一起也是偶
  2. 二进制数相减,不要考虑借位,而是允许-1存在,加法类似
  3. 所有n的排列中,奇排列数p=偶排列数q,因为交换任意两个元素必定使逆序对奇偶性变化,对所有p交换某两个位置,$p \ge q,同理q \ge p$

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