首页 > 编程语言 >算法设计与分析-算法模板(不定期更新)

算法设计与分析-算法模板(不定期更新)

时间：2024-01-17 19:25:48浏览次数：26  
标签：const int 不定期 long 算法 ms return include 模板

算法大纲

基础算法：模拟，分治，递归，排序，概率，堆

进阶算法：DP，贪心，图论，计算几何，FFT，字符串

22级期末考试题型：

诚信承诺题、选择题5道、归并思想(175/184)、排序的变形题(155/169)、贪心(170/185)、线性动态规划(77/136)、区间动态规划（33/61)、最短路变形(3/25)、多源多汇最大流(12/23)，之后还有字符串(0/0)、计算几何(0/7)、FFT(1/7)、数论(4/8)。

一、头文件和STL

#include<bits/stdc++.h>//万能头
#include<cstdio>//使用scanf和printf的头文件
#include<cstring>//使用C风格字符串函数的头文件
#include<algorithm>//使用算法库的头文件，max,min,swap,sort等
#include<iostream>//使用cin,cout的头文件
#include<string>//使用string时的头文件
#include<vector>//使用vector时的头文件
#include<stack>//使用stack时的头文件
#include<cstdlib>//使用memset函数的头文件
#include<cmath>//数学函数的头文件
#include<set>//使用set的头文件
#include<list>//使用list的头文件
#include<deque>//使用deque的头文件
#include<map>//使用map的头文件
using namespace std;
ios::sync_with_stdio(false);
cin.tie(nullptr);//加速专用,不要再用printf

二、基础算法(模拟,分治,递归,排序,概率)

快速幂

long long fastPower(long long base, long long power,long long mod) {//base为底数，power为指数,结果对mod取余
	long long result = 1;
	while (power>0) {
		if ((power&1)==1) {//指数为奇数
			power--;//减1变偶数
			result = result * base % mod;//把分离出来的底数的一次方收集好
		} 
		power=power>>1;
		base = base * base % mod;
	}
	return result;
}

矩阵乘法快速幂

const int mod =1e9+7;
const int ms = 130;
long long A[ms][ms],res[ms][ms];
long long temp[ms][ms];
void MXMP(long long a[][ms],long long b[][ms],int n){
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
			temp[i][j] = 0;
	
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
			for(int k = 1;k<=n;k++)
				temp[i][j] = (temp[i][j] + ((a[i][k]%mod)*(b[k][j]%mod))%mod)%mod;
	
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
			a[i][j] = temp[i][j];
}
void fastPower(long long A[][ms],int n,int x){//快速幂
	memset(res,0,sizeof(res));
	for(int i=1;i<=n;i++)  
		res[i][i] = 1;//初始化为单位矩阵
	while(x){
		if((x&1)==1)
			MXMP(res,A,n);
		
		MXMP(A,A,n);
		x >>= 1;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			A[i][j] = res[i][j];
}
int t,n;
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%lld",&A[i][j]);
	
		fastPower(A,n,n);//快速幂
		for(int i = 1;i<=n;i++){
			for(int j = 1;j<=n;j++){
				cout<<A[i][j]<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}

gcd和lcm

__gcd(a,b)和a*b/__gcd(a,b)

第k小的数

void quickSort(int left,int right){//[left,right]的闭区间,找第k小的数
	if(left>=right)
		return;
	int r=rand()%(right-left+1)+left;//随机分界元素位置
	swap(ar[r],ar[left]);//分界元素移到最左边
	int last=left;
	for(int i=left+1;i<=right;i++){
		if(ar[i]<ar[left]){
			last++;
			swap(ar[i],ar[last]);
		}
	}
	swap(ar[left],ar[last]);//移回分解元素，此时左边的小，右边的大
	if(last>k)
		quickSort(left,last);
	else if(last<k)
		quickSort(last+1,right);
	else 
		printf("%d",ar[k]);
}

逆序对

long long merge_count(int left,int mid,int right){
	int i=left,j=mid+1,k=left;
	long long S=0;
	while(i<=mid&&j<=right){
		if(ar[i]<=ar[j])
			tmp[k++]=ar[i++];
		else{
			tmp[k++]=ar[j++];
			S+=(mid-i+1);
		}
	}
	while(i<=mid)
		tmp[k++]=ar[i++];
	while(j<=right)
		tmp[k++]=ar[j++];	
	for(i=left;i<=right;i++)
		ar[i]=tmp[i];
	return S;
}
long long solve(int left,int right){
	if(left==right)
		return 0;
	else{
		long long mid,S1,S2,S3;
		mid=(left+right)/2;
		S1=solve(left,mid);
		S2=solve(mid+1,right);
		S3=merge_count(left,mid,right);
		return (S1+S2+S3);
	}
}

高精度加法

int ar[ms],br[ms],cr[ms];
int la,lb,lc;
void add(){
	for(int i=0;i<lc;i++){
		cr[i]+=ar[i]+br[i];
		cr[i+1]+=cr[i]/10;
		cr[i]%=10;
	}
	if(cr[lc])//处理最高位
		lc++;
}
int main(){
	string a,b;
	cin>>a>>b;
	la=a.size(),lb=b.size(),lc=max(la,lb);
	for(int i=la-1;~i;i--)
		ar[la-1-i]=a[i]-'0';
	for(int i=lb-1;~i;i--)
		br[lb-1-i]=b[i]-'0';
	add();
	for(int i=lc-1;~i;i--)
		printf("%d",cr[i]);
	return 0;
}

高精度减法

bool cmp(){//若ar<br,则交换，输出负号
	if(la!=lb)
		return la>lb;
	for(int i=la-1;~i;i--)
		if(ar[i]!=br[i])
			return ar[i]>br[i];
	return true;
}
void sub(){
	for(int i=0;i<lc;i++){
		if(ar[i]<br[i]){//借位
			ar[i+1]--;
			ar[i]+=10;
		}
		cr[i]=ar[i]-br[i];
	}
	while(lc&&cr[lc]==0)//处理前导0
		lc--;
}
int main(){
	string a,b;
	cin>>a>>b;
	la=a.size(),lb=b.size(),lc=max(la,lb);
	for(int i=la-1;~i;i--)
		ar[la-1-i]=a[i]-'0';
	for(int i=lb-1;~i;i--)
		br[lb-1-i]=b[i]-'0';
	if(!cmp())
		swap(ar,br),cout<<"-";
	sub();
	for(int i=lc;~i;i--)
		printf("%d",cr[i]);
	return 0;
}

三、动态规划

1.背包问题

(1)0-1背包(每种物品只有1件)

//普通二维数组
const int ms=1003;
int s[ms],v[ms];//每件商品容量和价值
int DP[ms][ms];//DP[i][j]前i件商品放入容量为j的背包的最大价值
int T,M;//背包容量与商品数目
int rec[ms][ms];
void solve(){
	for(int i=1;i<=M;i++){
		for(int j=1;j<=T;j++){
			if(j>=s[i]&&DP[i-1][j-s[i]]+v[i]>DP[i-1][j]){
				DP[i][j]=DP[i-1][j-s[i]]+v[i];
				rec[i][j]=1;//选了第i个商品
			}
			else{
				DP[i][j]=DP[i-1][j];
				rec[i][j]=0;
			}
		}
	}
	//输出具体装了哪些商品
	int j=T;
	for(int i=M;i>=1;i--){
		if(rec[i][j]==1){
			printf("%d",i);
			j=j-s[i];
	    }
	}
	cout<<DP[M][T];//背包最大价值
}

//滚动数组空间优化，注意逆序循环和j的范围
void solve(){
	for(int i=1;i<=M;i++){//物品i
		for(int j=T;j>=s[i];j--){//容量j
			DP[j]=max(DP[j],DP[j-s[i]]+v[i]);
		}
	}
	printf("%d",DP[T]);
}
//如果要求恰好装满背包，那么在初始化时除了DP[0]为0,其它DP[1..V]均设为-∞，这样就可以保证最终得到的DP[N]是一种恰好装满背包的最优解,当然如果DP[N]<0则无解
//如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将DP[0..V]全部设为0。

2.最长上升子序列优化

int find(int br[],int x,int len){//二分查找第一个≥x的位置
	int left=1,right=len;
	while(left<=right){
		int mid=(left+right)/2;
		if(x>br[mid]) left=mid+1;
		else right=mid-1;
	}
	return left;
}
int main(){
	int n,i,j;
	scanf("%d",&n);
	int ar[n],br[n];
	for(i=1;i<=n;i++)
		scanf("%d",&ar[i]);
	int len=1;//上升子序列的长度
	br[1]=ar[1];
	for(i=2;i<=n;i++){
		if(ar[i]>br[len])
			br[++len]=ar[i];//大于则添加到br末尾
		else{
			j=find(br,ar[i],len);
			br[j]=ar[i];//小于等于则替换
		}
	}
	printf("%d",len);//输出br长度即为答案
	return 0;
}

3.最大子数组

void solve(){
	for(int i=1;i<=n;i++){
		DP[i]=max(DP[i-1]+ar[i],ar[i]);
		ans=max(ans,DP[i]);
	}
}

4.最小编辑距离

char s1[2005],s2[2005],ar[2005],br[2005];
int Rec[2005][2005];//跟踪数组，0表示左，1表示上，2表示左上
int D[2005][2005];//递推数组
int min(int a,int b,int c){//求三个数的最小值
	int x=-1;
	x=(a<=b)?a:b;
	x=(c<=x)?c:x;
	return x;
}
int Minimum_Edit_Distance(char ar[],char br[],int len_a,int len_b){
	for(int i=1;i<=len_a;i++){
		for(int j=1;j<=len_b;j++){
			int c=0;
			if(ar[i]!=br[j])
				c=1;
			int Replace=D[i-1][j-1]+c;//替换对应的是左上，2
			int Delete=D[i-1][j]+1;//删除对应上，1
			int Insert=D[i][j-1]+1;//添加对应左,0
			
			if(Replace==min(Replace,Delete,Insert)){
				D[i][j]=D[i-1][j-1]+c;
				Rec[i][j]=2;
			}
			else if(Delete==min(Replace,Delete,Insert)){
				D[i][j]=D[i-1][j]+1;
				Rec[i][j]=1;
			}
			else if(Insert==min(Replace,Delete,Insert)){
				D[i][j]=D[i][j-1]+1;
				Rec[i][j]=0;
			}
		}
	}
	return D[len_a][len_b];
}
int main(){
	scanf("%s %s",s1,s2);
	int len_a=strlen(s1),len_b=strlen(s2);
	for(int i=1;i<=len_a;i++)
		ar[i]=s1[i-1];
	for(int j=1;j<=len_b;j++)
		br[j]=s2[j-1];	//一定要注意DP问题大多都要从1开始，不是0，因此这一步是必要的
	
	for(int i=0;i<=len_a;i++){
		D[i][0]=i;
		Rec[i][0]=1;
	}
	for(int j=0;j<=len_b;j++){
		D[0][j]=j;
		Rec[0][j]=0;
	}//初始化D数组和Rec数组
	printf("%d",Minimum_Edit_Distance(ar,br,len_a,len_b));
}

5.最长公共子串

int DP[ms][ms];//以ar[i],br[j]结尾的最大子串的长度
int l_max=-1,p_max=0;//最长子串长度，字串末尾
void print_LCS(){//打印结果
	for(int i=p_max-l_max+1;i<=p_max;i++)
		cout<<ar[i];
}
void solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ar[i]!=br[j])//递推公式为，ar，br不等时，DP=0
				DP[i][j]=0;
			else{
				DP[i][j]=DP[i-1][j-1]+1;//ar，br相等时，DP[i]][j]=DP[i-1][j-1]+1
				if(DP[i][j]>l_max){
					l_max=DP[i][j];
					p_max=i;
				}
			}
		}
	}
	print_LCS();
}

6.最长公共子序列

int C[ms][ms];//动态规划数组,C[m][n]为最长公共子序列长度
int Rec[ms][ms];//跟踪数组，记左上为2，左为1，上为0
void print_LCS(int i,int j){
	if(i==0||j==0)
		return;
	if(Rec[i][j]==2){
		print_LCS(i-1,j-1);
		cout<<ar[i];
	}
	else if(Rec[i][j]==1)
		print_LCS(i,j-1);
	else print_LCS(i-1,j);
}
void solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){//递推公式
			if(ar[i]==br[j]){
				C[i][j]=C[i-1][j-1]+1;
				Rec[i][j]=2;
			}//末尾相等的时候，C[i][j]=C[i-1][j-1]+1,Rec取左上
			else if(C[i-1][j]>=C[i][j-1]){
				C[i][j]=C[i-1][j];
				Rec[i][j]=0;
			}
			else{
				C[i][j]=C[i][j-1];
				Rec[i][j]=1;
			}//不相等的时候，C[i][j]=max{C[i-1][j],C[i][j-1]},Rec取上或左
		}
	}
	print_LCS(n,m);
}

四、贪心

活动选择问题：选结束最早的

五、图论(注意是有向图还是无向图)

1.最短路相关

（1）dijkstra单源最短路，边权不能为负

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int ms=5e5+2;//点数
struct edge{
	int ed;//指向的顶点
	int wei;//权值
	bool operator <(const edge &x)const{
		return x.wei<wei;
	}
}temp;
vector<edge> g[ms];
priority_queue<edge> q;
int dist[ms],vis[ms];
int n,m,s,u,v,w;
void dijkstra(int start){
	dist[start]=0;
	q.push({start,0});
	while(!q.empty()){
		temp=q.top();
		q.pop();
		int st=temp.ed;//松弛起点
		if(!vis[st]){
			vis[st]=1;
			for(int i=0;i<g[st].size();i++){//松弛操作
				int ed=g[st][i].ed;//松弛终点
				if(dist[st]+g[st][i].wei<dist[ed]){
					dist[ed]=dist[st]+g[st][i].wei;
					if(!vis[ed]){
						temp.ed=ed,temp.wei=dist[ed];
						q.push(temp);
					}
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++){
		vis[i]=0;//vis数组初始化0
		dist[i]=1e18+2;
	}
	dijkstra(s);
	return 0;
}

（2）Floyd全源最短路

//注意初始化dist为无穷大，且dist[i][i]=0;如果重边，要选小的建边
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dist[i][k]+dist[k][j]<dist[i][j]){
					dist[i][j]=dist[i][k]+dist[k][j];
					//path[i][j]=k;	//记录插点
				}
			}
		}
	}
}
//void print(int i,int j){//递归输出路径
//	if(path[i][j]==0)
//		return;
//	int k=path[i][j];
//	print(i,k);
//	printf("%d ",k);
//	print(k,j);
//}

（3）Bellman-Ford判负环

#include <bits/stdc++.h>
using namespace std;
//Bellman-Ford算负权最短路，并能判断有无负环
const int ms=2e3+2;
const int inf=0x3f3f3f3f;
struct edge{
	int to;
	int wei;
};
vector<edge> G[ms]; 
int dist[ms];
int T,n,m,u,v,w;
bool Ford(int s){//从顶点s出发
	dist[s]=0;
	bool flag;
	for(int i=1;i<=n;i++){
		flag=false;
		for(int j=1;j<=n;j++){
			if(dist[j]==inf)
				continue;
			for(int k=0;k<G[j].size();k++){
				int toward=G[j][k].to;
				if(dist[j]+G[j][k].wei<dist[toward]){
					dist[toward]=dist[j]+G[j][k].wei;
					flag=true;
				}
			}
		}
		if(!flag)//没有可以松弛的边时就停止算法
			break;
	}
	return flag;//第n轮循环仍然可以松弛时说明s点可以抵达一个负环,返回true,否则返回false
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			cin>>u>>v>>w;
			G[u].push_back(edge{v,w});
			if(w>=0)
				G[v].push_back(edge{u,w});
		}
		for(int i=1;i<=n;i++)//距离初始化为无穷大
			dist[i]=inf;
		
		bool flag=Ford(1);
		if(flag)
			cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		for(int i=1;i<ms;i++)
			vector<edge>().swap(G[i]);
	}
	return 0;
}

2.最大流相关

(1)最大流Dinic模板

//如果是多组输入，记得清空e,head,并且重置tot=1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX=1e16;
const int N=5e3+2;
const int M=1e4+2;
struct edge{
	int ed;
	ll wei;
	int next;
}e[M<<1];
int tot=1,head[N];//tot边的编号,从2开始,便于异或找反向边
int n,m,u,v,s,t;//s和t:源点和汇点
ll w;
int depth[N],cur[N];
void add(int u,int v,ll w){
	tot++;
	e[tot].ed=v;
	e[tot].wei=w;
	e[tot].next=head[u];
	head[u]=tot;
}
bool bfs(){//在残量网络中构造分层图 
	for(int i=1;i<=n;i++)
		depth[i]=INT_MAX;
	queue<int> q;
	q.push(s);
	depth[s]=0;
	while(!q.empty()){
		int st=q.front();
		q.pop();
		cur[st]=head[st];
		for(int i=head[st];i;i=e[i].next){
			int ed=e[i].ed;
			if(depth[ed]==INT_MAX&&e[i].wei>0){
				depth[ed]=depth[st]+1;
				q.push(ed);
				if(ed==t)
					return true;
			}
		}	
	}
	return false;
}
ll dfs(int st,ll flow){
	if(st==t)
		return flow;
	ll sum=0;
	for(int i=cur[st];i;i=e[i].next){
		cur[st]=i;//当前弧优化
		int ed=e[i].ed;
		if(depth[ed]==depth[st]+1 && e[i].wei>0){
			ll tmp=dfs(ed,min(flow,e[i].wei));
			flow-=tmp;
			sum+=tmp;
			e[i].wei-=tmp;
			e[i^1].wei+=tmp;
			if(flow==0)//余量优化
				break;
		}
	}
	if(sum==0)//残枝优化
		depth[st]=INT_MAX;
	return sum;
}
ll dinic(){
	ll ans=0;
	while(bfs())
		ans+=dfs(s,MAX);
	return ans;
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,0);
	}
	cout<<dinic();
	return 0;
}

(2)最大二分图匹配

建立超级源点和超级汇点，超级源点指向左边的点，右边的点指向超级汇点，所有边的权值都赋值为1，(别忘了反向边建立权值是0)，然后用Dinic跑最大流即为答案

3.最小生成树kruskal，适合稀疏图

const int ms=2e5+2;//边数
struct edge{
	int u,v;
	ll w;
	bool operator <(const edge &t)const{
		return w<t.w;
	}
}e[ms];
int n,m,fa[ms],cnt;
ll ans;
int find(int x){
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void solve(){
	for(int i=1;i<=n;i++)//初始化并查集，把n个点放在独立的集合
		fa[i]=i;
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++){
		int x=find(e[i].u);
		int y=find(e[i].v);
		if(x!=y){
			fa[x]=y;
			ans+=e[i].w;
			cnt++;//最后如果cnt=n-1就有最小生成树
		}
	}
}
	for(int i=1;i<=m;i++)//输入
		scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);

4.Topo排序

vector<int> e[102];
queue<int> q;
int n;
int inDegree[102];//入度
void Topological_Sort_BFS(){
	for(int i=1;i<=n;i++)
		if(inDegree[i]==0)
			q.push(i);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		cout<<v<<" ";
		for(int i=0;i<e[v].size();i++){
			inDegree[e[v][i]]--;
			if(inDegree[e[v][i]]==0)
				q.push(e[v][i]);
		}
	}
}

六、计算几何

凸包

//Graham扫描算法
const int ms=1e5+2;
struct node{
	double x,y;
}point[ms],Stack[ms];
int n;
double check(node a,node b,node c){//计算叉积(b-a)X(c-a),大于0则线段ab在ac的顺时针方向
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dist(node a,node b){//两点间距离
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(node a,node b){
	double temp=check(point[1],a,b);
	if(temp>0) 
		return 1;
	if(temp==0&&dist(point[1],a)<dist(point[1],b))
		return 1;
	return 0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&point[i].x,&point[i].y);
		if(i!=1&&(point[i].y<point[1].y||(point[i].y==point[1].y&&point[i].x<point[1].x))){//先找到最低的y,y相同找x最小的
			swap(point[1].x,point[i].x);
			swap(point[1].y,point[i].y);
		}
	}
	sort(point+2,point+n+1,cmp);
	Stack[1]=point[1];
	int cnt=1;
	for(int i=2;i<=n;i++){
		while(cnt>1&&check(Stack[cnt-1],Stack[cnt],point[i])<=0)
			cnt--;
		cnt++;
		Stack[cnt]=point[i];
	}
	Stack[cnt+1]=point[1];
	double ans=0;
	for(int i=1;i<=cnt;i++)
		ans+=dist(Stack[i],Stack[i+1]);
	printf("%.2lf",ans);
	return 0;
}

最近点对

const int maxn=4e5+2;
int n;
struct Point{
	long long x,y;
}p[maxn],q[maxn];
bool cmp(const Point &a,const Point &b){
	return a.x<b.x;
}
long long dis(const Point &a,const Point &b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long divide(int l,int r){
	if(l==r) 
		return LONG_LONG_MAX;
	int mid=(l+r)/2;
	long long midx=p[mid].x;
	long long d=min(divide(l,mid),divide(mid+1,r));
	int p1=l,p2=mid+1,tot=0;
	while(p1<=mid||p2<=r){
		if(p1<=mid&&(p2>r||p[p1].y<p[p2].y))
			q[++tot]=p[p1++];
		else
			q[++tot]=p[p2++];
	}
	for(int i=1;i<=tot;i++)
		p[l+i-1]=q[i];
	
	tot=0;
	long long dd=d;
	d=sqrt(dd);
	for(int i=l;i<=r;i++){
		if(abs(p[i].x-midx)<=d) 
			q[++tot]=p[i];
	}
	for(int i=1;i<=tot;i++){
		for(int j=i-1;j>=1&&q[i].y-q[j].y<=d;j--){
			dd=min(dd,dis(q[i],q[j]));
			d=sqrt(dd);
		}
	}
	return dd;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&p[i].x,&p[i].y);
	sort(p+1,p+n+1,cmp);
	printf("%lld",divide(1,n));
	return 0;
}

七、FFT

1.迭代FFT

#include<bits/stdc++.h>
using namespace std;
const int ms=1e7+2;
const double PI=acos(-1);//arccos(1)=pai
int R[ms];
complex<double> a[ms],b[ms];//复数容器
void change(complex<double> A[],int n){
	for(int i=0;i<n;i++){
		R[i]=R[i/2]/2+(i%2)*(n/2);
	}
	for(int i=0;i<n;i++){
		if(i<R[i])//保证每对数只翻转一次
			swap(A[i],A[R[i]]);
	}
}
void FFT(complex<double> A[],int n,int op){//op=1为正变换,op=-1为逆变换
	change(A,n);
	for(int m=2;m<=n;m<<=1){//枚举块宽
		complex<double> w1({cos(2*PI/m),sin(2*PI/m)*op});
		for(int i=0;i<n;i+=m){//枚举块数
			complex<double> wk({1,0});
			for(int j=0;j<m/2;j++){//枚举半块
				complex<double> x=A[i+j],y=A[i+j+m/2]*wk;
				A[i+j]=x+y;
				A[i+j+m/2]=x-y;
				wk=wk*w1;
			}
		}
	}
}
int n,m;//一个n次多项式和一个m次多项式
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=0;i<=n;i++)
		cin>>a[i];
	for(int i=0;i<=m;i++)
		cin>>b[i];
	
	for(m+=n,n=1;n<=m;n*=2);//长度补成2的幂
	FFT(a,n,1),FFT(b,n,1);//正变换求点值
	for(int i=0;i<n;i++)//乘积
		a[i]=a[i]*b[i];
	FFT(a,n,-1);//逆变换求系数
	for(int i=0;i<=m;i++)
		cout<<(int)(a[i].real()/n+0.5)<<" ";
	return 0;
}

2.大数乘法

char s1[ms],s2[ms];
int main(){
	scanf("%s%s",s1,s2);
	int n=strlen(s1)-1,m=strlen(s2)-1;
	for(int i=0;i<=n;i++)
		a[i]=s1[n-i]-'0';
	for(int i=0;i<=m;i++)
		b[i]=s2[m-i]-'0';
	
	for(m+=n,n=1;n<=m;n*=2);//长度补成2的幂
	FFT(a,n,1),FFT(b,n,1);//正变换求点值
	for(int i=0;i<n;i++)//乘积
		a[i]=a[i]*b[i];
	FFT(a,n,-1);//逆变换求系数
	
	for(int i=0;i<n;i++){
		ans[i]+=(int)(a[i].real()/n+0.5);
		ans[i+1]+=ans[i]/10;
		ans[i]%=10;
	}
	while(n>=0&&!ans[n])
		n--;
	for(int i=n;i>=0;i--)
		printf("%d",ans[i]);
	return 0;
}

八、字符串

1.KMP

#include<bits/stdc++.h>
using namespace std;
const int ms=1e6+2;
char s1[ms],s2[ms];
int ne[ms];
int main(){
	scanf("%s",s1+1);//主串
	scanf("%s",s2+1);//模式串
	int m=strlen(s1+1);
	int n=strlen(s2+1);
	//求ne,ne[i]表示模式串P[1,i]中相等前后缀的最长长度
	ne[1]=0;
	for(int i=2,j=0;i<=n;i++){
		while(j && s2[i]!=s2[j+1])
			j=ne[j];
		if(s2[i]==s2[j+1])
			j++;
		ne[i]=j;
	}
	for(int i=1,j=0;i<=m;i++){
		while(j && s1[i]!=s2[j+1])
			j=ne[j];
		if(s1[i]==s2[j+1])
			j++;
		if(j==n){
			printf("%d\n",i-n+1);
			j=ne[j];	
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d ",ne[i]);	
	return 0;
}

2.hash

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int P=131;
const int ms=1e4+2;
//p[i]=P^i,h[i]=s[1~i]的hash值
ull p[ms],h[ms];
char s[ms];//从s[1]开始存储
int n;//字符串长度

//预处理hash函数的前缀和
void init(){
	p[0]=1,h[0]=0;
	for(int i=1;i<=n;i++){
		p[i]=p[i-1]*P;
		h[i]=h[i-1]*P+s[i];
	}
}
//计算s[l~r]的hash值
ull get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}
//判断两子串是否相同
bool substr(int l1,int r1,int l2,int r2){
	return get(l1,r1)==get(l2,r2);
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	return 0;
}

3.最长回文串

const int ms=3e7;
char ar[ms],s[ms];
int n,k,d[ms],ans;
void manacher(){//注:原串的最长回文串=新串的最大半径-1
	n=strlen(ar+1);
	k=0;
	s[0]='$',s[++k]='#';
	for(int i=1;i<=n;i++)
		s[++k]=ar[i],s[++k]='#';
	n=k;
	d[1]=1;
	for(int i=2,l,r=1;i<=n;i++){
		if(i<=r)
			d[i]=min(d[r-i+l],r-i+1);
		while(s[i-d[i]]==s[i+d[i]])
			d[i]++;
		if(i+d[i]-1>r)
			l=i-d[i]+1,r=i+d[i]-1;
	}
}
int main(){
	scanf("%s",ar+1);
	manacher();
	for(int i=1;i<=n;i++)
		ans=max(ans,d[i]);
	printf("%d",ans-1);
	return 0;
}

标签：const,int,不定期,long,算法,ms,return,include,模板
From： https://www.cnblogs.com/Wild-sunflower/p/17970837

相关文章

  • 基础算法(三）二分查找---以“数的三次方”为例
    数的三次方根给定一个浮点数 n，求它的三次方根。输入格式共一行，包含一个浮点数 n。输出格式共一行，包含一个浮点数，表示问题的解。注意，结果保留 6 位小数。数据范围−10000≤n≤10000输入样例：1000.00输出样例：10.000000题解如下#include<iostream>usingnamespace......
  • 推荐算法之-召回中的随机负采样
    //二分查找deffetchBinarySearch(trainItems:Array[(String,Double)],target:Double):String={//valtrainItems=Array(("1",0),("2",1),("3",3),("4",4),("5",6))//valtarget=6.00000000......
  • 区域人数统计AI智能分析网关V4客流统计AI算法介绍及应用场景
    客流量统计AI算法是一种基于人工智能技术的数据分析方法，通过机器学习、深度学习等算法，实现对客流量的实时监测和统计。该算法主要基于机器学习和计算机视觉技术，其基本流程包括图像采集、图像预处理、目标检测、目标跟踪和客流量统计等步骤，通过在监控视频中识别和跟踪人的轮廓或特......
  • 基础算法（二）归并排序模板
    模板如下#include<iostream>usingnamespacestd;constintN=1000010;intq[N],tmp[N];voidmerge_sort(intq[],intl,intr){if(l>=r)return;intmid=(l+r)>>1;intk=0,i=l,j=mid+1;merge_sort(q,l,mid);merge_sort(q,......
  • 模板编程
    函数模板不是一个实在的函数，编译器不能为其生成可执行代码。定义函数模板后只是一个对函数功能框架的描述，当他具体执行的时候，将根据传递的实际参数决定其功能（运行期间的多态，动态多态）。C++提供两种模板机制：类模板和函数模板。注意这里T类型必须在使用模板的时候定义，而且可以有多个T......
  • HanLP — HMM隐马尔可夫模型 -- 维特比(Viterbi)算法 --完整示例代码
    完成代码importpicklefromtqdmimporttqdmimportnumpyasnpimportosdefmake_label(text_str):"""从单词到label的转换,如:今天---->BE麻辣肥牛:--->BMME的--->S"""text_len=len(text_str)iftext_len==1:......
  • 在 SAP Web IDE 个人版中根据模板创建项目时，选择 OData 服务时出现catalog service is
     1.NOTE2684697 ，重点是点2点5的问题 2.去掉CatalogServiceVersion2的系统别名（包括LOCAL）翻阅其他博客，有人说是因为系统别名，我给去掉了。 ......
  • 二次剩余模板简记
    \(x^2\equivn\pmodp\)，其中\(p\)是奇素数。当\(n=0\)时有\(x=0\)，以下规定\(n\not=0\)。假设\(n\)是二次剩余且有多个不同解，其中两个解分别是\(x_0,x_1\in[1,p)\)。有\({x_0}^2\equiv{x_1}^2\equivn\pmodp\)。移项，平方差公式得\((x_0+x_1)(x_0-x_1)\equiv0\p......
  • 基于内容的电影推荐算法研究
    引言今天读的文章为一篇名为《基于内容的电影推荐算法研究》的文章，文章提出了一种基于内容的电影推荐算法，通过分析电影特征和用户兴趣，实现更精准的电影推荐。文章中使用到了TF-IDF向量化方法，将电影类型和导演信息转化为特征向量，然后使用余弦相似度来衡量电影之间的相关性，接下来......
  • C++ STL标准模板库
    目录简介容器（Containers）迭代器（Iterators）算法（Algorithms）函数对象（FunctionObjects）适配器（Adaptors）分配器（Allocators）std::min_element()简介C++中的STL（标准模板库）可以分为六个部分，分别是容器（Containers）、迭代器（Iterators）、算法（Algorithms）、函数对象（FunctionObjects）、适配器（Adapto......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99