算法大纲
基础算法:模拟,分治,递归,排序,概率,堆
进阶算法: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