清北学堂day1考试代码

1.内容敏感图像压缩

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int data[3010][3010];
int dp[3010][3010];
int n, m, ans=0x7fffffff;
inline void read(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            scanf("%d", &data[i][j]);
}
inline void solve(){
    for(int i=1; i<=m; ++i)    dp[1][i]=data[1][i];    
    for(int i=2; i<=n; ++i){
        dp[i][1]=data[i][1]+min(dp[i-1][m], min(dp[i-1][1], dp[i-1][2]));
        for(int j=2; j<=m-1; ++j)
            dp[i][j]=data[i][j]+min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1]));
        dp[i][m]=data[i][m]+min(dp[i-1][m-1], min(dp[i-1][m], dp[i-1][1]));
    }
    for(int i=1; i<=m; ++i)    ans=min(ans, dp[n][i]);
    cout << ans << endl;
}
int main(void){
    freopen("compress.in" , "r", stdin);
    freopen("compress.out", "w", stdout);
    read();
    solve();
    return 0;
}

2.划水

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int g[210][210];
int n, m;
double lges=-99999999;
const int maxw=0x3fffffff;
void show(){
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j)
            cout << g[i][j] << " ";
        cout << endl;
    }
}
int main(void){
    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for(int i=1; i<=n; ++i)    g[i][i]=0;
    for(int i=1; i<=m; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[v][u]=g[u][v]=min(g[u][v], w);
    }
    for(int k=1; k<=n; ++k)
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                g[i][j]=min(g[i][j], g[i][k]+g[k][j]);        
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            lges=max(lges, (double)g[i][j]);
    printf("%.2f\n", lges/2);
    return 0;        
}

3.复习

#include<cstdio>
#include<iostream>
using namespace std;
struct tree{
    int b, e, m, sum;
    tree *l, *r;
};
inline bool ifin(int w, tree* in){
    return w>=in->b&&w<=in->e;
}
void show(tree* in){
    cout << in->sum << endl;
    if(in->l!=NULL){
        show(in->l);
        show(in->r);
    }
}
void build(int inb, int ine, tree* in){
    in->b=inb;
    in->e=ine;
    in->m=(in->b+in->e)/2;
    in->sum=0;
    if(in->b==in->e)    in->l=in->r=NULL;
    else{
        in->l=new tree;
        in->r=new tree;
        build(in->b, in->m, in->l);
        build(in->m+1, in->e, in->r);
    }
}
void add(int w, int p, tree* in){
    in->sum+=w;
    if(in->l==NULL)    return ;
    if(ifin(p, in->l))    add(w, p, in->l);
    else                add(w, p, in->r);
}
int change(int p, int v, tree* in){
    int cc=0;
    if(in->l==NULL)    {
        cc=v-in->sum;    
        in->sum=v;
        return cc;
    }
    if(ifin(p, in->l))    cc=change(p, v, in->l);
    else                cc=change(p, v, in->r);
    in->sum+=cc;
    return cc;
}
int queo(int &f, int &t, tree* in){
    if(f<=in->b&&t>=in->e){
        f=in->e;
        return in->sum;
    }
    if(in->l==NULL)    return 0;
    return queo(f, t, in->l)+queo(f, t, in->r);
}
int n, k;
int main(void){
    freopen("review.in", "r", stdin);
    freopen("review.out", "w", stdout);
    tree* head;
    head=new tree;
    scanf("%d", &n);
    build(1, n, head);
    for(int i=1; i<=n; ++i)    {
        int w;
        scanf("%d", &w);
        add(w, i, head);
    }
    scanf("%d", &k);
    int f, t;
    for(int i=1; i<=k; ++i){
        int op;
        scanf("%d", &op);
        if(op==1){
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            for(int i=l; i<=r; ++i){
                f=i, t=i;
                change(i, queo(f, t, head)%x, head);
            }
        }
        else if(op==2){
            int p, v;
            scanf("%d%d", &p, &v);
            change(p, v, head);
        }
        else{
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", queo(l, r, head));
        }
    }
    return 0;
}