• 个人简介

    手写快速排序

    void qsort(int l,int r){
int mid=a[(l+r)/2],i=l,j=r;
do{while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){swap(a[i],a[j]);i++;j--;}
}while(i<=j);
if(l<j)qsort(l,j);
if(i<r)qsort(i,r);
}

    * 单源/全源最短路径（ Dijkstra/SPFA/FloydDijkstra/SPFA/Floyd）

    /已经离我们而去的 SPFA
#include<bits/stdc++.h>
#define N 2<<20
#define INF 0x7fffffff
using namespace std;
int d[N],u[N],v[N],w[N],n,m,s,c;
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
for(int i=1;i<=n;i++)d[i]=INF;
d[s]=0;
for(int k=1;k<=n-1;k++){
c=0;
for(int i=1;i<=m;i++)if(d[v[i]]>d[u[i]]+w[i]){
d[v[i]]=d[u[i]]+w[i];
c=1;
}if(!c)break;
}for(int i=1;i<=n;i++)cout<<d[i]<<' ';
return 0;
}

    最小生成树（Kruskal/PrimKruskal/Prim）

    //Prim 算法
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int d[5005],n,m,e[5005][5005],s,sm;
bool v[5005];
void p(){
int x;
for(int j=1;j<n;++j){
int mn=INF;
for(int i=1;i<=n;i++)if(!v[i]&&d[i]<mn){mn=d[i];x=i;}
v[x]=1;sm+=d[x];
for(int i=1;i<=n;i++)if(!v[i]&&e[x][i]!=INF&&d[i]>e[x][i])d[i]=e[x][i];
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
    for(int j=1;j<i;++j)e[i][j]=e[j][i]=INF;
   for(int i=0;i<m;i++){
    int x,y,l;
    cin>>x>>y>>l;
    if(l<e[x][y])e[x][y]=e[y][x]=l;
    }
    for(int i=1;i<=n;++i)d[i]=e[1][i];
    v[1]=1;p();
    cout<<sm<<endl;
    return 0;
}

    欧拉筛/埃氏筛

    int prime[maxn];
int visit[maxn];
void Prime(){
    mem(visit,0);
    mem(prime, 0);
    for (int i = 2;i <= maxn; i++) {
        cout<<" i = "<<i<<endl;
        if (!visit[i]) {
            prime[++prime[0]] = i;      //纪录素数， 这个prime[0] 相当于 cnt，用来计数
        }
        for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
//            cout<<"  j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

    快速读入模板

    inline int read(){
   register int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}

    快速输出模板

    inline void print(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

    手写GCD

    inline int gcd(int x, int y){return y?gcd(y,x%y):x;}

    手写LCM

    inline int lcm(int GCD,int n,int m){return n*m/GCD;}

    快速幂

    #define int long long
inline int qp(){
    int s=1;
    while(p>0){
        if(p&1)s=s*b%k;
        p>>=1;
        b=(b*b)%k;
    }return s%k;
}

    最长路模板

    #include<bits/stdc++.h>
using namespace std;
#define INF 100000001
int d[2<<23],w[2<<23],n,m,mn,f[2<<23][3];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){d[i]=w[i]=INF;f[i][1]=f[i][2]=0;}
    for(int i=1;i<=m;i++){
        int x,y,l;
        cin>>x>>y>>l;
        f[i][1]=x,f[i][2]=y,w[i]=-l;
    }d[1]=0;
    for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)d[f[j][2]]=min(d[f[j][2]],d[f[j][1]]+w[j]);
    if(d[n])printf("%d",-d[n]);
    else puts("-1");
    return 0;
}

    SPFA 模板

    #include<bits/stdc++.h>
#define N 2<<20
#define INF 0x7fffffff
using namespace std;
int d[N],u[N],v[N],w[N],n,m,s,c;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;
    for(int k=1;k<=n-1;k++){
        c=0;
        for(int i=1;i<=m;i++)if(d[v[i]]>d[u[i]]+w[i]){
            d[v[i]]=d[u[i]]+w[i];
            c=1;
        }if(!c)break;
    }for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return 0;
}

    Prim 模板

    #include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int d[5005],n,m,e[5005][5005],s,sm;
bool v[5005];
void p(){
	int x;
	for(int j=1;j<n;++j){
		int mn=INF;
		for(int i=1;i<=n;i++)if(!v[i]&&d[i]<mn){mn=d[i];x=i;}
		v[x]=1;sm+=d[x];
		for(int i=1;i<=n;i++)if(!v[i]&&e[x][i]!=INF&&d[i]>e[x][i])d[i]=e[x][i];
	}
}int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<i;++j)e[i][j]=e[j][i]=INF;
	for(int i=0;i<m;i++){
		int x,y,l;
		cin>>x>>y>>l;
		if(l<e[x][y])e[x][y]=e[y][x]=l;
	}
	for(int i=1;i<=n;++i)d[i]=e[1][i];
	v[1]=1;p();
	cout<<sm<<endl;
	return 0;
}

    单调队列模板

    #include<bits/stdc++.h>
using namespace std;
int n,m,q1[2<<25],q2[2<<25],a[2<<25];
int minque(){
    int h=1,t=0;
    for(int i=1;i<=n;i++){
        while(h<=t&&q1[h]+m<=i)++h;
        while(h<=t&&a[i]<a[q1[t]])t--;
        q1[++t]=i;
        if(i>=m)printf("%d ",a[q1[h]]);
    }cout<<endl;
}int maxque(){
    int h=1,t=0;
    for(int i=1;i<=n;i++){
        while(h<=t&&q2[h]+m<=i)h++;
        while(h<=t&&a[i]>a[q2[t]])t--;
        q2[++t]=i;
        if(i>=m)printf("%d ",a[q2[h]]);
    }
}int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    minque();maxque();
    return 0;
}

    朴素Dijkstra模板

    #include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int d[5001],n,m,edge[5001][5001],mn,x,s;
bool v[5001];
void dijkstra(){
	for(int j=1;j<n;++j){
		mn=INF;
		for(int i=1;i<=n;i++)if(!v[i]&&d[i]<mn){mn=d[i];x=i;}
		v[x]=1;
		for(int i=1;i<=n;i++)if(e[x][i]!=INF){int t=e[x][i]+d[idx];if(d[i]>t)d[i]=t;}
	}
}int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)for(int j=1;j<i;++j)e[i][j]=e[j][i]=INF;
	for(int i=0;i<m;i++){int x,y,l;cin>>x>>y>>l;e[x][y]=l;}
	for(int i=1;i<=n;++i)d[i]=e[s][i];
	v[s]=1;dijkstra();
	for(int i=1;i<=n;i++)cout<<d[i]<<' ';
	return 0;
}

    并查集模板

    inline int fd(int k){
    if(f[k]==k)return k;
    return f[k]=fd(f[k]);
}inline void mr(int v,int u){
    int t1=fd(v),t2=fd(u);
    if(t1!=t2)f[t2]=t1;
}

    手写快排模板

    void qsort(int l,int r){
    int mid=a[(l+r)/2],i=l,j=r;
    do{while(a[i]<mid)i++;
       while(a[j]>mid)j--;
       if(i<=j){swap(a[i],a[j]);i++;j--;}
    }while(i<=j);
    if(l<j)qsort(l,j);
    if(i<r)qsort(i,r);
}

    埃拉托色尼素数筛

    inline void Era(){
	int m=sqrt(n+0.5);
	for(register int i=2;i<=m;++i)if(!vis[i])for(register int j=i*i;j<=n;j+=i)vis[j]=1;
}

    欧拉素数筛法

    bool n[2<<32];int p[2<<24],c;
void w(int n){
    for(int i=2;i<=n;++i){
        if(!n[i])p[++c]=i ;
        for(int j=1;j<=c&&i*p[j]<=n;++j){
          n[i*p[j]]=1;
          if(i%p[j]==0)break;
        } 
    }
}

    欧拉函数

    #define MAX 20005
int phi[MAX],prime[v],tot;
bool b[MAX];
void getphi(){
    phi[1]=1;
    for(int i=2;i<=MAX;i++){
        if(!b[i]){
            prime[++tot]=i;
            phi[i]=i-1;
        }for(int j=1;j<=tot;j++){
            if(i*prime[j]>MAX)break;
            b[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

    线段树

    #include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200002],n,m,T,d[1000005],b[1000005];
void build(int s,int t,int p){
    if(s==t){
        d[p]=a[s];
        return;
    }int m=(s+t)/2;
    build(s,m,p*2);
    build(m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}void update(int l,int r,int c,int s,int t,int p){
    if(l<=s&&t<=r){
        d[p]+=(t-s+1)*c;
        b[p]+=c;
        return;
    }int m=(s+t)/2;
    if(b[p]&&s!=t){
        d[p*2]+=b[p]*(m-s+1);
        d[p*2+1]+=b[p]*(t-m);
        b[p*2]+=b[p];b[p*2+1]+=b[p];
        b[p]=0;
    }if(l<=m)update(l,r,c,s,m,p*2);
    if(r>m)update(l,r,c,m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}int getsum(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r)return d[p];
    int m=(s+t)/2;
    if(b[p]){
        d[p*2]+=b[p]*(m-s+1);
        d[p*2+1]+=b[p]*(t-m);
        b[p*2]+=b[p];
        b[p*2+1]+=b[p];
        b[p]=0;
    }int sum=0;
    if(l<=m)sum=getsum(l,r,s,m,p*2);
    if(r>m)sum+=getsum(l,r,m+1,t,p*2+1);
    return sum;
}signed main(){
	cin>>n>>m;
	int x,y,op,k;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	for(int i=0;i<m;i++){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			update(x,y,k,1,n,1);
		}if(op==2){
			cin>>x>>y;
			cout<<getsum(x,y,1,n,1)<<endl;
		}
	}return 0;
}

    ST表

    #include<bits/stdc++.h>
#define isdigit(x) ('0'<=x&&x<='9')
#define max(x,y) (x>y?x:y)
using namespace std;
inline int rd(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}int n,m,a[2000001],f[2000001][21],x,y;
void pre() {
	a[1]=0;a[2]=1;
	for(register int i=3;i<200001;i++)a[i]=a[i>>1]+1;
}int main(){
	n=rd();m=rd();
	for(register int i=1;i<=n;i++)f[i][0]=rd();
	pre();
	for(register int j=1;j<=21;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	for(register int i=1;i<=m;i++){
		x=rd();y=rd();
		int s=a[y-x+1];
		printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
	}return 0;
}

    树状数组基操

    int lowbit(int x){
    return x&-x;
}void add(int x,int k){//单点修改
    while(x<=n){//当在最大区间范围内时
        c[x]=c[x]+k;//对当前节点进行修改
        x=x+lowbit(x);//“跳跃”到下一个节点
    }
}int getsum(int x){//求a1,a2,a3……ax的和
    int ans=0;
    while(x>=1){//当x在给定范围内
        ans+=c[x];//求和
        x-=lowbit(x);//跳跃到下一个节点
    }return ans;
}inline void init(){//O(n)建树
    for(int i=1;i<=n;++i){
        t[i]+=a[i];
        int j=i+lowbit(i);
        if(j<=n)t[j]+=t[i];
    }
}

    最后，祝大家做题愉快！

  • 通过的题目

  • 最近活动

    This person is lazy and didn't join any contests or homework.

  • 最近编写的题解

    This person is lazy and didn't write any solutions.
10
已递交
9
已通过
0
题解被赞

题目标签

聪明人游戏
3
dp
1
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 19ms
  4. Powered by Hydro v4.11.2 Community