蓝桥杯算法题3

前言

区间dp

回⽂字串

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=1010;
int f[N][N];
//状态表示：f[i][j]表示字符串第i到j个字符需要最少插入字符数
//s[i]==s[j],f[i][j]=f[i+1][j-1]
//s[i]!=s[j],j的右边插一个s[i]的话，f[i][j]=f[i+1][j]+1
//i左边插入一个s[j]的话，f[i][j]=f[i][j-1]+1，所以s[i]!=s[j]，f[i][j]=min(f[i+1][j]+1,f[i][j-1]+1)//初始化：我们每个f[i][j]要使用的是左边，下边，和左下的
//遍历顺序，从len=1开始遍历，从左端点开始遍历，这样就可以得到右端点了
int main(){string s;cin>>s;int n=s.size();s= " "+s;//当len=1的时候，就是f[i][i]=0；所以可以直接从2开始for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){//i+len-1就是右端点int j=i+len-1;//所以j肯定大于i的，在右上角位置if(s[i]==s[j]) f[i][j]=f[i+1][j-1];//只有len为2的时候，f[i+1][j-1]可能会是右下角的值，但是len为2的时候，左边等于右边，那么就是0，没有问题的else f[i][j]=min(f[i+1][j]+1,f[i][j-1]+1);//这两个不会越界}}cout<<f[1][n]<<endl;return 0;
}

石子合并（弱化版）

石子合并（弱化版

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=310;
int n;
int sum[N];//前缀和数组
int f[N][N];//f[i][j]表示从i~j的最小代价
//取一个点k，i<=k<j,这样就可以把i~j分为两个区间，[i,k][k+1,j]
//f[i][j]=min(f[i][k]+f[k+1][j]+sum[i,j],f[i][j])//初始化：因为每次min中都有f[i][j]，所以初始化为正无穷，然后len为1的时候，代价为0int main(){cin>>n;for(int i=1;i<=n;i++){int a;cin>>a;sum[i]=sum[i-1]+a;}memset(f,0x3f,sizeof f);for(int i=1;i<=n;i++){f[i][i]=0;}for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;for(int k=i;k<j;k++){f[i][j]=min(f[i][k]+f[k+1][j]+sum[j]-sum[i-1],f[i][j]);}}}cout<<f[1][n]<<endl;return 0;
}

最小生成树

【模板】最小生成树

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;//最小生成树，prim算法，就是说每次都选一个距离树最近的点
const int N=5010;
int edges[N][N];
int dist[N];//dist[i]表示第i个节点到树的最小距离
bool st[N];//st[i]表示这个i节点在不在这个树里面，默认false不在
int n,m;
const int  M= 0x3f3f3f3f;
int dfs(){memset(dist,0x3f,sizeof dist);int ret=0;dist[1]=0;//随机选一个点作为源,说它最近for(int i=1;i<=n;i++){//选取n个点int t=0;//找出距离树最小的下标,设置为0，因为dist[0]永远最大for(int j=1;j<=n;j++){if(!st[j]&&dist[j]<dist[t]) t=j;}if(dist[t]==M) return M;//说明不联通了st[t]=true;//加入树ret+=dist[t];//更新所有节点到这个点的最近距离for(int i=1;i<=n;i++){if(!st[i]){dist[i]=min(dist[i],edges[i][t]);}}}return ret;
}int main(){cin>>n>>m;memset(edges,0x3f,sizeof edges);for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;//如果没有说明的话，可能两个点之间有多个边，我们选择最小的就可以了--》min。，所以初始化为无穷大edges[x][y]=min(edges[x][y],z);edges[y][x]=edges[x][y];}int ret=dfs();if(ret==M)cout<<"orz"<<endl;else cout<<ret<<endl;return 0;
}

拓扑排序

【模板】拓扑排序 / 家谱树

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;const int N=110;
int edges[N][N];
int in[N];//存储每个边的入度信息
int n;
int main(){cin>>n;for(int i=1;i<=n;i++){int j;while(cin>>j,j){edges[i][j]=1;in[j]++;}}//开始拓扑排序//先将入度为0的点存入队列queue<int> q;for(int i=1;i<=n;i++){if(in[i]==0)q.push(i);}while(q.size()){int t=q.front();cout<<t<<" ";q.pop();//消除t指向的节点的入度for(int i=1;i<=n;i++){if(edges[t][i]==1){in[i]--;if(in[i]==0)q.push(i);}	}}return 0;
}

单源最短路

【模板】单源最短路径（弱化版）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>//pow
#include<vector>
using namespace std;
const int M=2147483647;
const int N=1e4+10;
int d[N];//记录s到每个边的最短距离
bool is[N];//记录这个点是否已经确定了最短距离
int n,m,s;typedef pair<int,int> PLL;
vector<PLL> edges[N];//记录每个点指向的点和权值void test(int s){//初始化
//		memset(d,0x3f,sizeof d);//每个初始化为Mfor(int i=0;i<=n;i++){d[i]=M;//记得从0开始}d[s]=0;for(int i=1;i<n;i++){//找出n-1个点的最短距离，最后一个点的距离就确定了int t=0;//记录每个d的最短距离的下标for(int j=1;j<=n;j++){if(!is[j]&&d[j]<d[t])t=j;}//确定t为最短距离
//		if(d[t]==M)return M;is[t]=true;//更新到其他点的距离for(auto point : edges[t]){int x=point.first;int y=point.second;if(!is[x]&&d[x]>d[t]+y)d[x]=d[t]+y;}}
}int main(){
//	cout<<M;
//	cout<<(long long)pow(2,31)<<endl;cin>>n>>m>>s;while(m--){int u,v,w;cin>>u>>v>>w;edges[u].push_back({v,w});}test(s);for(int i=1;i<=n;i++)cout<<d[i]<<" ";return 0;
}

【模板】单源最短路径（标准版)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>//有优先级队列的const int N=1e5+10;
int n,m,s;
using namespace std;
typedef pair<int,int> PLL;
vector<PLL> edges[N];//x为链接的节点，y为权值
priority_queue<PLL,vector<PLL>,greater<PLL>> p;
//这是一个堆，存储的元素是PLL,底层容器是vector<PLL>，排序是按照PLL的升序排
//所以小元素有高的优先级，x为d[i],y为被s链接的节点iint d[N];
bool is[N];void test(int s){memset(d,0x3f,sizeof d);d[s]=0;p.push({0,s});while(p.size()){PLL point=p.top();p.pop();//取出最短边int t=point.second;if(is[t])continue;//不然每个都会去走for循环了，因为走了if(!is[x]&&d[x]>d[t]+y)，不会把原来的//覆盖，但是取到的肯定是最小的，防止再去for循环，所以要单独处理一下is[t]=true;//更新所有的边for(auto tmp:edges[t]){int x=tmp.first;int y=tmp.second;if(!is[x]&&d[x]>d[t]+y){d[x]=d[t]+y;p.push({d[x],x});}}}
}int main(){cin>>n>>m>>s;while(m--){int u,v,w;cin>>u>>v>>w;edges[u].push_back({v,w});}test(s);for(int i=1;i<=n;i++){cout<<d[i]<<" ";}return 0;
}

多源最短路

【模板】Floyd

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=110;
int f[N][N];
int n,m;
int main(){cin>>n>>m;//初始化f，代表插入0个点的时候，i到j的最短距离memset(f,0x3f,sizeof f);while(m--){int u,v,w;cin>>u>>v>>w;f[u][v]=f[v][u]=min(f[u][v],w);//因为可能存在重边}for(int i=1;i<=n;i++){f[i][i]=0;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//代表插入第k个点时候的最短距离}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<f[i][j]<<" ";}cout<<endl;}return 0;
}

最⼤公约数和最⼩公倍数

[信息与未来 2018] 最大公约数

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;//gcb为a和b的最大公约数，lcm为a和b的最下公倍数
//那么gcb*lcm=a*b
//gcb(a,b)=gcb(b,a%b);//最终如果b为0，那么a就是最大公约数
//a<b的话，gcb(a,b)=gcb(b,a);int gcb(int a,int b) {if(b==0){return a;}return gcb(b,a%b);
}int main(){int x,y,z;cin>>x>>y>>z;cout<<gcb(gcb(x,y),z);return 0;
}

质数的判定

【深基7.例2】质数筛

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;bool isprime(int a){if(a<=1)return false;for(int i=2;i<=a/i;i++){if(a%i==0)return false;}return true;
}int main(){int n;cin>>n;while(n--){int a;cin>>a;if(isprime(a))cout<<a<<" ";}	return 0;
}

筛质数,埃氏筛，线性筛

【模板】线性筛素数

#include<iostream>
using namespace std;
const int N=1e8+10; typedef long long LL;
LL n,q;
bool is[N];//记录这个位置是不是质数LL f[N];//记录所有的质数
LL cnt;//记录有几个质数//埃氏筛
//void isprime(){
//	for(LL i=2;i<=n;i++){
//		if(!is[i]){
//			f[++cnt]=i;
//			for(LL j=i*i;j<=n;j+=i){
//				is[j]=true;
//			}
//		}
//	}
//}//线性筛
void isprime(){for(LL i=2;i<=n;i++){if(!is[i])f[++cnt]=i;//每次从i的质数倍开始晒for(int j=1;f[j]*i<=n;j++){is[f[j]*i]=true;//每次i为质数的倍数的时候停止if(i%f[j]==0)break;}}
}int main(){scanf("%lld%lld",&n,&q);isprime();while(q--){int x;scanf("%d",&x);printf("%d\n",f[x]);}return 0;
}

算术基本定理

任何⼀个⼤于的⾃然数，都可以唯⼀分解成有限个质数的乘积

质因子分解

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=10010;
int f[N];//记录i这个因子出现了多少次
int n;
//任何一个数都可以表示为若干个质数的乘积
void isprime(int a){for(int i=2;i<=n/i;i++){int cnt=0;while(a%i==0){a=a/i;cnt++;}f[i]+=cnt;}if(a>1)f[a]++;
}int main(){cin>>n;for(int i=2;i<=n;i++){isprime(i);}for(int i=2;i<=n;i++){if(f[i])cout<<i<<" "<<f[i]<<endl;}return 0;
}

约数

约数之和

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int main(){cin>>n;int sum=0;for(int i=1;i<=n/i;i++){if(n%i==0){sum+=i;if(i!=n/i)sum+=n/i;}}cout<<sum;return 0;
}

约数个数的和

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;int n;int main(){cin>>n;int sum=0;for(int i=1;i<=n/2;i++){sum+=n/i;}sum+=n-n/2;cout<<sum;return 0;
}

欧拉函数

仪仗队

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=40010;//思考易得，只要横纵坐标互质，那么就看得到，求j列能看到的，说白了就是求j的欧拉函数，坐标从0开始
int phi[N];//phi[i]存储1~i中与i互质的数的个数，就是欧兰函数
int sum;//可以化成两半，一半是1~n的欧兰函数和m。所以sum=2*m+1;
int n;
bool is[N];//是否是质数
int f[N];//存储质数
int cnt;//质数的个数void test(){phi[1]=1;//1的欧拉函数就是1for(int i=2;i<=n;i++){if(!is[i]){f[++cnt]=i;phi[i]=i-1;}for(int j=1;1ll* f[j]*i<=n;j++){//把i的质数倍变成trueint x=i*f[j];is[x]=true;if(i%f[j]==0){phi[x]=f[j]*phi[i];break;}else{phi[x]=phi[i]*(f[j]-1);}}}
}int main(){cin>>n;test();for(int i=1;i<n;i++){sum+=phi[i];}sum=sum*2+1;if(n==1)cout<<0;else cout<<sum;return 0;
}

费马小定理

序列求和

#include<iostream>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL p=1000000007;
//s(n)=(n*(n*1)(2*n+1))/6%p;
//a/b%p======>a*b^-1%p,而b^-1=b^p-2;//使用前提b与p互质，且p为质数LL mypow(LL a,LL b,LL p){LL ret=1;while(b){if(b&1!=0){ret=ret*a%p;}a=a*a%p;b=b>>1;}return ret;
}int main(){LL n;while(cin>>n){LL a=n%p;LL b=(n+1)%p;LL c=(2*n+1)%p;LL d=mypow(6,p-2,p);LL sum=a*b%p;sum=sum*c%p;sum=sum*d%p; cout<<sum<<endl;}return 0;
}

欧拉定理与扩展欧拉定理

在这里插入图片描述
b比较小的时候，直接用快速幂，b比较大的时候，就用扩展欧拉定理

【模板】扩展欧拉定理

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;typedef long long LL;//试除法求单个数的欧拉函数，线性筛求一堆数的欧拉函数
//用欧兰函数的定理====m*(p1-1)/p1......
LL oula(LL m){LL ret=m;for(LL i=2;i<=m/i;i++){if(m%i==0){ret=ret/i*(i-1);while(m%i==0){m/=i;}}}if(m>1)ret=ret/m*(m-1);return ret;
}LL kuozhan(string s,LL m){LL ret=0;bool flag=false;for(auto s1: s){ret=ret*10+s1-'0';if(ret>=m){flag=true;ret=ret%m;}}if(flag)ret=ret+m;return ret;
}LL kuaisu(LL a,LL b,LL m){int ret=1;while(b){if(b&1)ret=ret*a%m;a=a*a%m;b=b>>1;}return ret;
}int main(){LL a,m;string b;cin>>a>>m>>b;//求a^b%m//先求出m的欧拉函数LL ol=oula(m);//再把b用扩展欧拉定理变小LL b1=kuozhan(b,ol);//最后求快速幂cout<<kuaisu(a,b1,m);return 0;
}