终末之章

前言

走了,回来了,不管如何,这条路似乎已经延伸得很漫长了,从兴趣,变成兼修,变成接近专修,又变回兴趣,,这中间的路太长,以至于虽然百味杂陈,却说不出什么感想.

除了爱与恨以外,我有时候觉得信息学已经成为了我生命中无法割舍的一部分了,不知是好是坏

这样长篇的总结,大概在我还能被称作所谓的竞赛选手时,不会有多少了

亦是最后的挣扎,亦是痛心的告别,希望这条路还能再延伸那最后的一段吧

特殊思路

环断边:对于环上存在的问题,可以考虑将环倍增然后断为链.一般用于从某点开始对环进行遍历的问题
权值与下标交换:将答案设为下标,将下标放入数组的权值.适用于答案极值偏小,但是某一下标过大且表达的信息过于离散的问题(如JOI 2020 final-集邮比赛),如果仍然放不下的话可以考虑二分答案
对于元素独立,询问独立且多个限制之间互相独立的问题,可以先通过遍历来筛选元素,且降低元素的特异性,使得后续处理与存储更为优秀,实际可以总结为提取出所需要元素的有效信息,优化存储/处理方式

做题思想

解决后效性

首先在设置状态时,要搞清楚哪些变量之间互不影响,前后计算没有任何影响,一般会将其设为状态

其次,对于设置完的状态出现后效性问题,有两种解决方式

再设置一个下标来分开各个选择以消除后效性(因为可获得之前选择的更多信息所以后效性不影响)
类似于上一种,可以尝试将状态之间转移的关系提前计算为一个数组,并且在这个数组中处理后效性.这种做法要求各个状态之间的转移经常规律性变化(类似于矩阵)

常识

n个元素的子集的子集个数为$3^n$
计数类问题常使用总方案数减不符合要求的方案数

结论

猴子打字

大概形式为在一个字符范围内随机增加字符,求最后$k$个字符为某一字符串时的期望打字数

结论:设$f[i]$表示当前已经打的字符串中后$i$个字符与目标串匹配时达到最终状态的打字期望数,$p$为字符集大小,$fail$的定义与$kmp$中的定义相同,均表示最大失配指针

$f[i]=f[fail[i]]+p^i$

基础算法

高精度

一个工具,当计算的数据达到需要的程度时使用即可

枚举算法

一般出现在当前题目的计算要求过于复杂,且数据范围极小时

直接对于一些可能出现状况极少的变量进行枚举

递推

通过特定方式进行多次运算,最终解决复杂问题

与dp的主要区别在于是否动态比较更改答案,但是信息学一般不做区分

一般性递推

按一个线性方式遍历数据然后以此不断更新答案获得最优解

组合计数

由于研究对象会有一定限制,所以利用其他的数组实现阶段性地递推或者提高状态描述维度以解决限制

部分博弈问题

通过合适的状态设定获得博弈图,然后根据题目规则来获得当前博弈图的必胜必败态的关系,然后由唯一确定的最终状态(必胜态)逆向推导获得答案

由于递推非常具有规律性,所以经常可以将递推过程简化

dp

详见dp类

递归

仅一种实现方式

分治

主要标志: 当数据小到一定程度(即子问题)时,问题易解决且问题答案可以通过子问题答案合并获得

CDQ

当一个数组上的计数类问题或最值问题存在多个要求且相互独立时可以使用CDQ来依次解决(一般第一维在最外层排序解决,第二维在分治过程中排序解决,第三维使用线段树或树状数组解决)

当相互独立的限制超过三个时CDQ一般不是最优解

最优解类分治

一般下一层所得结果可以限制上层需要询问答案的范围

点分治

适用于解决大规模树上路径信息的问题

边分治

与点分治类似,更适合解决边上问题

点分树

一种将树的最大深度控制在严格$log(n)$的重构方式,适用于与树原形态无关的问题

整体二分

当一个可以简单二分解决的问题要求多次询问时,对于每次询问分别二分的话,会有大量的重复运算,所以将所有询问一并读入,然后在一次二分中同时处理

二分一般同时传递当前区间的询问与修改并在二分的一次执行中经常使用树状数组维护

树状数组清零很慢,一般将所有进行过的操作反向进行一边(指加减)
有时直接传递vector会导致空间不足,这时可以发现,二分操作的序列可以直接将原数组部分重新排序,然后只传递操作序列的左右端点即可,查询时直接在原序列中查询

贪心

区间最大覆盖个数

在一个数轴上按照区间覆盖,求最大能放下的区间个数

按右端点排序依次取

区间选点

在数轴上放点使得所有给定区间内都有点

按右端点排序,尽量往右边放

区间覆盖

在数轴上用尽可能少的区间表示所有给定区间的并

按左端点排序,依次查询合并

搜索

剪枝

减少搜索范围
当前状态无法获得更优解
当前状态无法得解

杂项

莫队

适用于可以在$O(1)$的时间将区间$[L,R]$的答案转移得到$[L,R+1]$与$[L-1,R]$的答案时

奇偶性优化

对于奇数块的询问,按$R$从小到大排序，对于偶数块的询问，按$R$从大到小排序

三分

适用于答案存在于一个单峰函数的极值问题上

dp

坐标类

所有方案数
一条最优路径
两条最优路径(状态中同时表示两条路径的到达点,一同转移)

提高组dp不一定会很复杂,所以尝试思考高维的状态来表达

线性

LIS

单调队列优化
值域二分优化

LCS

同样,注意考虑高维状态来维护

区间

对于环上问题可将环拓展为两倍,然后取区间长度为n的答案的最优值

背包

01

$f[i]:使用i的空间的最大价值\\ f[j]=max(f[j],f[j-c[i]]+v[i])$

for(int i=1;i<=n;i++){
	for(int j=m;j>=1;j--){
        f[j]=max(f[j],f[j-c[i]]+v[i]);
    }
}

完全

$f[i]:使用i的空间的最大价值\\ f[j]=max(f[j],f[j-c[i]]+v[i])$

for(int i=1;i<=n;i++){
    for(int j=c[i];j<=m;j++){
        f[j]=max(f[j],f[j-c[i]]+v[i]);
    }
}

多重

$f[i]:使用i的空间的最大价值\\ f[j]=max_{k=1}^{num_i}(f[j],f[j-k*c[i]]+k*v[i])$

for(int i=1;i<=n;i++){
    for(int j=m;j>=1;j--){
        for(int k=1;k<=num[i];k++){
            f[j]=max(f[j],f[j-k*c[i]]+k*v[i]);
        }
    }
}

二进制优化

将k个i物品拆成许多个包含$2^x$个的i物品的物品集,当作新物品,将多重转化为01

单调队列优化

由于单调队列基本的dp方程并非仅与当前枚举变量有关,所以改变枚举方式

令$\Large g_{x,y}=f_{i,x\cdot c_i+y}$,$\Large g’_{x,y}=f_{i-1,x\cdot c_i+y}$

$\Large g_{x,y}=max(g'_{x-k,y}+k\cdot v)\\ \Large g_{x,y}=max(g'_{x-k,y}-(x-k)\cdot v)+x\cdot v$

这里注意到max内式子只与x-k有关,并且我们之前的枚举会访问他,所以可以直接单调优化

混合

对于不同的物品使用不同的方程dp即可

二维费用

与一维类似,两种限制分别枚举,不冲突

分组背包

先枚举组,再枚举组内物品,最后枚举消耗(也就是f数组的参数)

依赖背包

对于每一个主件及其附带附件,将所有可能的购买情况记录下来,当作分组背包做

对于多叉树,先算子节点,再算父节点

最大子序列/子矩阵及类似问题

一维

简单dp,类似01背包的做法

二维

对于规定大小的类型,可以直接前缀合优化解决

对于未规定大小的类型,首先枚举矩形的左右边界,然后将上下当做一维问题解决

注意n,m范围,有可能会出现特殊情况,如m<=2

树型

二叉树

由于二叉树每个点儿子都极少,所以可能存在枚举左右儿子分配资源(消耗)或者枚举左右01分别状况的dp

子树影响

有些时候看似题目本身存在后效性,但是可以通过一定的理论证明来优化dp方程或者增加状态,以消除后效性

如Luogu P2899

多次

实际只是dp问题无意义的独立嵌套,需要注意不忘记这一做法即可.对于信息过于复杂时,可以尝试考虑通过多次dp来简化问题

如SCOI2009-粉刷匠,JZOJ 1303-骑士

状压

状压题目的标志性一般极其明显,当数据范围极小但是每个点之间的选择状态又会造成影响时,可以考虑状压

很多时候仅仅压缩一维状态并不能设出无后效性的状态,所以可以设置类似于最后到达哪个点这样类似的第二维甚至第三维
状压问题并不一定要枚举从$0$到$1$的位,实际可以直接枚举子集,完成转移

铺瓷砖

在给定空间中用刚好的特定形状的物品填满,一般选择物品的一个特定点来代表整个物品来状压

单调队列

将dp方程写出后进行变形,如果最后能够做到使min/max中不存在与i有关的变量的可以进行单调队列优化

同时要求

斜率优化

对于一类动态规划问题,若可以将转移方程变形为如下形式,则可以将决策点转化为二维坐标系上具象化的点

$k_1x+f[i]*k_2+b=y$

其中$k_1,b$与当前点有关,$x,y$与决策点有关,而$k_2$为常数,仅与方程有关

方程变形过程中主要注意将与$i$有关,与$j$有关,与$i,j$有关的量分开

斜率单调&决策点单调

决策点单调即x单调

直接使用单调队列维护

斜率不单调|决策点不单调

CDQ分治或平衡树解决

决策单调性

对于最优化dp(即转移只来自一个点,而非许多状态的加和),若通过理论分析或者打表分析得到决策点只向一个方向变化的结论,即可只从上一个状态的决策点向后枚举转移

对于任何最优化dp都可以尝试考虑单调性优化

常与整体二分一同考核

四边形不等式

本质就是决策单调性,但是形式稍特殊,一般还是使用打表分析决策点是否单调

形式类似区间dp

数据结构优化

对于任何一个状态的转移,存在区间的连续枚举,那么可以简单的用数据结构维护区间内权值(一般下标与dp数组的下标不一致)

数位

一种极为特定的dp,多为计数类dp

一般询问方式为从$L$到$R$之间有多少个数满足要求

注意记忆化时的条件要求,一定要不满足上界时才可记忆化

概率&期望

概率类问题一般采用正推,而期望类一般采用逆推

若存在后效性,则使用高斯消元解决

数据结构

提高组并非省选,不太可能存在太多的高级数据结构,将基础的几类运用纯熟更为重要,以及总结其拓展

并查集

可用于分连通块,查询联通

可带权值,需在路径压缩时更新权值

经常将每个对象的几种状态拆点,然后类似2-sat进行计算

树状数组&线段树

区间修改与区间查询