CSP2019集训总结

发布于 2019-11-15  300 次阅读


By Tony102

Nov. 15, 2019

算法总结

动态规划

区间DP

  1. 通常用来解决一类合并求最大收益的问题,注意区间DP是一个有合并顺序的DP
  2. 有时候区间DP可能会有一些类似于倍增的思想,而非常见套路(见[USACO16OPEN]262144)

例题: UVA10559 方块消除

数位DP

  1. 一个数有很多位,按照一位一位去dp。
  2. 通常一般就是要统计一个区间[l,r]内满足一些条件数的个数

例题:SCOI2009 Windy数 HDU2089 不要62

状压DP

非常暴力的DP,通常用来处理一种选/不选为状态的题目,状态通常用一个二进制数表示(前置知识位运算)

用一个二进制数来表示这种状态的思想亦可用在搜索上,极大减小空间占用.

例题:SCOI2005互不侵犯 [USACO06NOV]玉米田Corn Fields

树形DP

通常有三种模型:选点类,树形背包类和换根DP

树形DP通常从下至上处理,这样比较简介也容易符合最优子结构

选点类树形DP是最为基础的DP,其主要模型为:设f[u][0/1]表示选或不选这个节点及其子树.

树形背包类DP跟上面的有些类似,但是需要处理最优性问题.与背包的思想差不多.

换根DP用于处理一些看似需要 O(n^2) 的复杂度内解决的问题,而实则可以在 O(n) 的时间内解决.通常需要先钦定一个根(例如1号节点),并对它进行原先的DP.之后再通过遍历计算贡献其他节点为根的子树的贡献即可.

例题:HNOI2018 道路 选课 CF1187E 没有上司的舞会 POJ3345 / UVA1222 Bribing FIPA

序列/线性DP

• 序列dp的给出形式一般两种:
• 1.给你序列,让你划分成若干块。
• 2.给你序列,选出一个子集。
• 不难发现,这两种是差不多的。
• 所以我们是设f[i]代表前i个,并且选择第i个的答案,如果还需要+状态,那么是用来描述前面的子集的性质
的。
• 当然也不一定非得这种形式,比如可以f[i]代表前i个的答案,每次转移枚举下一个是否放入集合A中,这个
就是类似于数位dp的转移。
• 总结:两种dp形式,一个是枚举子序列中的上个数,一个是枚举当前这个数选不选。

上面引用了GZY在讲解序列/线性DP时候的总结,很精华.

这一类DP的优化手段主要是:单调队列;决策单调性;斜率优化;数据结构优化;凸优化

经典的模型有如:LIS. 例题:CF10D HNOI2008 玩具装箱

背包

这一类问题通常用来解决:你有一些物品和一些钱,希望通过用这些钱购买物品获得最大价值的一类问题.

主要有:0/1背包,完全背包,多重背包,分组背包和依赖背包与背包方案计数问题.

例题:采药 金明的预算方案 开心的金明 HAOI2008 硬币购物

技巧: 对排列的处理手段

• 最优化问题:
• 可能可以通过排序的手段使得按照某种顺序是最优的,这种情况可以转化为序列dp的问题。
• 对排列位置本身的限定(p_i ≥p_j),如贪心中讲过的HNOI2015菜肴制作,HNOI2018D2T2,这个一般
靠贪心。

• 计数类:一般统计合法排列的个数。又分两种
• 对排列位置本身的限定,比如说我限定p_i\leq pj ,这个在偏序关系为树的情况下可以方便统计; 值得注
意的是,如果偏序关系为一条链(方向不确定),某些时候我们只需要判断相邻大小关系,那么可以
f[i][j]枚举i在前i个中的位置是j,这样dp即可,在某些时候有奇效。
• 对排列的一些限制,同样也需要特殊处理,与最优化的差不太多。

贪心

贪心是一种由局部最优推广至全局最优的思想。推广至全局最优时,往往可以获得某些性质,或者消除某
些条件。

常见模型:

  1. 需要给出一个顺序,使得一个函数最大(国王游戏)。
    改变相邻两个数的顺序并不影响全局,并且满足传递性,所以可以按照这个大小关系直接排序。
  2. 最小化字典序,使该排列/字符串合法。有两种思路,不过都是基于已经选出一个前缀而言的:一种是
    从字典序最小的开始加字符,直到存在合法的为止;另一种是维护增加字符存在合法串的集合,从中
    选出最小的。

一些比较经典的问题:

 1. 若干个区间,选出最多的区间个数使得区间两两不交。
 2. 每个区间有权值,使选出的权值和最大。
 3. 选出最少的区间覆盖整个序列。
 4. 每个区间有代价,选出的权值和最小。

对于第一个问题,我们可以对右端点排序,能选则选;

对于第二个问题,设f_i代表前i个位置的答案,对每一个区间都有一个转移f_r=max(f_r,max{f_j}+w) . (j

对于第三个问题,左端点排序,每次覆盖一个最长的前缀。

对于第四个问题,本质和第二个问题一模一样,取min即可.

经典例题:田忌赛马 数据备份 拯救小矮人 观光公交

题解:拯救小矮人

数学与数论

之前写了很详细的总结了,放上链接

Math.pdf

搜索

基础的搜索:深度优先搜索(爆搜),广度优先搜索,迭代加深搜索

广搜可以开双端队列优化(不好写)

启发式搜索有A*,IDA*

剪枝主要根据题目确定剪枝方法,最基本的剪枝方法有:最优性剪枝\排除等效冗余\可行性剪枝和记忆化.

例题:小木棍 Sudoku K短路 八数码难题

字符串

联赛考的很少,学会Manacher就不错了

例题:Manacher算法模板 [国家集训队]最长双回文串

数据结构

基础数据结构

一种先进后出的数据结构,基本操作有进栈和出栈,STL中有stack

它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

队列

与栈相似地,基本操作是入队和出队,STL中也有queue提供使用

广搜时经常要用到队列

链表

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的顺序表,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

例题:小奇的糖果

并查集

基本数据结构, 没有任何优化的复杂度在O(n) (询问,操作)

基本优化

启发式合并(按秩合并)

运用启发式合并的思想,我们尝试每次将较小的集合并入较大的集合.由于要判断集合之间的大小关系,每一个元素需要维护其所在集合的大小.

运用启发式合并后的时间复杂度可以被证明为:O(nlog_2n)

参见如下代码:

const int SIZE = 10000 + 5;

int fa[SIZE], Size[SIZE];

int Find(int x)
{
    if (fa[x] == x) return x;
    return Find(fa[x]);
}

void Unite(int x, int y) 
{
    x = Find(x), y = Find(y);
    if (Size[x] > Size[y]) std::swap(x, y);
    fa[x] = y, Size[y] += Size[x];
}
路径压缩

在更进一步地,我们发现集合中只有代表元是有用的,而寻找代表元是经过的中间点是冗余的,如果我们将这些中间点再访问过后直接将他们的父亲指向集合的代表元,在后续的访问中就不会产生这部分的冗余

路径压缩后的复杂度约为O(n\alpha(n)),其中\alpha(n)是反阿克曼函数,增长极其缓慢,可以看做常数[4,5], 可以被卡到O(nlog_2n)

参见如下代码:

int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }

带权并查集

在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算,从而解决更多的问题

由于并查集的实质是由若干棵树构成的森林,可以维护一个数组d[],记录节点到其父亲之间的比安全

例题:[NOI2002]银河英雄传说

并查集的扩展域

可以根据题目将并查集倍长,根据不同的关系将不同域的节点并在一起

例题:[NOI2001]食物链 [JSOI2008]星球大战 [BOI2003]团伙

支持插入、求最大值、删除最大值的数据结构。
一般都写 std::priority_queue
用两个只支持基本操作的堆可以实现删除任意元素。

双堆

这个是ZSY讲课的时候提到的一个技巧

假如我们要删除堆中的某个指定元素,可以通过"双堆"这个技巧来实现

大概地说, 开两个堆,一个插入,一个删除,取最大值时比较两个堆堆顶,若相同则同时弹出

也就是说,我们拿另一个堆记我每次删了哪个元素.

具体代码参加下面:

CSP2019集训总结

例题:[模板]堆 合并果子

ST表

f[i][j] 表示从 i 位置出发连续 2^j 长度的某些信息.

预处理时间复杂度是O(nlog_2n) , 询问是 O(1)

例题:[模板]ST表 超级钢琴 CF1142B Lynyrd Skynyrd

树状数组

树状数组 c_i 维护原数组 [i − lowbit(i) + 1, i] 内的信息,其中 lowbit(x) 表示 x 在二进制
下的最低位位值。
支持 O(log n) 单点修改,维护前缀信息。
注意到树状数组只能维护前缀信息,因此不可减(如求最小值)的区间信息是无法使用
树状数组维护的。

常见技巧

树状数组上二分

值域树状数组支持 O(log n) 二分求第 k 大,只需要按二进制位从高到低依次确定即可。

区间加区间求和

设原数组第i位的值为a_i, 记查分数组为d_i = a_i - a_{i - 1}

则有:a_x = \sum_{i=1}^{x} d_i

所以有:\sum_{i =1}^{x} a_i = \sum_{i =1}^{x} \sum_{j =1}^{i} d_j = \sum_{i=1}^{x} (x - i + 1)d_i

于是得到了: \sum_{i =1}^{x} a_i = (x + 1) \sum_{i = 1} ^ {x} d_i - \sum_{i = 1}^{x} d_i * i

所以开两个树状数组分别维护:\sum d_j\sum d_j * j

例题:【模板】树状数组 1 【模板】树状数组 2 [SDOI2009]HH的项链 逆序对

线段树

二叉树的每一个节点表示一个区间。根节点表示区间[1,n], 若一个节点表示的区间[l,r] 满足l ,令 mid = \lfloor \frac{l+r}{2} \rfloor ,则其左右儿子分别为 [l,mid][mid+1,r]

这样任意一个区间[l,r] ⊆ [1,n] 均可拆分成线段树上 O(logn) 和节点表示的区间

一般来讲需要维护的信息会满足结合律,这样在区间修改的时候可以使用懒标记维护。

例题:[JSOI2008]最大数 【模板】线段树 1 【模板】线段树 2 [AHOI2009]维护序列

树链剖分

树剖是通过轻重边剖分将树分割成多条链,然后利用数据结构来维护这些链(本质上是一种优化暴力)

详解可以看这一篇:树剖详解

例题: 【模板】树链剖分 [NOI2015]软件包管理器 [ZJOI2008]树的统计 [HAOI2015]树上操作 [国家集训队]旅游

[BJOI2018]求和

图论

最小生成树

在图上找到一棵树使得任意两个点都联通

常用的算法有Kruskal和Prim算法,两者各有优势,Kruskal是对边权排序,用并查集判断连通性.

Prim 算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始,不断加点(而不是 Kruskal 算法的加边)。

例题:[HAOI2006]聪明的猴子 「SCOI2005」繁忙的都市

最短路算法

单源最短路

最常用的有两种算法,一种是能够处理负边权的SPFA算法(Bellman-Ford算法的队列优化),而另一种无法处理负边权但高效的算法是Dijkstra堆优化算法.

SPFA算法容易被菊花图等特殊图卡死,但是一般情况跑的很快.在没有负权边时最好使用 Dijkstra 算法

例题:【模板】单源最短路径(弱化版) (SPFA) 【模板】单源最短路径(标准版) (Dijkstra堆优化)

[USACO06NOV]路障Roadblocks

多源最短路

Floyd算法,一种基于DP思想的最短路算法,时间复杂度 O(n^3)

这个算法也可以处理传递闭包问题.

分层图最短路

分层图最短路,如:有k次零代价通过一条路径,求总的最小花费。

相当于把每个结点拆分成了k+1 个结点,每个新结点代表使用不同多次免费通行后到达的原图结点。换句话说,就是每个结点u_i 表示使用i次免费通行权限后到达u结点。

例题:[BJWC2012]冻结 [JLOI2011]飞行路线

LCA

在线的算法是倍增算法,离线的可以用Tarjan处理

例题:SP3978 DISQUERY - Distance Query 货车运输 【模板】最近公共祖先(LCA)

连通性相关

有向图的强连通分量(缩点)

对于一个环我们可以用Tarjan算法缩成一个点

Tarjan算法详解

例题:[USACO5.3]校园网Network of Schools [HAOI2006]受欢迎的牛|【模板】强连通分量 消息扩散

正则表达式 HXY烧情侣 采蘑菇 [国家集训队]稳定婚姻 CF894E Ralph and Mushrooms

题解

无向图的双连通分量

分为点双联通分量和边双联通分量,还有个点和桥

不详细讲解了

图论常见技巧

https://www.luogu.org/blog/chengni5673/tu-lun-di-xiao-ji-qiao-yi-ji-kuo-zhan

这一篇写的很好,推荐观看.


苟利国家生死以,岂因祸福避趋之.