高精

高精

关注
发信
关注(28)粉丝(399)

秘制CSP模板

不定期更细中。。。。。。

声明1：由于js的问题导致VIEW CODE按钮只能点“I”附近才能展开代码

声明2：为了排版的美观，所有的解释以及需要留意的地方我都放在代码中了

声明3：以下所有代码均是已经AC的，请各位放心食用

STL类

堆

#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int> >dui;
int main(){
    cin>>n;
    for(register int i=1;i<=n;++i){
        register int ty;cin>>ty;
        if(ty==1){
            cin>>ty;
            dui.push(ty);
        }
        else if(ty==2){
            cout<<dui.top()<<endl;
        }else{
            dui.pop();
        }
    }
}

图类

负环

#include<bits/stdc++.h>
using namespace std;
int tt,n,m,head[100005],ji,dis[100005],cnt[100005];
int read(){
  int x=0,f=1;char c=getchar();
  while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
  while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
  return x*f;
}
struct node{
    int next,yuan,w;
}ed[1000005];
void add(int p,int q,int quan){
    ed[++ji].next=head[p];
    ed[ji].yuan=q;
    ed[ji].w=quan;
    head[p]=ji;
}
bool huan;
queue<int>dui;//队列就行了
void spfa(){
    while(dui.size())dui.pop();
    dui.push(1);
    dis[1]=0;//0号节点到根节点的距离为0
    while(dui.size()){
        int x=dui.front();dui.pop();
        for(int i=head[x];i;i=ed[i].next){
            int y=ed[i].yuan,l=dis[x]+ed[i].w;
            if(dis[y]>l){
                dis[y]=l;
                ++cnt[y];
                dui.push(y);
                if(cnt[y]>=n){huan=1;return;}//>=n!!!
            }
        }
    }
}
int main(){
    cin>>tt;
    while(tt--){
        cin>>n>>m;
        memset(head,0,sizeof(head));
        memset(ed,0,sizeof(ed));
        memset(dis,127,sizeof(dis));
        memset(cnt,0,sizeof(cnt));
        ji=0,huan=0;
        for(int i=1;i<=m;i++){
            register int cn=read(),cm=read(),cw=read();
            if(cw<0)add(cn,cm,cw);
            else add(cm,cn,cw),add(cn,cm,cw);
        }
        spfa();
        if(huan)cout<<"YE5"<<endl;
        else cout<<"N0"<<endl;
    }
    return 0;
}

Dij

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int m,n,s,ji,head[200005],dis[200005];
bool bo[200005];
struct node{
    int w,next,yuan;
}ed[200005];
void add(int p,int q,int quan)
{
    ed[++ji].w=quan;
    ed[ji].yuan=q;
    ed[ji].next=head[p];
    head[p]=ji;
}
priority_queue < pair < int , int > > dui;//注意怎么写
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int cm,cn,cs;
        scanf("%d%d%d",&cm,&cn,&cs);
        add(cm,cn,cs);
    }
    for(int i=1;i<=n;i++)dis[i]=0x7fffffff;//注意是只有初始化
        dis[s]=0;
        dui.push(make_pair(0,s));//注意make_pair怎么写,内容是什么
        while(!dui.empty()){//注意有括号
            int x=dui.top().second;//括号
            dui.pop();
            if(bo[x])continue;//记得判断重复
            bo[x]=1;
            for(int j=head[x];j;j=ed[j].next){
                int y=ed[j].yuan,l=dis[x]+ed[j].w;
                if(dis[y]>l){
                    dis[y]=l;
                    dui.push(make_pair(-dis[y],y));//是-dis[y]
                }
            }
        }

    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

spfa

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int read(){
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
int head[200005],ji,dis[200005];
struct node{
    int next,yuan,w;
}ed[5000005];
void add(int p,int q,int quan){
    ed[++ji].next=head[p];
    ed[ji].yuan=q;
    ed[ji].w=quan;
    head[p]=ji;
}
bool bo[1000005];
queue<int>dui;
void spfa(){
    dui.push(s);bo[s]=1;
    for(int i=1;i<=n;i++)dis[i]=0x7fffffff;dis[s]=0;
    while(dui.size()){
        int x=dui.front();dui.pop();
        bo[x]=0;
        for(int i=head[x];i;i=ed[i].next){
            int y=ed[i].yuan,l=ed[i].w+dis[x];
            if(dis[y]>l){
                dis[y]=l;
                if(!bo[y]){//注意注意spfa与dij最大的额就是bo的位置
                //dij每个点只会更新一次spfa可能会多次更新
                    bo[y]=1;
                    dui.push(y);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int cn=read(),cm=read(),cw=read();
        add(cn,cm,cw);
    }
    spfa();
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}

tarjan

#include<bits/stdc++.h>
using namespace std;
int n,m,head[100005],ji,sum,ans,mem;
struct node{
    int next,yuan;
}ed[100005];
void add(int p,int q){
    ed[++ji].next=head[p];
    ed[ji].yuan=q;
    head[p]=ji;
}
int dfn[100005],low[100005];
stack<int>dui;//必须用stack!!!队列是先进先出
bool bo[100005];
void tarjan(int k){
    mem=0;
    low[k]=dfn[k]=++ji;
    dui.push(k);bo[k]=1;
    for(int i=head[k];i;i=ed[i].next){
        int y=ed[i].yuan;
        if(!dfn[y]){
            tarjan(y);
            low[k]=min(low[k],low[y]);
        }else {
            if(bo[y]){
                low[k]=min(low[k],low[y]);
            }
        }
    }
    if(dfn[k]==low[k]){
        bo[k]=0;
        int x=dui.top();
        while(x!=k&&dui.size()){
            bo[x]=0;
            dui.pop();
            x=dui.top();
            ++mem;
        }
        dui.pop();
        if(mem>0)++ans;//因为题目说了构成联通块的牛的数量要>=2
        mem=0;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int cn,cm;
        cin>>cn>>cm;
        add(cn,cm);
    }
    ji=0;
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    cout<<ans;
}

SCC

#include<bits/stdc++.h>
using namespace std;
int n,m,dfn[1000005],low[1000005],col[1000005],sum,si[1000005],out[1000005];
struct node{
    int next,yuan;
}ed[1000005];
int head[10000105],ji;
void add(int p,int q){
    ed[++ji].next=head[p];
    ed[ji].yuan=q;
    head[p]=ji;
}
bool bo[1000005];
stack<int>dui;
void tarjan(int k){
    low[k]=dfn[k]=++ji;
    dui.push(k);
    bo[k]=1;
    for(int i=head[k];i;i=ed[i].next){
        int y=ed[i].yuan;
        if(!dfn[y]){
            tarjan(y);
            low[k]=min(low[k],low[y]);
        }else {
            if(bo[y]){
                low[k]=min(low[k],low[y]);
            }
        }
    }
    if(dfn[k]==low[k]){
        si[++sum]=1;
        col[k]=sum;
        bo[k]=1;
        while(dui.top()!=k){
            col[dui.top()]=sum;
            bo[dui.top()]=0;
            si[sum]++;//与正常tarjan相比就是这里和上面col不同，si是统计每个块里面有多少个元素
            dui.pop();
        }
        dui.pop();
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int cn,cm;cin>>cn>>cm;
        add(cn,cm);
    }ji=0;
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    //到这里强连通分量已经算完啦
    //后面只是题目要求。。。
    /*
    具体解释参考 恨妹不成穹 的解释：
    但如果有多个点出度为0，那么它们都当不了明星（它们没有受到对方的爱慕—>它们没有受到所有牛的爱慕）
    得出结论:
    1.缩点后，若只有一个出度为0的点，那么明星牛的个数即那个强连通分量包含的点的个数；
    2.缩点后，若有多个出度为0的点或无出度为0的点，那么明星牛的个数即为0。
    */
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=ed[j].next){
            int y=ed[j].yuan;
            if(col[i]!=col[y])++out[col[i]];
        }
    }
    int cun=0,ans=0;
    for(int i=1;i<=sum;i++){
        if(!out[i]){//
            ++cun;
            ans+=si[i];
        }
        if(cun>=2){
            cout<<"0"<<endl;
            return 0;
        }
    }
    cout<<ans;
}

LCA

#include<bits/stdc++.h>
using namespace std;
int n,m,root,f[500005][25];
struct node{
    int next,yuan;
}ed[5000005];
int head[500005],ji,de[500005];
inline int read(){
    register int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
inline void add(int p,int q){
    ed[++ji].next=head[p];
    ed[ji].yuan=q;
    head[p]=ji;
}
inline void dfs(int k,int ste){
    for(int j=1;j<=20;j++){//因为不一定编号小的就是编号大的 的祖先所以要在dfs时预处理f
        f[k][j]=f[f[k][j-1]][j-1];  //还有，f预处理必须放在dfs前面，因为后面的儿子会要用到这个f
    }
    for(register int i=head[k];i;i=ed[i].next){
        register int y=ed[i].yuan;
        if(!de[y]){
            de[y]=ste;
            f[y][0]=k;
            dfs(y,ste+1);
        }
    }

}
inline int lca(int p,int q){
    if(de[p]>de[q])swap(p,q);
    for(register int i=20;i>=0;i--){
        if(de[f[q][i]]>=de[p])q=f[q][i];//记得是>=!!!
    }
    if(p==q)return p;
    for(register int i=20;i>=0;i--){
        if(f[p][i]!=f[q][i]){
            p=f[p][i],q=f[q][i];
        }
    }
    return f[p][0];
}
int main(){
    cin>>n>>m>>root;
    for(register int i=1;i<n;i++){
        register int cn=read(),cm=read();
        add(cn,cm);add(cm,cn);
    }
    de[root]=1;
    dfs(root,2);
    for(register int i=1;i<=m;i++){
        register int cn=read(),cm=read();
        printf("%d\n",lca(cn,cm));//cout->printf 2.7s->1.7s
    }
}

数论类

线性基

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p[55],a,n,ans;
void merge(ll k){
    for(int i=55;i>=0;i--){//>=0!!!!!!!!
        if(!(k>>i))continue;
        if(!p[i]){p[i]=k;break;}
        k^=p[i];//消去最高位，后面的1不管，这也是为什么线性基不唯一——shuixirui
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        merge(a);
    }
    for(int i=55;i>=0;i--){
        if((ans^p[i])>ans)ans^=p[i];
    }
    cout<<ans;
}
//如果要查询某个数是否能被该线性基表出可以把该数转成二进制
//对于每一位如果为1就XORp[i]如果最后结果为0则可以被表出

裴蜀定理

//裴蜀定理内容ax+by=c,x∈Z*,y∈Z*成立的充要条件是gcd(a,b)∣c,Z* 表示正整数集。
//扩展到求ax+by=c 的最小非负 c,显然 c 要满足 (a,b)|c,所以 c 取 (a,b)是最小的。
#include<bits/stdc++.h>
using namespace std;
int n,a,ans;
int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a;a>0?(a*=1):(a*=(-1));ans=gcd(ans,a);}
    cout<<ans;
}

并查集

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200005];
int find(int k){
    while(fa[k]!=k)k=fa[k]=fa[fa[k]];//循环版找爸爸
    return k;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int cn,cm,cz;
        cin>>cn>>cm>>cz;
        int a=find(cm),b=find(cz);
        if(cn==1){
            if(a>b)fa[a]=b;//按序号大小合并
            else fa[b]=a;
        }else{
            if(a==b)cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
}

快速排序

#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int read(){
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
void quick_sort(int l,int r){
    if(l>=r)return ;
    int mid=a[(l+r)>>1],i=l,j=r;
    while(i<=j){
        while(a[i]<mid)++i;//不能加‘=’不然会T
        while(a[j]>mid)--j;
        if(i<=j){//要特判
            swap(a[i],a[j]);
            ++i,--j;//注意注意
        }
    }
    if(l<j)quick_sort(l,j);//!!!
    if(r>i)quick_sort(i,r);//!!!
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    quick_sort(1,n);
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
}

素数筛

#include<bits/stdc++.h>
using namespace std;
int n,m,prime[100000005],ji;
bool bo[10000005];
int main(){
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        if(!bo[i])prime[++ji]=i;//不能加括号！！！，每次都要更新！！！
        for(int j=1;i*prime[j]<=n;j++){//记得是prime[j]*i,i和j换个位置
            bo[i*prime[j]]=1;
            if(i%prime[j]==0)break;//期中有其他因子的时候就退出来
        }
    }
    bo[1]=bo[0]=1;
    for(int i=1;i<=m;i++){
        int cn;cin>>cn;
        if(bo[cn])cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}
//当你n特别大比如1e12时我们可以这么求出这个数可以被分解成多少个质数：
#include<bits/stdc++.h>
using namespace std;
long long read()
{
    long long x=0,f=1;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')f=-1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
long long T,n,ans;
int main(){
    T=read();
    while(T--){
        n=read();
        ans=0;
        for(long long i=2;i*i<=n;++i)
            while(!(n%i)){
                n/=i;
                ans++;
            }
        if(n>1)ans++;
        if(ans==2)printf("Bob\n");
        else printf("Alice\n");
    }
    return 0;
}

快速幂

#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long m,n,mod;
ll quick(ll x,int y){//快速幂
    ll res=1;
    while(y){
        if(y&1)res=(ll)res*x%mod;
        x=(ll)x*x%mod; y>>=1;
    }return res;
}
int main(){
    cin>>m>>n>>mod;
    cout<<m<<"^"<<n<<" mod "<<mod<<"="<<quick(m,n)%mod;
}
或者你也可以这么写 下面是我早期写的版本
#include<iostream>
using namespace std;
long long b,p,k;
long long mod(long long x)
{
    if(x==0) return 1%k;
    long long y=x,s;
    bool bo=y%2;
    y/=2;
    s=mod(y);
    s*=s%k;
    if(bo==1) s*=b;
    return s%k;
}
int main(){

    cin>>b>>p>>k;
    cout<<b<<"^"<<p<<" mod "<<k<<"="<<mod(p);
}

三分法

#include<bits/stdc++.h>
#define eps 1e-6
using namespace std;
int n;
double l,r,a[20];
double f(double x){//秦九昭定理
    double s=0;
    for(int i=1;i<=n+1;i++)s=s*x+a[i];//巧妙的操作
    return s;
}
int main(){
    cin>>n>>l>>r;
    for(int i=1;i<=n+1;i++)cin>>a[i];//特别注意有n+1个值
    while(r-l>=eps){
        double k=(r-l)/3.0;
        double mid1=l+k,mid2=r-k;
        if(f(mid1)>f(mid2))r=mid2;
        else l=mid1;
    }
    printf("%.5lf",l);
}

矩阵快速幂

#include <bits/stdc++.h>
#define ll long long
#define m 1000000007
using namespace std;
inline ll gi(){
    register char ch=getchar();register ll x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
ll n,k;
struct node {
    ll mat[100][100];
}add,a,ans,mu,e,qk;
inline node mul(node x,node y){
    node mem=qk;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            for(register int h=1;h<=n;h++){
                mem.mat[i][j]=(mem.mat[i][j]+x.mat[i][h]*y.mat[h][j])%m;//记得加上原来的
            }
        }
    }
    return mem;
}
inline void quick(ll k){
    ans=e;
    while(k){
        if(k&1)ans=mul(ans,mu);
        mu=mul(mu,mu);
        k>>=1;
    }
}
int main(){
    cin>>n>>k;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            mu.mat[i][j]=a.mat[i][j]=gi();
        }
    }
    for(ll i=1;i<=n;i++){
        e.mat[i][i]=1;
    }
    quick(k);
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            printf("%lld ",ans.mat[i][j]);
        }
        printf("\n");
    }
    return 0;
}

乘法逆元

//法1(递推法)
#include<bits/stdc++.h>
using namespace std;
long long n,p,inv[3000001];
int main(){
    cin>>n>>p;
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(p-p/i)*inv[p%i]%p;
    }
    for(int i=1;i<=n;i++)printf("%d\n",inv[i]);
}
/*
递推求inv的解释：
设p=k*i+r;
则有k*i+r≡0(mod p)
为了把r^(-1)剥离出来两边同乘i^(-1)*r^(-1)
得到r^(-1)=-k*r^(-1);
k=p/i,r^(-1)=inv[p%i];
此时我们注意到这样乘起来是负数
所以我们用p减去他
*/

//法2(扩展欧几里得法)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p,inv[3000001],x,y;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1,y=0;return ;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        exgcd(i,p,x,y);
        x=(p+x%p)%p;
        cout<<x<<endl;
    }
}
/*
a*x≡c(mod p)
令t=x^(-1)
我们要求的就是
x*t≡1(mod p)
于是我们有
x*t+p*y=1
求t即可
*/

//法3(快速幂)
//即x^(p-2);
//由于这个方法只适用于x与p互质的情况，exgcd不仅比他快还适用所有情况 这里就不在赘述

NIM游戏

#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++){
            int ci;
            cin>>ci;
            ans^=ci;
        }
        if(ans)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

中国剩余定理

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100005],b[100005];
void  exgcd(int aa,int bb,int &x,int &y){
    if(!bb){x=1,y=0;return ;}
    exgcd(bb,aa%bb,y,x);
    y-=aa/bb*x;
}
int ksc(int aa,int bb,int mod){
    int re=0;
    while(bb){
        if(bb&1)re=(re+aa)%mod;
        bb>>=1,aa=(aa+aa)%mod;
    }
    return re;
}
void crt(){
    int ans=0;
    for(int i=1;i<=n;i++){
        int mi=m/b[i],x,y;
        exgcd(mi,b[i],x,y);//求出mi的逆元
        ans=(ans+ksc(ksc(x,mi,m)%m,a[i],m)%m)%m;
    }
    ans=(ans%m+m)%m;
    cout<<ans;
}
signed main(){
    cin>>n;m=1;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){cin>>b[i];a[i]=(a[i]%b[i]+b[i])%b[i];m*=b[i];}//吧a转换成正数并计算m
    crt();
}
/*
对于sum{ai*mi*mi^(-1)}的解释
xi≡ai*mi*mi^(-1)(mod bi)
xj≡aj*mj*mj^(-1)(mod bj)
当循环到j时由于mj=b1*b2*...*bj-1*bj+1*...*bn
故sum之后即为答案
*/

字符串类

manacher

//注意此算法求的是回文串，必须是连续的一段序列
//而回文序列则不必连续
#include<bits/stdc++.h>
using namespace std;
char s[31000005];
int r[31000005],len;//r是包括自己向右扩展的最大半径
int main(){
    s[0]=s[1]='#';len=2;
    while(cin>>s[len]){
        s[++len]='#';++len;
    }
    --len;//在每个字符之间插板子
    r[0]=r[1]=1;
    int maxr=1,pos=0,ans=0;
    for(int i=1;i<=len;i++){//必须一个一个更新 因为可能答案是关于‘#’对称的。。。
        if(i<maxr){
            r[i]=min(r[(pos<<1)-i],maxr-i);//两种情况
        }else r[i]=1;
        for(;s[i-r[i]]==s[i+r[i]];++r[i]);//左右拓展
        if(maxr<i+r[i])pos=i,maxr=i+r[i];
        ans=max(ans,r[i]);
    }
    cout<<ans-1;//半径减去‘#’的个数
}

KMP

#include<bits/stdc++.h>
using namespace std;
int n,m,lena,lenb,nex[1000005];
char a[1000005],b[1000005];
int main(){
    scanf("%s%s",a+1,b+1);
    lena=strlen(a+1);
    lenb=strlen(b+1);
    int j=0;
    for(int i=2;i<=lenb;i++){
        while(j&&b[i]!=b[j+1])j=nex[j];
        if(b[i]==b[j+1])++j;
        nex[i]=j;
    }
    j=0;
    for(int i=1;i<=lena;i++){
        while(j&&b[j+1]!=a[i])j=nex[j];
        if(b[j+1]==a[i])++j;
        if(j==lenb){cout<<i-lenb+1<<endl;j=nex[j];}
    }
    for(int i=1;i<=lenb;i++)cout<<nex[i]<<" ";
    return 0;
}

杂项

ST表

//交LG的话记得加快读~~~
#include<bits/stdc++.h>
using namespace std;
int n,m,f[5000005][20];//f[i][j]为从i开始(2^j)-1的最大值
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>f[i][0];
    }
    for(int k=1;k<=20;k++){
        for(int i=1;i<=n-(1<<k)+1;i++){
            f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);//将区间拆成两半[i,i+2^j-1]和[i+2^(j-1),j-1]
        }
    }//如果是先枚举i那么在f[1][2]的时候会不知道f[2][1]的值
    for(int i=1;i<=m;i++){
        int le,ri;cin>>le>>ri;
        int t=log(ri-le+1)/log(2);//换底公式即log以2为ri-le+1的对数，找到最大的k
        printf("%d\n",max(f[le][t],f[ri-(1<<t)+1][t]));//左右两半区间查询
        //记得+1如1~5:log2(5)=2,f[1][2]为1~4的max而后半段要2~5，5-2^2=1所以要加1！！！
    }
}

线段树1

#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[100005];
struct node{
    ll sum,add;
    ll l,r;
}t[1000005];
ll read(){
    ll x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
void build(ll p,ll l,ll r){
    t[p].l=l,t[p].r=r;
    if(l==r){t[p].sum=a[l];return ;}
    ll mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}


void spread(ll p){
    if(t[p].add){
        t[p*2].sum+=(ll)t[p].add*(t[p*2].r-t[p*2].l+1);//ll!!!
        t[p*2+1].sum+=(ll)t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].add+=t[p].add;//别忘了
        t[p*2+1].add+=t[p].add;
                t[p].add=0;
    }
}
void add(ll p,ll l,ll r,ll k){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].add+=k;
        t[p].sum+=(ll)k*(t[p].r-t[p].l+1);//不要忘了
        return ;
    }
    spread(p);
    ll mid=(t[p].l+t[p].r)>>1;//记得是在这个节点记录的区间的中点
    if(l<=mid)add(p*2,l,r,k);//注意是l<=mid否则当修改区间横跨了mid时就不会进行任何操作
    if(r>mid)add(p*2+1,l,r,k);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;//还要记得修改sum
}
ll ask(ll p,ll l,ll r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].sum;
    }
    spread(p);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    ll mid=(t[p].r+t[p].l)>>1;
    ll val=0;
    if(l<=mid)val+=ask(p*2,l,r);
    if(r>mid)val+=ask(p*2+1,l,r);
    return val;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    for(ll i=1;i<=m;i++){
        ll ty=read();
        if(ty==1){
            ll cn=read(),cm=read(),cw=read();
            add(1,cn,cm,cw);
        }
        else {
            ll cn=read(),cm=read();
            cout<<ask(1,cn,cm)<<endl;
        }
    }
}

线段树2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,a[1000005],mod;
struct node{
    ll sum,l,r,mu,add;
}t[1000005];
ll read(){
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
void build(ll p,ll l,ll r){
    t[p].l=l,t[p].r=r;t[p].mu=1;
    if(l==r){t[p].sum=a[l]%mod;return ;}
    ll mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void spread(ll p){


    t[p*2].sum=(ll)(t[p].mu*t[p*2].sum+((t[p*2].r-t[p*2].l+1)*t[p].add)%mod)%mod;
    t[p*2+1].sum=(ll)(t[p].mu*t[p*2+1].sum+(t[p].add*(t[p*2+1].r-t[p*2+1].l+1))%mod)%mod;

    t[p*2].mu=(ll)(t[p*2].mu*t[p].mu)%mod;
    t[p*2+1].mu=(ll)(t[p*2+1].mu*t[p].mu)%mod;

    t[p*2].add=(ll)(t[p*2].add*t[p].mu+t[p].add)%mod;
    t[p*2+1].add=(ll)(t[p*2+1].add*t[p].mu+t[p].add)%mod;

    t[p].mu=1,t[p].add=0;
}
void add(ll p,ll l,ll r,ll k){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].add=(t[p].add+k)%mod;
        t[p].sum=(ll)(t[p].sum+k*(t[p].r-t[p].l+1))%mod;//只要加上增加的就好
        return ;
    }
    spread(p);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)add(p*2,l,r,k);
    if(mid<r)add(p*2+1,l,r,k);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;

}
void mu(ll p,ll l,ll r,ll k){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].add=(t[p].add*k)%mod;//比较重要的一步,add要在这里乘上k,因为后面可能要加其他的数而那些数其实是不用乘k的
        t[p].mu=(t[p].mu*k)%mod;
        t[p].sum=(t[p].sum*k)%mod;
        return ;
    }
    spread(p);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)mu(p*2,l,r,k);
    if(mid<r)mu(p*2+1,l,r,k);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
ll ask(ll p,ll l,ll r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].sum;
    }
    spread(p);
    ll val=0;
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)val=(val+ask(p*2,l,r))%mod;
    if(mid<r)val=(val+ask(p*2+1,l,r))%mod;
    return val;
}
int main(){
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int ty=read();
        if(ty==1){
            ll cn=read(),cm=read(),cw=read();
            mu(1,cn,cm,cw);
        }else if(ty==2){
            ll cn=read(),cm=read(),cw=read();
            add(1,cn,cm,cw);
        }else {
            ll cn=read(),cm=read();
            cout<<ask(1,cn,cm)<<endl;
        }
    }
}

悬线法

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],l[1005][1005],r[1005][1005],up[1005][1005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char ch;cin>>ch;
            if(ch=='F')a[i][j]=1;
            r[i][j]=l[i][j]=j,up[i][j]=1;
        }

    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(a[i][j]==a[i][j-1]&&a[i][j]==1)l[i][j]=l[i][j-1];
        }
        for(int j=m-1;j>=1;j--){
            if(a[i][j]==a[i][j+1]&&a[i][j]==1)r[i][j]=r[i][j+1];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1&&a[i][j]==a[i-1][j]&&a[i][j]==1){//是>1才进去但是i=1时还是要做的
                r[i][j]=min(r[i][j],r[i-1][j]);
                l[i][j]=max(l[i][j],l[i-1][j]);
                up[i][j]=up[i-1][j]+1;
            }
            ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
        }
    }
    cout<<ans;
}

哈夫曼树

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
priority_queue<pair<int,int> >dui;
signed main(){
    cin>>n>>m;int w;
    for(int i=1;i<=n;i++){
        cin>>w;
        dui.push(make_pair(-w,-1));
    }
    while((dui.size()-1)%(m-1))dui.push(make_pair(-0,-1));//最后一次合并要满足=0 因为每次合并要减少k-1个节点要将n个节点合并成1个
    //题解里的解释：因为每次都是将k个节点合并为1个（减少k-1个），一共要将n个节点合并为1个，如果（n-1）%（k-1）！=0 则最后一次合并时不足k个。也就表明了最靠近根节点的位置反而没有被排满，因此我们需要加入k-1-（n-1）%（k-1）个空节点使每次合并都够k个节点（也就是利用空节点将其余的节点挤到更优的位置上）。
    int ans=0;
    while(dui.size()>=m){
        int re=0,h=-0;
        for(int i=1;i<=m;i++){
            int x=dui.top().first,y=dui.top().second;dui.pop();
            re+=x;
            h=min(h,y);
        }
        ans+=re;
        dui.push(make_pair(re,h-1));
    }
    cout<<-ans<<endl<<-dui.top().second-1;
}

LIS

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],f[100005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];f[i]=0x7ffffff;
    }
    int len=0;f[0]=0;
    for(int i=1;i<=n;i++){
        if(f[len]<a[i])f[++len]=a[i];
        else {
            int l=1,r=len;
            while(l<r){
                int mid=(l+r)>>1;
                if(a[i]<f[mid])r=mid;//因为要将a[i]插入到f中，且插入位置保证f[mid]>=a[i]，所以>a[i]也可能是答案
                else l=mid+1;
            }
            f[l]=a[i];
        }
    }
    cout<<len;
}

LCS

#include<bits/stdc++.h>
using namespace std;
int n,f[100001],a[100001],b[100001],ma[100001];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];ma[a[i]]=i,f[i]=0x7fffffff;
    }
    for(int i=1;i<=n;i++)cin>>b[i];
    f[0]=0;
    int len=0;
    for(int i=1;i<=n;i++){
        if(f[len]<ma[b[i]])f[++len]=ma[b[i]];//比队尾还大
        else {
            int l=1,r=len;
            while(l<r){
                int mid=(l+r)>>1;
                if(f[mid]<ma[b[i]])l=mid+1;
                else r=mid;
            }
            f[l]=ma[b[i]];
        }
    }
    cout<<len;
}
/*由于数据过大我们在时间和空间上都不能像下面那样做
那怎么办呢
我们发现既然是1到n的排列 那我们就可以把A离散化 这样我们就可以得到B在A序列中的编号
如果我们找到了一段编号序列的子序列，他是单调递增的，那么就表明对应元素在A和B中是从前往后排列的
这就是我们要的答案
差点忘了说 找这段单调递增的序列其实就是LIS哦
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005],b[2005],f[2005][2005];
inline int read(){
    register int x=0;register char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
int main(){
    freopen("lcis.in","r",stdin);
    freopen("lcis.out","w",stdout);
    cin>>n>>m;
    for(register int i=1;i<=n;++i){
        a[i]=read();
    }
    for(register int i=1;i<=m;++i){
        b[i]=read();
    }
    register int maxn=0;
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            if(a[i]==b[j]){
                for(register int k=1;k<j;++k){
                    f[i][j]=max(f[i][j],f[i][k]+1);
                }
                maxn=max(maxn,f[i][j]);
            }else f[i][j]=f[i-1][j];
        }
    }
    cout<<maxn<<endl;
}
/*
fij表示到ai和bj的位置且ai必选
*/

LCIS

#include<bits/stdc++.h>
using namespace std;
int n,m,a[505],b[505],g[505][505],f[505][505];
void path(int i,int j){
    if(j==0)return ;
    path(g[i][j],j-1);
    if(g[i][j]!=i){
        printf("%d ",a[i]);
    }
}
int main(){
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;for(int j=1;j<=m;j++)cin>>b[j];
    int maxn=0,x=0,y=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                f[i][j]=1;
                for(int k=1;k<i;k++){
                    if(a[k]<a[i]){
                        if(f[i][j]<f[k][j-1]+1){//如果是f[k][j]由于a[1~i]与b[j]不匹配所以这样是错的
                            f[i][j]=f[k][j-1]+1;
                            g[i][j]=k;
                        }
                    }
                }
                if(maxn<f[i][j]){maxn=f[i][j],x=i,y=j;}
            }else{
                f[i][j]=f[i][j-1];
                g[i][j]=i;
            }

        }
    }
    cout<<maxn<<endl;
    path(x,y);
    cout<<endl;
}
/*
输出的递归函数path应有两个参数(i,j),表示当前在数组A中位置是i,在数组B中位置是j.
我们沿着f[i][j]转移时的路径递归,也就是path(i-1,g[i][j]).
若g[i][j]==j,则说明这里是没有增加LCIS长度的转移,
应该沿着f[i][j]转移时的路径继续递归,但不输出.直到g[i][j]!=j就输出B[j].
*/

后序遍历

#include<bits/stdc++.h>
using namespace std;
char q[1000005],z[1000005];
int len;
int find(char k){
    for(int i=1;i<=len;i++)if(q[i]==k)return i;
}
void dfs(int l1,int r1,int l2,int r2){
    int m=find(z[r2]);
    cout<<q[m];
    if(m>l1)dfs(l1,m-1,l2,r2-r1+m-1);//有左子树
    if(r1>m)dfs(m+1,r1,l2+m-l1,r2-1);
}
//r2-(r1-m+1)
//r2-r1+m-1
//l2+(m-r1)
//l2+m-r1
int main(){
    scanf("%s",q+1);scanf("%s",z+1);
    len=strlen(q+1);
    dfs(1,len,1,len);
}

后缀表达式

#include<bits/stdc++.h>
using namespace std;
char a[1005];
int sum,k;
stack <int> stk;
int main()
{
    gets(a);
    for(int i=0;a[i]!='@';i++)
    {
        if(a[i]=='.')
        {
            sum=0,k=1;
            for(int j=i-1;j>=0&&a[j]>='0'&&a[j]<='9';j--) sum=sum+(a[j]-48)*k,k*=10;
            stk.push(sum);
            continue;
        }
        if(a[i]>='0'&&a[i]<='9') continue;
        sum=stk.top();
        stk.pop();
        if(a[i]=='+') sum=stk.top()+sum;
        if(a[i]=='-') sum=stk.top()-sum;
        if(a[i]=='*') sum=stk.top()*sum;
        if(a[i]=='/') sum=stk.top()/sum;
        stk.pop();
        stk.push(sum);
    }
    printf("%d",stk.top());
    return 0;
}

中缀表达式转后缀表达式

#include<bits/stdc++.h>
#define M 10007
using namespace std;
int n;
char ss[10000005];
stack<char>dui;
int main(){
    cin>>n;
    scanf("%s",ss   +1);
    string s=".";
    for(int i=1;i<=n;i++){
        if(ss[i]=='('||ss[i]=='*'){
            dui.push(ss[i]);
        }
        if(ss[i]=='+'){
            while(dui.size()&&dui.top()=='*'){//直到找到优先级更低的符号
                s+=dui.top();
                dui.pop();
            }
            dui.push('+');
        }
        if(ss[i]==')'){
            while(dui.size()&&dui.top()!='('){
                s+=dui.top();
                dui.pop();
            }
            dui.pop();
        }
        if(ss[i]!='('&&ss[i]!=')'){
            s+='.';
        }
    }
    while(dui.size())s+=dui.top(),dui.pop();
    cout<<s<<endl;
}
/*
8
+*+(*+)*

下面的话来自题解区：

转换过程需要用到栈，具体过程如下：

1）如果遇到操作数，我们就直接将其输出。

2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。

4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。

5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

备注：本题中我们用一个"."来代表数字。扫描整个表达式（读入的字符串），如果当前位置不是括号（既不是左括号也不是右括号），就在后缀表达式里填一个"."表示这里应有一个数字。


*/

高精度

高精度加法

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000000
using namespace std;
char d[maxn],e[maxn];
int a[maxn],b[maxn],c[maxn];
int main(){
    scanf("%s%s",&d,&e);
    int lena=strlen(d),lenb=strlen(e),lenc=lena>lenb?lena:lenb,jin=0;
    for(int i=0;i<lena;i++){
        a[lena-i]=d[i]-48;
    }
    for(int i=0;i<lenb;i++){
        b[lenb-i]=e[i]-48;
    }
    for(int i=1;i<=lenc;i++){
        c[i]=a[i]+b[i]+jin;
        jin=c[i]/10;
        c[i]%=10;
    }
    lenc++;
    c[lenc]=jin;
    while(!c[lenc]&&lenc>1){
        lenc--;
    }
    for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
    return 0;
}

高精度减法

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000000
using namespace std;
char d[maxn],e[maxn];
int a[maxn],b[maxn],c[maxn],f[maxn];
int main(){
    scanf("%s%s",&d,&e);
    if(strcmp(d,e)==0){
        cout<<"0";
        return 0;
    }
    int lena=strlen(d),lenb=strlen(e);

    for(int i=0;i<lena;i++){
        a[lena-i]=d[i]-48;
    }
    while(!a[lena]){
        lena--;
    }
    for(int i=0;i<lenb;i++){
        b[lenb-i]=e[i]-48;
    }
    while(!b[lenb]){
        lenb--;
    }
    int lenc=lena>lenb?lena:lenb;
    if(memcmp(a,b,lenc)<0&&lena==lenb||(lena<lenb)){
        memcpy(f,a,sizeof(a)); memcpy(a,b,sizeof(b)); memcpy(b,f,sizeof(f));
        cout<<"-";
        int t=lena;
        lena=lenb;
        lenb=t;
    }
    lenc=lena>lenb?lena:lenb;

    for(int i=1;i<=lenc;i++){
        if(a[i]-b[i]<0){
            a[i]+=10;
            a[i+1]--;

        }
        c[i]=a[i]-b[i];

    }
    lenc++;
    while(!c[lenc]&&lenc>1){
        lenc--;
    }
    for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
    return 0;
}

高精度乘法

#include<iostream>
#include<cstring>
using namespace std;
int a[2005],b[2005],c[2005];
char a1[2005],b1[2005];
int main(){
    scanf("%s%s",&a1,&b1);
    int lena=strlen(a1),lenb=strlen(b1);
    for(int i=0;i<lena;i++) a[lena-i]=a1[i]-'0';
    for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0';
    for(int i=1;i<=lenb;i++){
        int jin=0;
        for(int j=1;j<=lena;j++){
            c[i+j-1]=a[j]*b[i]+jin+c[i+j-1];
            jin=c[i+j-1]/10;
            c[i+j-1]%=10;
        }
        c[lena+i]=jin;
    }
    int lenc=lena+lenb;
    while(!c[lenc]&&lenc>1)lenc--;
    for(int i=lenc;i>=1;i--)printf("%d ",c[i]);
    return 0;
}

高精除以低精（附带出输出余数）

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[2005],b,c[2005],jin;
char a1[2005];
int main(){
    scanf("%s",&a1);
    cin>>b;
    int lena=strlen(a1);
    for(int i=0;i<lena;i++) a[i+1]=a1[i]-'0';//记得是从前往后处理
    for(int i=1;i<=lena;i++){
        c[i]=(jin*10+a[i])/b;
        jin=(jin*10+a[i])%b;
    }
    int lenc=1;
    while(!c[lenc]&&lenc<lena)lenc++;
    for(int i=lenc;i<=lena;i++)printf("%d",c[i]);
    cout<<endl<<jin;
    return 0;
}
//jin取的是前面的余数，把前面的余数拼到后面一起除

排序

选择排序

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[99999999],n;
void swap(int &l,int &k){
    int t=l;
    l=k;
    k=t;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int ji=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[ji])ji=j;
        }
        if(ji!=i)
//      {//或者这样也行
//          int t=a[i];
//          a[i]=a[ji];
//          a[ji]=t;
//      }
            swap(a[i],a[ji]);//要传址调用
    }
    cout<<endl;
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}

正版冒泡

#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=n-1;i>=1;i--){
        for(int j=0;j<=i;j++){
            if(a[j]>a[j+1]) swap(a[j],a[j+1]);
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}

盗版冒泡

#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
//  for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    for(int i=1;i<=n;i++){
//      int ji=0;
        for(int j=i+1;j<=n;j++){
            if(a[i]>a[j]) swap(a[i],a[j]);
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}

插排

#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n,i,j;
void yi(int p,int q)
{
    for(int h=q;h>p;h--)a[h]=a[h-1];
}
int main(){
    cin>>n;
    for( i=1;i<=n;i++)scanf("%d",&a[i]);
    for( i=2;i<=n;i++){//a[i]为需要插入的数
        for( j=i-1;j>=1;j--)//寻找插入点
            if(a[j]<a[i])break;
            if(j!=i-1){//需要将a[i]插入a[j]后
                int temp=a[i];
                yi(j+1,i);
                a[j+1]=temp;
            }
    }
    cout<<endl;
    for(i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}

桶排

#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n,ji;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&ji);
        a[ji]++;
    }
    for(int i=0;i<=n;i++){
        while(a[i]){
            printf("%d ",i);
            a[i]--;
        }
    }
    return 0;
}

三数取中+插排版 快排

#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],n;
void cha(int p,int q)//p<q
{
    int f,g;
    for( f=p;f<=q;f++){
        for( g=f-1;g>=p;g++)if(a[g]<a[f])break;
        if(g!=f-1){
            int temp=a[f];
            for(int s=f;s>g;s--)a[s]=a[s-1];
            a[g+1]=temp;
        }
    }
}
void quick(int le,int ri)
{
    if(le>=ri)return;
    if(ri-le>=10)cha(le,ri);
    int t=(le+ri)/2,mid,x=le,y=ri;
    if(a[le]<a[t]){
        if(a[t]>a[ri]){
            int w=a[t];
            a[t]=a[ri];
            a[ri]=w;
        }
    }
    if(a[le]>a[t]){
        int w=a[t];
        a[t]=a[le];
        a[le]=w;//a[le]<a[t]
        if(a[t]>a[ri]){
            int w=a[t];
            a[t]=a[ri];
            a[ri]=w;
        }
    }
    mid=a[t];
    do{
        while(a[x]<mid)x++;
        while(a[y]>mid)y--;
        if(x<=y){
            int w=a[x];
            a[x]=a[y];
            a[y]=w;
            x++;
            y--;
        }
    }while(x<=y);
    if(le<y)quick(le,y);
    if(x<ri)quick(x,ri);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    quick(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
}
    return 0；

归并排序

#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999],b[99999999],n;
void gui(int le,int ri)
{
    if(le==ri)return;
    int mid=(le+ri)/2,x=le,y=mid+1,k=le;
    gui(le,mid);
    gui(mid+1,ri);
    while(x<=mid&&y<=ri){
        if(a[x]<a[y]){
            b[k++]=a[x++];
        }
        else{
            b[k++]=a[y++];
        }
    }
    while(x<=mid){
        b[k++]=a[x++];
    }
    while(y<=ri){
        b[k++]=a[y++];
    }
    for(int g=le;g<=ri;g++)a[g]=b[g];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    gui(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
}

测试数据生成器

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
int main(){
    freopen("testdata.in","w",stdout);
    srand((unsigned)time(NULL));
    for(int i=1;i<=10000;i++)
        printf("%d ",rand());
    return 0；
}
01-23 11:40
Powered by LMLPHP ©2024 高精 0.069017