模板整合
QingLin001 · · 个人记录
数学
快速幂
long long版
PS：如果传入参数是long long请自行修改
typedef long long LL;
LL qmi(int a,int b,int q)
{
LL ans=1%q;
while(b)
{
if(b & 1)
ans=ans*a%q;
a=(LL)a*a%q;
b>>=1;
}
return ans;
}int版
int qmi(int a,int b,int q)
{
int ans=1%q;
while(b)
{
if(b & 1)
ans=ans*a%q;
a=a*a%q;
b>>=1;
}
return ans;
}高精度运算
原地址：duoluoluo的博客-高精模板
最小公倍数和最大公约数
进制转换
int x,n,tot=0,s[100];
scanf("%d %d",&n,&x);
while (n!=0)
{
int a=n%x;
n=n/x;
s[++tot]=a;
}判断质数
bool prime(int x)
{
if(x<=1)return false;
if(x==2)return true;
for(int i=2;i<=sqrt(x);i++)
if(!x%i)
return false;
return true;
}排序
快速排序
void qsort(int l,int r)
{
int i,j,mid,p;
i=l;
j=r;
mid=a[(l+r)/2];
while(i<j)
{
while(a[i]<mid)
{
i++;
}
while(a[j]>mid)
{
j--;
}
if(i<=j)
{
p=a[i];
a[i]=a[j];
a[j]=p;
i++;
j--;
}
}
if(l<j)
{
qsort(l,j);
}
if(i<r)
{
qsort(i,r);
}
}归并排序
void msort(int l,int r)
{
if(l==r)return ;
int mid=(l+r)/2;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid && j<=r)
{
if(a[i]<=a[j])
{
R[k]=a[i];
i++;
k++;
}
else
{
R[k]=a[j];
j++;
k++;
}
}
while(i<=mid)
{
R[k]=a[i];
i++;
k++;
}
while(j<=r)
{
R[k]=a[j];
j++;
k++;
}
for(int i=l;i<=r;i++)
{
a[i]=R[i];
}
}逆序对
void msort(int l,int r)
{
if(l==r)return ;
int mid=(l+r)/2;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid && j<=r)
{
if(a[i]<=a[j])
{
R[k]=a[i];
i++;
k++;
}
else
{
R[k]=a[j];
j++;
k++;
ans=ans+mid-i+1;
}
}
while(i<=mid)
{
R[k]=a[i];
i++;
k++;
}
while(j<=r)
{
R[k]=a[j];
j++;
k++;
}
for(int i=l;i<=r;i++)
{
a[i]=R[i];
}
}冒泡排序
for(int i=1;i<=n;i++)
for(int j=1;j<n-i;j++)
if(array[j]>array[j+1])
swap(array[j],array[j+1];桶排序
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
a[tmp]++;
}
for(int i=0;i<=n;i++)
for(int j=1;j<=a[i];j++)
printf("%d ",i);
//注：本排序仅支持正整数动态规划
背包
01背包
for(int i=1;i<=m;i++)
for(int j=t;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]+b[i]);完全背包
for(int i=1;i<=m;i++)
for(int j=a[i];j<=t;j++)
f[j]=max(f[j],f[j-a[i]]+b[i]);多重背包
for(int i=1;i<=n;++i)
for(int j=V;j>=v[i];--j)
f[j]=max(f[j],f[j-v[i]]+w[i]);
for(int i=0;i<=V;++i)ans=max(ans,f[i]);混合背包
注释：混合背包没有固定形态，这里提供以樱花为例的模板。
for(int i=1;i<=n;i++)
{
scanf("%d %d %d",&x,&y,&z);
if(!z) //可以无限看
{
d[++tot]=0;
w[tot]=x;
v[tot]=y;
}
else
{
for(int j=1;j<=z;j*=2)
{
d[++tot]=1;
w[tot]=j*x;
v[tot]=j*y;
z-=j;
}
if(z)
{
d[++tot]=1;
w[tot]=z*x;
v[tot]=z*y;
}
} //二进制多重背包
}
for(int i=1;i<=tot;i++)
{
if(d[i])
for(int j=last_time;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
else
for(int j=w[i];j<=last_time;j++)
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}树形DP
邻接表
int head[N],ver[M],Next[M],edge[M],tot;
void add(int x,int y,int z)
{
ver[++tot]=y;
edge[tot]=z;
Next[tot]=head[x];
head[x]=tot;
}一般的树形DP
void dp(int x)
{
f[x][0]=0;
f[x][1]=h[x];
int len=son[x].size();
for(int i=0;i<len;i++)
{
int y=son[x][i];
dp(y);
f[x][0]+=max(f[y][0],f[y][1]);
f[x][1]+=f[y][0];
}
}树形DP-背包
以选课为例
void dp(int x)
{
f[x][0]=0;
int len=son[x].size();
for(int i=0;i<len;i++)
{
int y=son[x][i];
dp(y);
for(int j=m;j>=0;j--)
for(int t=j;t>=0;t--)
f[x][j]=max(f[x][j],f[x][j-t]+f[y][t]);
}
if(x!=0)
{
for(int t=m;t>=1;t--)
{
f[x][t]=f[x][t-1]+s[x];
}
}
}换根DP-积蓄程度
void dp(int x)
{
v[x]=1;
d[x]=0;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(v[y])
continue;
dp(y);
if(deg[y]==1)
d[x]+=edge[i];
else
d[x]+=min(d[y],edge[i]);
}
}
void dfs(int x)
{
v[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(v[y])
continue;
if(deg[x]==1)
f[y]+=d[y]+edge[i];
else
f[y]=d[y]+min(f[x]-min(d[y],edge[i]),edge[i]);
dfs(y);
}
}状压DP
最短Hamilton路径
memset(f,0x3f,sizeof(f));
f[1][0]=0;
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
{
if((i>>j) & 1)
{
for(int k=0;k<n;k++)
{
if((i>>k) & 1)
{
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+a[k][j]);
}
}
}
}
}
printf("%d",f[(1<<n)-1][n-1]);蒙德里安的梦想
for(int i=0;i<1<<n;i++)
{
int cnt=0;
st[i]=true;
for(int j=0;j<n;j++)
{
if(i>>j & 1)
{
if(cnt & 1)
st[i]=false;
cnt=0;
}
else
cnt++;
}
if(cnt & 1)
st[i]=false;
}
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<1<<n;j++)
for(int k=0;k<1<<n;k++)
if(!(j & k) && st[j | k])
f[i][j]+=f[i-1][k];
printf("%lld\n",f[m][0]);单调栈
单调递增栈
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
while(tot>0 && x>sta[tot][0])
{
ans[sta[tot][1]]=i;
tot--;
}
sta[++tot][0]=x,sta[tot][1]=i;
}单调递减栈
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
while(tot>0 && x<sta[tot][0])
{
ans[sta[tot][1]]=i;
tot--;
}
sta[++tot][0]=x,sta[tot][1]=i;
}单调队列
单调递增队列
for(int i=0;i<n;i++)
{
if(hh<=tt && i-q[hh]+1>k)
hh++;
while(hh<=tt && a[q[tt]]>=a[i])
tt--;
q[++tt]=i;
if(i>=k-1)
printf("%d ",a[q[hh]]);
} 单调递减队列
for(int i=0;i<n;i++)
{
if(hh<=tt && i-q[hh]+1>k)
hh++;
while(hh<=tt && a[q[tt]]<=a[i])
tt--;
q[++tt]=i;
if(i>=k-1)
printf("%d ",a[q[hh]]);
} 搜索
全排列类问题
void dfs(int x)
{
if(x==n+1)
{
for(int i=1;i<=n;i++)
{
printf("%5d",a[i]);
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
st[i]=true;
a[x]=i;
dfs(x+1);
st[i]=false;
}
}
} 平面移动类问题
以回家为例
int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
void dfs(int x,int y,int z)
{
z--;
if(hp==0||ss>n*m||ss>s)
{
return;
}
if(a[x][y]==4)
{
z=6;
}
if(x==h1&&y==h2)
{
u=0;
s=min(ss,s);
return;
}
for(int i=0;i<4;i++)
{
if(a[x+fx[i]][y+fy[i]]!=0&&x+fx[i]>=0&&x+fx[i]<n&&y+fy[i]>=0&&y+fy[i]<m)
{
ss++;
dfs(x+fx[i],y+fy[i],z-1);
ss--;
}
}
}一些关于树的其他东西
遍历
中序、前序求后序
void dfs(int L1,int R1,int L2,int R2)
{
int m=a.find(b[L2]);
if(m>L1)
{
dfs(L1,m-1,L2+1,m+L2-L1);
}
if(m<R1)
{
dfs(m+1,R1,R2-R1+m+1,R2);
}
cout<<a[m];
}中序、后序求前序
void dfs(int L1,int R1,int L2,int R2)
{
int m=a.find(b[R2]);
cout<<a[m];
if(m>L1)
{
dfs(L1,m-1,L2,m+L2-L1-1);
}
if(m<R1)
{
dfs(m+1,R1,R2-R1+m,R2-1);
}
}树的直径
DP做法
void dp(int x)
{
v[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(v[y])
continue;
dp(y);
ans=max(ans,d[x]+d[y]+edge[i]);
d[x]=max(d[x],d[y]+edge[i]);
}
}2次BFS做法
int bfs(int x)
{
queue<int> q;
while(!q.empty())
{
q.pop();
}
memset(v,0,sizeof(v));
memset(dis,0,sizeof(dis));
memset(fa,0,sizeof(fa));
q.push(x);
int k,max_num,MAX=0;
while(q.size())
{
k=q.front();
q.pop();
v[k]=1;
for(int i=head[k];i>=1;i=Next[i])
{
int y=ver[i];
if(v[y])
{
continue;
}
v[y]=1;
fa[y]=k;
dis[y]=dis[k]+edge[i];
if(dis[y]>MAX)
{
MAX=dis[y];
max_num=y;
}
q.push(y);
}
}
return max_num;
}
线段树
建树
struct segmenttree{
int l,r,sum;
};
segmenttree a[4*N+1];
void build(int p,int l,int r)
{
a[p].l=l,a[p].r=r;
if(l==r)
{
a[p].sum=b[l];
return ;
}
int mid=a[p].l+a[p].r>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
a[p].sum=a[p*2].sum+a[p*2+1].sum;
}单点修改
void rebuild_node(int p,int x,int k)
{
if(a[p].l==a[p].r)
{
a[p].sum+=k;
return ;
}
int mid=a[p].l+a[p].r>>1;
if(x<=mid)
rebuild_node(p*2,x,k);
else
rebuild_node(p*2+1,x,k);
a[p].sum=a[p*2].sum+a[p*2+1].sum;
}询问
int ask(int p,int l,int r)
{
int ans=0,mid=a[p].l+a[p].r>>1;
if(a[p].l>=l && a[p].r<=r)
{
ans+=a[p].sum;
return ans;
}
if(l<=mid)
ans+=ask(p*2,l,r);
if(r>mid)
ans+=ask(p*2+1,l,r);
return ans;
}图论
单源最短路SPFA
void SPFA()
{
d[s]=0;
v[s]=1;
q.push(s);
while(q.size())
{
int x=q.front();
q.pop();
v[x]=0;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i],z=edge[i];
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
if(!v[y])
{
v[y]=1;
q.push(y);
}
}
}
}
}其它
区间DP的拆环操作
for(int i=1;i<=n;i++)
{
a[i+n]=a[i];
}一维前缀和
for(int i=1;i<=n;i++)
{
w[i]+=w[i-1]+a[i];
}二维前缀和初始化模板
for(int i=1;i<=5001;i++)
for(int j=1;j<=5001;j++)
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];二维前缀和累加模板
for(int i=m;i<=5001;i++)
for(int j=m;j<=5001;j++)
ans=max(ans,a[i][j]-a[i-m][j]-a[i][j-m]+a[i-m][j-m]);快速输入1
inline int read()
{
int num=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num;
}快速输入2
inline int in()
{
int f,t;
f=1,t=0;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
t=t*10+ch-'0';
ch=getchar();
}
return f*t;
}快速输出1
inline void quick_put(int x)
{
if(x==0)
{
printf("0");
return ;
}
char F[200];
int tmp=abs(x);
if(x<0)putchar('-') ;
int cnt=0;
while(tmp>0)
{
F[cnt++]=tmp%10+'0';
tmp/=10;
}
while(cnt>0)
putchar(F[--cnt]) ;
}快速输出1
putchar(x+'0');二分
long long l=0,r=N;
while(l<r)
{
long long mid=l+r+1>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}