xjsc01

# 算法竞赛进...

# ACM进阶训练（进阶）(3) # CodeForce(3) # NOJ题解(11) # 堆栈队列单调栈(23) # 数据结构的实现(4) # 数据结构课后思考题(5) ACM(1) c++(1) 题解(3)

/ 注册

全部文章 / # 算法竞赛进阶指南（ACM培训）（共30篇）

算法竞赛进阶指南 0x53 区间DP

总论线性DP：从初态开始，沿着阶段的扩张，向某一个方向扩张，知道求出答案。区间DP是一种特殊的线性DP，同时也与线段树等树形结构具备相同的特征。阶段：区间的长度（一个转态要从比他小的区间并且包含于他的区间递推过来）转态：左端点，右端点。 <mark>注意：先是阶段，然后...

2022-10-06

0 0

算法竞赛进阶指南 0x54 树形DP

总论树状DP就是以子树大小节点的深度为阶段。当一个节点的最优解仅仅和他的儿子有关系，那么就可以。 AcWing\285. 没有上司的舞会 Ural 大学有 N 名职员，编号为 1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快...

2022-10-06

0 0

算法竞赛进阶指南 0x57 倍增优化DP

文章目录总论 [AcWing\293. 开车旅行](https://www.acwing.com/problem/content/295/) part1 确定`ga[], gb[]` part2 确定`f[]` ...

2022-10-06

0 0

算法竞赛进阶指南 0x58 数据结构优化DP

文章目录 [AcWing\295. 清理班次](https://www.acwing.com/problem/content/description/297/) [AcWing\296. 清理班次2](https://www.acwing.com/problem/...

2022-10-06

0 0

算法竞赛进阶指南 0x65 负环与差分约数

这里与最短路密切相关可以使用spfa，利用spfa的原理（cnt数组），如果发现一个点是通过了超过n-1条边更新而来，那么就说明存在负环 AcWing361. 观光奶牛给定一张 L 个点、P 条边的有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。求图中的一个环，使“...

2022-10-06

0 0

算法竞赛进阶指南 0x67 Tarjan 算法与有向图连通性

相关概念有向图 G = ( V , E ) G = (V, E) G=(V,E)中，如果存在一个点 r r r，使得从 r r r出发，那么就可以到达所有的节点，那么称G为一个流图，记作 ( G , r ) (G, r) (G,r) 有向图的强连通分量对于强连通子图的等价条件就是具...

2022-10-06

0 0

算法竞赛进阶指南 0x68 二分图的匹配

相关概念对于一个无向图，节点的数N>=2，如果节点可以划分为两个非空集合A,B 满足 A与B的交集为空同一集合中的点没有边相连 A，B分别叫左部，右部二分图的判定方法染色判定法。由二分图的定义可以知道，如果i位于A中，那么与i连接的边一定在B中，这样遍历...

2022-10-06

0 0

算法竞赛进阶指南 0x21 树与图的遍历

这算是总结性的文章，比较简略，不太适合初学者文章目录深度优先搜索树的DFS序树的深度树的子树的大小树的重心连通块的遍历图以及树的广...

2022-10-06

0 0

算法竞赛进阶指南 0x22 深度优先搜索

AcWing165. 小猫爬山翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。翰翰和达达只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C...

2022-10-06

0 0

算法竞赛进阶指南 0x24 迭代加深

文章目录 [AcWing170. 加成序列](https://www.acwing.com/problem/content/172/) [AcWing171. 送礼物](https://www.acwing.com/problem/content/173/) ...

2022-10-06

1 0