「置顶」套路集锦

错误总结、套路集锦

常识

  1. 标准差是方差的算术平方根,所以说所谓方差是不需要开根的

  2. cmp函数不能在结构体内部

  3. 注意!multiset的count复杂度和对应元素数量相关

  4. 注意!set等非随机访问结构的lower_bound,必须调用结构内部的,用stl的那个函数会一次O(n)但不会报错

  5. 在无c++11的时候,queue系列的swap是o(n)的

  6. stable_sort在一些交互题中很好用(sort会在较小的地方用插入排序)

错误总结

  1. 不等式的移项 一定要分析正负性

  2. stl的比较重载不能随便搞,一定要满足传递性和大小情况单一性(stl用<和>推导出=)。例如在cmp里写>=这种东西会re

  3. fft得答案时要round

  4. 带取模计数,判无解不能用答案=0,因为答案可能是模数的倍数。特别是一些模数在输入给出的题,特别好构造

  5. 注意 s&bin[i] 和 (s&bin[i])>0 的不同(惯犯

  6. 用指针a[]表示数组的时候,sizeof a只会得到单位大小,而不是整个数组的大小

  7. 如果一个东西的插入复杂度是通过势能分析保证的(如sam、朴素pam、ac自动机),那么通常不能支持删除操作,因为可以多次进行再回撤高复杂度的操作

  8. 线段树如果值域int,求mid的时候可能爆int;另外区间范围涉及负数的时候,mid=(l+r)/2会有取整方向问题,导致RE

  9. 在CF的在线比赛时,任何自选模数的题都应该rand或者双模数,例如路径关键点、hash

  10. 我习惯定义的循环宏fo,注意循环变量是ll的情况

  11. 感觉自己经常在想题过程中把题意扭曲了……以后如果卡住了要再三检查前面的题意转化是否出问题

  12. 计数等题经常会出现等比数列,记得判公比为1的情况

  13. 经常写着写着忘记,点分治最外面那次也要找重心……

  14. 以后一些以为想清楚的不会发生/必定发生的情况,也要写个assert

做数论题的常用姿势

  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}$;如果枚举一个数的倍数就是调和级数的复杂度,可见n内所有数的约数个数和上界为$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}
$$

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

  2. x不断对「<x」的数取模,只会进行$O(logn)$ 次,因为每次做完的结果总是不超过x/2

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

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

  4. $gcd(x_1,x_2…x_n)=gcd(x_1,x_2-x_1,….,x_n-x_{n-1})$,经典问题就是区间加法求区间gcd

  5. 有时候会碰到些奇怪的模数导致某数z没有逆元,如果答案一定是整数的话,可以考虑先所有数放大z倍(即先按这个算,而且模数也要放大z倍),最后模出来的结果一定是z的倍数,直接除掉

  6. 根据wolframalpha,$O(\sum_{i=1}^n \frac{1}{i^{1.5}})=O(1)$,看起来很帅

数学

  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$的逆元再还原出前缀逆元,配合前缀积求出单个逆元

  5. 有些模型是n个中选k个且k给出,然后最优化一些东西;那么随机一个点作为答案中某点,复杂度中含有k时,我们有时间做n/k次,借助wolfram知错误率极限是$\frac{1}{e}$(其实就是k=1最坏然后用e的定义?),次数乘个5之类的,正确率就足以接受了

树形结构

  1. 点分的本质:点分树上点对的LCA一定也在原树两点路径上,可以从这个LCA统计这个路径的信息

    然后点分有个小trick,如果处理一个块的复杂度通过根号分治达到$O(B\sqrt B)$,总复杂度为$n*\sum (n/2^i)^{1/2}=n \sqrt n*2\sum \frac{1}{2^i}=O(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

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

  7. 多个点的lca=dfs序最小和最大点的lca

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

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

  10. 给定一棵树结构,每个点标号成排列,要求每个点的编号比子树其他点小,合法方案个数=$\frac{n!}{\prod siz_i}$,因为某个子树成立的概率是独立的

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

  12. 树上高斯消元可以线性:将每个方程写成$f(x)=k_x*f(fa)+b_x$的形式,这个从叶子开始就能搞出来,最后$f(rt)=b_{rt}$

  13. bfs序递增加入树上点的话,设$dfn_i,dfn_j<dfn_x$,$若dis_{i,x} \le K,dis_{j,x} \le K则dis_{i,j} \le K$

    证明考虑$path_{x,i}和path_{x,j}$的第一个分叉点w且i在w子树内,则$dis_{i,j} \le dis_{x,j} \le K$

图论-其他

  1. 对于无向图,一个点双内如果有奇环,那么内部每条边都至少在一个奇环中;

    点双内有奇环的充要条件是在dfs搜索树上存在一个「一条非树边+若干树边」组成的奇环;

    一个图如果只有奇环,那么只会有简单环,因为两个奇环相交会产生偶环

  2. 让拓扑序的逆字典序最小,应建反向边跑大根堆,在AGC001F中用过

  3. 无向图的dfs树不会有横叉边,这种边很恶心所以一般随便找个生成树的时候都会优先选择dfs(但是注意,可能会有向下的边,即在返祖边的上面访问这条边)

  4. 基环内向树森林修改出边得到一个环的最小步数为孤立环+叶子;策略的话先说一棵基环树,就是将环上每个点a挂的树内所有叶子向下个叶子连接,然后a的上一个点连向a的树得到的叶子链的首部。加入其它孤立环的话,从某个a那里拆就只会增加一次操作。例题:projecteuler522 Hilbert’s Blackout

  5. 众所周知森林有$联通块=点-边$,同理仙人掌有$联通块=点-(边-环)$

字符串

  1. 如果一个串是双回文串(两个回文串的拼接),一定存在一种分割,满足前面是最长回文前缀或者后面是最长回文后缀

  2. 同一个串重复无限次得到串的最长回文子串,如果不是无限长,则最多用两个也能拼起来(三个以上的话,随便画一画就会发现,必须满足自己是个双回文串,一定无限)

决策算法

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

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

数据结构

其实k维偏序在k较大时可以考虑bitset做,时间都是$O(kn^2/w)$

做法一:对每个询问维护哪些点在前面所有维都满足条件,考虑这一维时把询问和点排序,递增处理询问,空间是$O(n^2/w)$,时空常数为1。如果空间被gank了但时间充裕,把被询问点分成B次做,这样时间乘B,空间除B

做法二:先预处理出$(i,s)=第i维 \le s的集合$(必须将值离散化成n的排列),然后枚举每个询问做并,这样时空是常数2的$O(kn^2/w)$;优化空间的话,把前面第二维分块,设块大小为T,时间$O(k*\frac{n}{T}*(n/w+T)+qk(n/w+T))$,空间$O(k*\frac{n}{T}*n/w)$。在不太影响时间时取$T=n/w,空间为O(kn)$

所以在卡空间时方法二更优越,方法一的优势大概是好写?

一些突破口

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

  2. 如果一个式子出现k次方,可能是直接斯特林数或二项式定理处理,如果是建图相关可以差分成2x+1(如WC2007石头剪刀布学习小组),也可能是考虑组合意义:如果是$某整数变量^k$可以看做在其中恰好放k个球(如蔬菜),如果是类似于$\sum_i (x=i的情况数)=S,求\sum_i (x=i的情况数)^2$,可以看做$\sum_i (\sum_{情况} [x=i])^2=\sum_{情况1} \sum_{情况2} [x_1=x_2]$,这样就跟具体是什么无关了(如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
    类似地,如果区间长度不定,枚举每种区间长度L做(毕竟块数满足调和级数,只要能把复杂度搞得只与块数有关就好了),例如每个区间都会经过恰好一个关键点,枚举枚举关键点算贡献(计数啥的),举例:「NOI2016」优秀的拆分股市的预测、poj3693 Maximum repetition substring

  9. 然后每个串会经过一个关键点,
    举例:「NOI2016」优秀的拆分股市的预测、poj3693 Maximum repetition substring

  10. 有的问题如果确定一部分,另一部分的限制会很强,可以考虑meet in middle,如CF1257F

  11. 很多单点修改维护整体答案的题目,可以考虑转化题意为可并信息(无脑的就是矩乘,有脑的就是自己定义两个结构体的运算),然后用线段树维护

  12. 对于n不大或随机算法的题,多多注意能否将大小<i的东西去掉,使得n/=i,优化指数级算法,或者正确概率乘以i

技巧

  1. 取模题对拍时,如果暴力能做范围很小,可以改小模数检验

  2. 对于比较陌生的题目操作形式,可以多造几组数据来模拟,找到一些性质,用这些性质转化题目

  3. 分治的时候判掉l=1可以让$2l>r$,这是一些自己搞自己的分治算法需要考虑、可以加以利用的,如一些分治NTT(例如链式反应)

经典问题

  1. 物品权值总和为S的背包,可以$O(S \sqrt S)$完成:只有根号级别的不同权值,每种权值单调队列优化多组背包即可;

    另外集合${1,2,..n}的01背包也可以O(wt^{1.5})$完成(整数拆分),就是多加根号wt级别的一维记录使用的数字个数
    然后$dp(S,m)$可以从$dp(S-m,m)$整体加1得到,也可以从$dp(S-m,m-1)$即第一个是1
    但要注意不能得出比n大的数,综上$dp(S,m)=dp(S-m,m-1)+dp(S-m,m)-dp(S-(n+1),m-1)$

  2. 若干个不同的集合,要求选最多对数满足来自不同的集合
    当$mx>sum-mx$,显然答案为$sum-mx$;
    否则只要每次在最大集合中取一个,在其他地方取一个,就能始终保证满足$2mx \le sum$,答案为$\lfloor \frac{sum}{2} \rfloor$;

    如果每次要k元组,那应该只能用堆模拟了(每次取前k大)?不过有一个不错的式子,反过来对于一个答案W,有哪些k可以至少取到W:$kW \le \sum min(count_{num},W)$,这个的必要性显然,构造证明式子是紧的:先把大于W的那些给W组都丢一个,小的那些选最少的若干个丢一个进去,肯定能搞出W个(其实这样构造的话组的大小只会有A和A+1两种,找A的那些放即可)

  3. 最大化长度为n排列的首尾相接时相邻差;最小化这个,可以递增奇数+递减偶数,正确性是显然的。然而值得一提的是,最小化相邻差的平方和(根据$(a-b)^2=a^2+b^2-2ab$,等价于最大化相邻乘积的和)也是这样放(而且能拓展到任意实数序列),证明见[NOI Online 提高组]最小环中EI写的题解,类似的题是loj520「LibreOJ β Round #3」绯色 IOI(开端)

  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-cnt*T>=0$即$\sum (val-T)>=0$

  6. 一个数的所有约数的哈斯图的最长反链(定义一个数被另一个数整除时可比)
    首先肯定是Dilworth去转成最小链覆盖,然后观察这个图的特性发现这其实每个点$\prod p_i^{k_i}可以看做(k_1,k_2..k_{cnt})$,然后发现是可以按$\sum k_i$分层的,而分层dag的最小链覆盖显然是最大的那个层的大小,对于本问题就是$\prod_i (\sum_{j=0}^{mx_i} z^j)$的最大系数,可以分治NTT做。事实上一个结论是这东西的系数是先递增再递减的,且其最高点为$[z^{\lfloor (\sum mx)/2 \rfloor}]$,相关资料可见此OEIS。例题:CF1257G Divisor Set

  7. 麻将题,「CF1110D」Jongmah

  8. $\frac{x}{y} \in (\frac{a}{b},\frac{c}{d})$要最小化x或y:为了方便说明,假定$\frac{x}{0} \to \infty$:

    先$\frac{x}{y} \in (\frac{a}{b},\frac{c}{d}) \rightarrow \frac{y}{x} \in (\frac{d}{c},\frac{b}{a})$,这样就是最小化分母

    设$solve(\frac{a}{b},\frac{c}{d})$找到最小的y满足$\frac{x}{y} \in (\frac{a}{b},\frac{c}{d})$

    1. $\frac{a}{b} \ge 1$,$t=\lfloor \frac{a}{b} \rfloor,solve(\frac{a\%b}{b},\frac{c}{d}-t,\frac{x}{y}-t)$,因为分母不会变

    2. $\frac{a}{b}<1,\frac{c}{d}>1,x=y=1$

    3. $\frac{a}{b}<\frac{c}{d} \le 1,将分数倒置,\frac{x}{y} \in (\frac{a}{b},\frac{c}{d}) \rightarrow \frac{y}{x} \in (\frac{d}{c},\frac{b}{a}),但此时问题是最小化分子$

    然后就懵逼了很久,感性上说分数这种jb玩意的大小关系是个整体,但这次真的不太想感性了

    其实理性的话就一句:$\frac{c}{d}有最小分子,\frac{a}{b}有最小分母,则\frac{c}{d} \le \frac{c}{b} \le \frac{a}{b}$,而$\frac{c}{b}$作为大人不想做选择

    接着分析复杂度,注意到每次是把左边界搞个辗转相除,然后交换左右边界,因此复杂度为$O(2log)$

    例题如Codejam2019Round2 New Elements Part 22019多校hdu6624 fraction

其他

  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. 对于$D=x^2+y^2$,对x和y奇偶性讨论可知:$D\%4=0 \leftrightarrow xy都是偶$;$D\%4=2 \leftrightarrow xy都是奇$;$D\%2=1 \leftrightarrow 一奇一偶$。可能构造题会比较常见,例如CF1270E Divide Points、AGC025D Choosing Points

  5. m次操作,第i次操作为将区间染色成i,始终保持连续相同的颜色缩起来成块,则每次区间操作覆盖的块数之和总和为$O(n)$。可以简单势能分析,每次块数约为删除块数,而新建块数只有1

国家集训队论文集

论文集2012
论文集2013
论文集2014
论文集2015
论文集2016
论文集2017
论文集2018
论文集2019

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