头像

cz_yxc


访客:31

离线:1小时前



cz_yxc
5天前

归并排序板子题

归并排序的原理许多dalao都讲过了,我这里不再赘述
题目名字叫做归并排序,大家就不要用快排骗AC了/doge
(虽然我试了一下快排也可以过
这里主要是提供一种简洁的码风

#include<bits/stdc++.h>
#define N 100010
using namespace std;
template<typename T>inline void read(T &n){
    int w=1;n=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)){n=(n<<1)+(n<<3)+(ch&15);ch=getchar();}
    n*=w;
}
int c[N],now[N];//c数组是要排序的数组,now数组记录此次操作需要改变的数组
inline void merge(int l,int r){
    int mid=(l+r)>>1;int i=l,j=mid+1,p=l;
    while(i<=mid&&j<=r){
        if(c[i]>c[j]){
            now[p++]=c[j++];
        }else now[p++]=c[i++];
    }
    while(i<=mid)now[p++]=c[i++];
    while(j<=r)now[p++]=c[j++];
    for(int i=l;i<=r;++i)c[i]=now[i];
}
inline void mergesort(int l,int r){
    if(l>=r)return;
    int mid=(l+r)>>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    merge(l,r);
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int n;read(n);
    for(int i=1;i<=n;++i)read(c[i]);
    mergesort(1,n);
    for(int i=1;i<=n;++i)printf("%d ",c[i]);
    return 0;
}

注:该代码对于洛谷用户jhknmj_ZzDJR多有借鉴




cz_yxc
14天前
#include<bits/stdc++.h>
#define N 1010
using namespace std;
template<typename T>inline void read(T &n){
    int w=1;n=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)){n=(n<<1)+(n<<3)+(ch&15);ch=getchar();}
    n*=w;
}
char a[N],b[N];
int f[N][N];
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int n,m;read(n);read(m);
    for(int i=1;i<=n;++i){
        a[i]=getchar();
    }
    getchar();
    for(int i=1;i<=m;++i){
        b[i]=getchar();
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]){
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        }
    }printf("%d\n",f[n][m]);
    return 0;
}


活动打卡代码 AcWing 282. 石子合并

cz_yxc
14天前

跟着y总在B站上学的状压DP!

一道板子题

#include<bits/stdc++.h>
#define N 310
#define INF 0x3f3f3f3f
using namespace std;
template<typename T>inline void read(T &n){
    int w=1;n=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)){n=(n<<1)+(n<<3)+(ch&15);ch=getchar();}
    n*=w;
}
int s[N],f[N][N];
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int n;read(n);
    for(int i=1;i<=n;++i){
        read(s[i]);s[i]+=s[i-1];
    }
    for(int len=2;len<=n;++len){
        for(int i=1;i+len-1<=n;++i){
            int j=i+len-1;
            f[i][j]=INF;
            for(int k=i;k<j;++k){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}