ACM算法竞赛——模板-腾讯云开发者社区

开发者社区

文档建议反馈控制台

腾讯云架构师技术同盟

文章/答案/技术大牛

发布

ACM算法竞赛——模板

专栏成员

37

文章

13918

阅读量

12

订阅数

ACM/蓝桥杯基础算法篇——二分

腾讯云测试服务文件存储 wordpress 云数据库 postgresql 云数据库 MongoDB

分析：先找最左边的x，check函数为要找的整数区间，在x的右边，所以是qmid >= x, x在mid的左边，所以x所在区间为l, mid。再找最右边的x，check函数为要找的整数区间，在x的左边，所以是qmid <= x, x在mid的右边，所以x所在区间为mid, r。

战士小小白

2022-07-11

3290

ACM/蓝桥杯动态规划篇——最长上升子序列模型（一）习题精讲

腾讯云测试服务文件存储 wordpress 云数据库 MongoDB 云数据库 postgresql

分析：此题为最长上升子序列模型的变形，通过分析可以发现其实就是正向求一边最长上升子序列，反向求一便最长上升子序列。再进一步就是从正向开始求一边最长上升子序列和最长下降子序列。

战士小小白

2022-07-08

4200

算法竞赛动态规划篇——数字三角形模型

腾讯云测试服务文件存储 wordpress 云数据库 MongoDB 云数据库 postgresql

分析：本题是一道非常经典的dp问题，数字三角形问题可以从上往下走来寻找最大路径，也可以从下往上走来寻找最大路径，我们可以发现从上往下走我们要分析每个数是怎么走到这里的，比如0这个数字，只能从左边走过来，右边走不过来，这样我们就多了许多特判的问题，增加了代码的复杂性。我们再看从下往上走的情况，再看0这个数字，它可以走到他下面的任何两个4，这就省略了边界的问题，所以这道题目采用从下到上的方式最为简单，事实上，这也是这道题目的最优解，同学们做题目做多了自然也就掌握了。

战士小小白

2022-07-08

3150

ACM算法竞赛——线性筛（模板）

线性筛时间复杂度O(n) 埃氏筛时间复杂度O(nloglogn)埃氏筛会多次筛除一个元素，线性筛一个数只会被最小的质因数筛除线性筛是最强的判断质数的方法，模板会在多cint primes[N], cnt; // primes[]存储所有素数bool st[N]; // st[x]存储x是否被筛掉void get_primes(int n){ for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++

战士小小白

2022-07-02

2300

数据库系统概论第一章简答题-期末考得怎么样？

云数据库 MongoDB

数据：描述事物的符号记录称为数据。数据的种类有文字、图形、图象、声音、正文等等。数据与其语义是不可分的。

战士小小白

2022-07-02

2610

ACM算法竞赛——埃氏筛（模板）

腾讯微信算法大赛

求1~n中质数的个数 void get_primes(int n) { for(int i = 2; i <= n; i ++) { if(!st[i]) { primes[cnt ++] = n; for(int j = i + i; j <= n; j += i) st[j] = true; } } }

战士小小白

2022-05-18

2330

ACM算法竞赛——试除法判断质数（模板）

腾讯微信算法大赛

最简单的判断质数的方法 bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) return false; return true; }

战士小小白

2022-05-18

5280

ACM算法竞赛——匈牙利算法（模板）

腾讯微信算法大赛

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。1955年，库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Kőnig)的一个定理构造了这个解法，故称为匈牙利法。（百度百科）匈牙利算法用于求二分图的最大匹配问题时间复杂度：O(mn),实际运行时间一般小于O(mn) int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只

战士小小白

2022-05-18

3600

ACM算法竞赛——染色法判别二分图（模板）

腾讯微信算法大赛

时间复杂度：O(m+n) int n; // n表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色 // 参数：u表示当前节点，c表示当前点的颜色 bool dfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int

战士小小白

2022-05-18

2740

ACM算法竞赛——Kruskal算法（模板）

腾讯微信算法大赛

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。（百度百科） int n, m; // n是点数，m是边数 int p[N]; // 并查集的父节点数组 struct Edge // 存储边 { int a, b, w; bool operator< (const Edge &W)const { return w < W.

战士小小白

2022-05-18

4030

ACM算法竞赛——朴素版prim算法（模板）

腾讯微信算法大赛

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚

战士小小白

2022-05-18

4370

ACM算法竞赛——floyd算法（模板）

腾讯微信算法大赛

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。（百度百科） Floyd算法用于求多源汇最短路问题，通俗来讲就是求图中任意两点间的最短距离时间复杂度: O(n^3) 初始化： for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ )

战士小小白

2022-05-18

3090

ACM算法竞赛——spfa 算法（模板）

SPFA 算法是 Bellman-Ford算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。（百度百科）这也是为什么在算法竞赛中我们很少使用bellman-ford算法的原因 SPFA 一般：O(m) 线性最坏:O（nm） int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N];

战士小小白

2022-05-18

4370

ACM算法竞赛——Bellman-Ford算法（模板）

腾讯微信算法大赛

bellman-ford算法一般在竞赛中用不到，因为它的时间复杂度是严格的O（VE）,存在负权边的单源最短路问题常用SPFA算法，但如果给我难题给出要求经过的边数小于等于k，就必须用bellman-ford算法。

战士小小白

2022-05-18

5881

ACM算法竞赛——堆优化版dijkstra（模板）

腾讯微信算法大赛

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。(百度百科) 堆优化版dijkstra算法时间复杂度：O(mlogn) 适用范围：稀疏图 typedef pair<int, int> PII; int n; // 点的数量 int h[

战士小小白

2022-05-18

5150

ACM算法竞赛——朴素dijkstra算法（模板）

腾讯微信算法大赛

int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1;

战士小小白

2022-05-16

4520

ACM算法竞赛——最短路知识结构总结

············1.1.1朴素dijkstra算法 O(n^2) 适合稠密图

战士小小白

2022-05-16

5280

ACM算法竞赛——拓扑排序（模板）

腾讯微信算法大赛

bool topsort() { int hh = 0, tt = -1; // d[i] 存储点i的入度 for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) {

战士小小白

2022-05-16

2770

ACM算法竞赛——树与图的宽度优先遍历bfs（模板）

腾讯微信算法大赛

queue<int> q; st[1] = true; // 表示1号点已经被遍历过 q.push(1); while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; // 表示点j已经被遍历过

战士小小白

2022-05-16

3840

ACM算法竞赛——树与图的深度优先遍历dfs（模板）

腾讯微信算法大赛

int dfs(int u) { st[u] = true; // st[u] 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } }

战士小小白

2022-05-16

4860

点击加载更多

社区活动

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·干货材料·成员作品最新动态