问题描述 : 目的：使用C++模板设计单链表的抽象数据类型（ADT）。并在此基础上，使用单链表ADT的基本操作，设计并实现单链表的简单算法设计。 内容： （1）请使用模板设计单链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的ADT原型文件。） （2）ADT的简单应用：使用该ADT设计并实现单链表应用场合的...
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。 给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。 由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。 输入格式 第一行包含两个整数n和m。 接下来m行，每行包...
快速选择排序 快排的简单回顾 这是一种基于快速排序的应用算法，我们先来回顾一下快速排序快速排序模板 快排有三个步骤 0、选择一个支点； 1、根据指点将整个数组划分为两部分，第一部分为小于等于支点x的数，另一部分为大于等于支点x的数； 2、递归调用函数，对左右两边进行排序； 快速选择算法 快速选择算法是基于快排的，快排第三步是对左右两个区间同时进行递归，而快速选择算法可以根据要查找的数据对区间进行一种缩小； #inc...
稀疏图和稠密图的评判标准 规定点数为n，边数为m 稠密图: \(m ~ n^2\), m和\(n^2\)对标 稀疏图: \(m ~ n\)， m和n对标
题目 https://www.luogu.com.cn/problem/P4718 思路 真的是阴间卡常模板题 blog 代码 #include<bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long using namespace std; int T; ll ans,n; inline ll mul(ll x,ll y,ll p) {ll yjy=(ld)x/p*y;ll aii=(ull)x*y-(ull)yjy*p;if(aii<0) aii+=p; if(aii>=p) aii-=p;return aii; } inline ll power(ll x,ll t,ll mod) {ll b=1;while(t){if(t&1)...
概述模板出自kuangbin的博客 典型应用:给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。 (1) 头文件1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 int Next[N]; 5 char S[N],T[N]; // S:主串 T:模式串 6 int slen,tlen;(2) getNext()函数 1 void getNext()2 {3 int j,k;4 j = 0; k = -1; Next[0] = -1;5 while(j < tlen)6 {7 ...
说明：该文章是学习浙大MOOC数据结构后对图这章涉及的一些代码的copy。目的是为了以后写代码时能直接找到现成的模板，减少工作量。 1.图的表示 1.1邻接矩阵表示 #define MaxVertexNum 100 /* 最大顶点数设为100 */ #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/ typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ typedef int WeightType; /* 边的权值设为整型 */ typedef cha...
目录目录 简介 实现数据结构定义 在数组前添加一个元素 判断 分堆 合并 快速排序的实现总结简介 上一篇使用C++模板模板实现了一个选择排序。这一次，更进一步的，实现了一个快速排序算法。关于快速排序的可以看这一篇文章快速排序 实现 和上一次一样，我把快速排序算法分为几个小的步骤，分别实现，然后联合在一起，实现算法。 数据结构定义 和之前类似，不过多定义了一个head_type，同时对一些类型进行了改名。 // 数据结构定义 t...
模板题：https://www.acwing.com/problem/content/833/ 题意：给两个字符串长度及序列，求第一个串在第二个串中出现的位置3 aba5 ababa求next数组： for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j; }kmp匹配过程 for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==m) j=ne[j]; //避免下次的p[j+1]越界 }代码： #include<iostream> #include<cstdio> u...
问题描述 :目的：使用C++模板设计单链表的抽象数据类型（ADT）。并在此基础上，使用单链表ADT的基本操作，设计并实现单链表的简单算法设计。 内容：（1）请使用模板设计单链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的ADT原型文件。） （2）ADT的简单应用：使用该ADT设计并实现单链表应用场合的一...
KM算法计算带权二分图最优匹配 时间复杂度\(O(n^3)\) 模板题：hdu2255 奔小康赚大钱 const int maxn=310; const int inf=0x3f3f3f3f;int n; int g[maxn][maxn],ex1[maxn],ex2[maxn],match[maxn],slack[maxn]; bool vis1[maxn],vis2[maxn];bool dfs(int x){vis1[x]=true;for(int y=0;y<n;y++) {if(vis2[y]) continue; int gap=ex1[x]+ex2[y]-g[x][y];if(gap==0){ vis2[y]=true;if(match[y]==-1 || dfs(match[y])){ match[y]=...
看进阶指南的时候看到的算法,正好最近没啥事干来学一下 大致题意 给一个长度为\(n\)字符串\(S\),求\(S\)中的最长回文字串 \(n≤1.110^7\)分析 算法一 暴力 枚举每个点能扩散到的最大长度 时间复杂度\(O(n^2)\)算法二 \(hash+\)二分 建立出\(S\)的前后缀\(hash\)值,然后二分答案,找到最大扩展长度 时间复杂度\(O(nlogn)\)算法三 \(manacher\)麻辣串算法 算法流程 1.在每两个字符间插入一个额外字符,以去掉偶回文串的情况2.定义\(r_i...
The Cow Prom POJ - 3180 题意： 奶牛圆舞：N头牛，M条有向绳子，能组成几个歌舞团（团内奶牛数 n >= 2)？要求顺时针逆时针都能带动舞团内所有牛。 分析： 所谓能带动，就是舞团构成一个强连通分量，就是赤裸裸的SCC。 代码实现：很好的一道题，有利于理解 korasaju 算法 #include<iostream> #include<queue> #include<vector> using namespace std; #define ms(a,b) memset(a,b,sizeof a) const int maxn = 1e5 + 10;int V; ...
啊这，为什么一道看上去完全跟图论无关的题有图论标签。正题： 差分约束系统&&转化： 顾名思义，差分约束系统就是给你很多个形如\(x_1-x_2\leqslant c_k\)的不等式（其中c为常数），让你求出一组解或者判断无解。看上面的式子，把它变成这样：\(x_1\leqslant x_2+c_k\)，是不是很熟悉，长得就跟最短路里面的三角形不等式一模一样，这样一来，我们就可以把\(x_2\)向\(x_1\)（注意，是2连向1，因为最短路中是\(\geqq\)，这里是$\leqs...
初始化：//n为元数的个数 int bitn=(int)(log(n)/log(2)) for (int i=0; i<n; ++i)f[i][0]=input[i]; for (int j=1; j<bitn; ++j)for (int i=0; i<n; ++i){if (i+(1<<(j-1))>=n) break;f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);} 查询 int query(int s,int e) //查询区间[s,e]的最值{int k=(int)((log(e-s+1.0)/log(2.0)));return max(f[s][k],f[e-(1<<k)+1][k]);}