19-大数据一班-杨文冠

分类

学习(23) 未归档(1) 练习(1) 题解(137)

/ 注册

TA的专栏 96篇文章 0人订阅

[kuangbin带我飞]专题十五数位DP

11篇文章 896人学习

[kuangbin带我飞]专题十四数论基础

2篇文章 652人学习

8篇文章 754人学习

动态规划入门

7篇文章 926人学习

1篇文章 673人学习

二分图匹配

2篇文章 658人学习

[kuangbin带我飞]专题七线段树

8篇文章 801人学习

3篇文章 750人学习

线段树进阶

3篇文章 663人学习

codeforces补题

32篇文章 882人学习

莫比乌斯反演

6篇文章 581人学习

网络流初步

4篇文章 767人学习

6篇文章 727人学习

2021杭电多校

3篇文章 791人学习

全部文章（共173篇）

BST树模板

一.Treap树左旋和右旋右旋：左旋：旋转代码，son[0]是左儿子，son[1]是右儿子 void rotate(Node * &o,int d){ //d=0,左旋转；d=1，右旋转 Node *k=o->son[d^1]...

Splay BST Treap

2020-05-28

1 757

动态规划

hdu 1024 题意：给你n个数，要你在这n个数中取m段数（每段无交集），使这m段之和最大。思路：状态表示取i段以j结尾时能取到的最大和，状态转移方程，表示第j个数单独成一段，表示第j个数不单独成一段。n、m比较大，明显要用滚动数组，就有，这时我们还要维护（注意一下位置就很好做到）一个一维数组p...

dp

2020-05-22

3 758

Tarjan算法练习

hdu 1827 Tarjan + 缩点题意：Wiskey知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到（通知的人最少花费也就会最小）。思路:缩点（缩点就是用强连通分量中的一个点代替其余的点）之后...

Tarjan

2020-05-20

2 686

有向图的连通性

SCC指的是强连通分量，求SCC有三种高效的算法，即，他们的复杂度都是,但Kosaraju要差一点。算法： hdu 1269 一个有向图，有n个点和m条边，判断整个图是否强连通，如果是输出，否则输出。手写一个栈，用的也行，我是用向前星存有向图。code: #include<bits/st...

Tarjan

2020-05-20

1 706

最短路练习

hdu 2433 好像是Dijkstra算法的变形，最短路生成树。题意：我老是看不懂题目说什么，N个城镇，M条边，每条边的距离都是1（当然两个城镇之间可能有多条边，也可能没有边），求城镇i到城镇j的最短路之和，即∑i=1n(∑j=1ndis[j])\sum_{i=1}^{n}{ (\sum_{j...

最短路生成树 Dijkstra SPFA dp状态压缩旅行商问题

2020-05-19

1 726

后缀数组练习

hdu 5769 题意：输入一个T，t组数据，每一组共两行，第一行是一个小写字母，第二行是仅由小写字母组成的字符串，问有多少种子串包含第一行的字符。比如的子串有。统计一个字符串有多少种子串也是后缀数组经典的应用。从文本串中提取子串可以分两步，先确定一个后缀，然后在后缀中确定前缀。比如1.确定后缀(...

后缀数组

2020-05-18

1 627

最短路

题意：n个点m条边，然后输入m条无向边和每条边的权值。问1 ~ n的最小路径。 Floyd思路：来源：传送门1.邻接矩阵g储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！,。2.遍历从到，作为中继点依次加入图中。每个点加入进行试探是否有路径长度被更...

Floyd SPFA Dijkstra 优先队列

2020-05-14

2 739

搜索

BFS： 1。双向广搜 hdu 1401 题意：一个8 x 8的棋盘，上面有4颗棋子，棋子可以上下左右移动。给定一个初始状态和一个目标状态，问能否在8步之内到达。棋子移动有两种方式：1.将一个棋子移动到一个空的相邻格子中。2.将一个棋子跳过一个相邻的棋子到一个空的格子中去。思路：1.从初始状态开...

BFS

2020-05-14

2 577

卡特兰数

hdu 5184 题目大意：一个n，然后一串括号，括号数量大于0小于等于n，问你在给出了前个括号的情况下，长度为n的规则括号序列有多少种。卡特兰数一眼题-----钟涛大佬。题目的输入不一定保证是规则括号序列，所以如果n是奇数或者存在右括号的数量多于左括号的数量，或者左括号的数量大于n的一半是一...

卡特兰数逆元

2020-05-13

4 559

最小生成树

图的两个基本元素是点和边，与此对应，有两种方法可以构造最小生成树T。这两种算法都基于贪心算法，因为MST问题满足贪心算法的“最优性原理”，即全局最优包含局部最优。prim算法的原理是“最近的邻居一定在MST”上，kruskal算法的原理是“最短的边一定在MST上”。第一次出现kruskal算法或pr...

最小生成树并查集 kruskal算法贪心 prim算法离线算法最大生成树次小生成树

2020-04-29

4 1146