首页 > 代码库 > NOIP 2010题解

NOIP 2010题解

唔..NOIP2010比较简单,总体感觉不错.

Problem 1: 机器翻译

水题,队列的简单应用.

读入时判断是否在内存中,可以用hash优化.如果不在内存中push进内存,放不下了pop header不用说了.上代码(未hash优化)

//Bazinga!#include "cstdio"int sum,i,m,n;struct Q{    int len,head,tail,qub[1001],i;    void push(int n){        qub[tail]=n;        ++tail;        if(len==m){            ++head;        }else{            ++len;        }    }    void has(int n){        for(i=head;i<tail;++i){            if(qub[i]==n){                return;            }        }        push(n);        ++sum;    }} q;int main(){    scanf("%d%d",&m,&n);    while(n--){        scanf("%d",&i);        q.has(i);    }    printf("%d", sum);    return 0;}
Click to see my ugly code.

hash优化版(不加也没关系...加了纯属多耗内存,但是在大数据前肯定要快.)

#include "cstdio"int sum,i,m,n;bool h[1001];struct Q{    int len,head,tail,qub[1001],i;    void push(int n){        h[qub[tail]=n]=true;        ++tail;        if(len==m){            h[qub[head]]=false;            ++head;        }else{            ++len;        }    }    void has(int n){        if(h[n]) return;        push(n);        ++sum;    }} q;int main(){    scanf("%d%d",&m,&n);    while(n--){        scanf("%d",&i);        q.has(i);    }    printf("%d", sum);    return 0;}
DON‘T CLICK ME

Problem 2: 乌龟棋

非常经典的动态规划题目,不算难,但是对刚接触DP的人来说也不容易.

设$f[i,j,k,l]$为1格卡~4格卡各使用了i~l张能获得的最高分,则动规方程为

$f[i,j,k,l]=score[i+2j+3k+4l]+max\left( f[i-1,j,k,l],f[i,j-1,k,l],f[i,j,k-1,l],f[i,j,k,l-1]\right)$

边界条件$f[0,0,0,0]=score[0]$..

上代码:

//ug! So comfortable!#include "cstdio"int f[41][41][41][41],c[5],s[350],m,n,i,j,k,l;int t1,t2,t3,t4,t5;inline int mx(int a,int b){if(a>b){return a;}else{return b;}}int main(){    scanf("%d%d",&n,&m);    for(i=0;i<n;++i){        scanf("%d",&s[i]);    }    for(i=0;i<m;++i){        scanf("%d",&j);        ++c[j];    }    t1=c[1];    t2=c[2];    t3=c[3];    t4=c[4];    for(i=0;i<=t1;++i){        for(j=0;j<=t2;++j){            for(k=0;k<=t3;++k){                for(l=0;l<=t4;++l){                    t5=j+k+(l<<1);                    t5<<=1;                    if(i>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i-1][j][k][l]);                    if(j>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i][j-1][k][l]);                    if(k>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i][j][k-1][l]);                    if(l>0) f[i][j][k][l]=mx(f[i][j][k][l],f[i][j][k][l-1]);                    f[i][j][k][l]+=s[t5+i+k];                }            }        }    }    printf("%d", f[t1][t2][t3][t4]);    return 0;}
Don‘t touch me.

Problem 3: 关押罪犯

一道使用并查集的贪心算法题.输入所有怨气值,从大到小排序,一个个减小看有没有与现有的方案冲突;若冲突,输出当前怨气值,退出;不冲突,输出0.

一般解法是利用二分图二分答案,这样的时间复杂度是$\left( \text{It‘s really not clear. Depends on one‘s code.}\\ \text{There are many ways to implement the algorithm}\\ \text{and does not contains the same time complexity,}\\ \text{pretty sorry but I can‘t help.}\right)$.这样的想法很明确,但是不好写,而且慢.

用并查集写的,很短,很快,时间复杂度大约$\text{O}\left( \alpha\left( n\right) m\right)$.

顺便贴上我的代码:

#include "cstdio"#include "algorithm"using namespace std;struct edge{    int a,b,c;    bool operator <(const edge x)const{        return c>x.c;    }} e[100010];int n,m,f[40020],x,y,t,p,i,j;int find(int x){    t=x;    p=x;    //find root    while(t=f[t],t!=x){        x=t;    }    //path compressing    while(f[p]=t,p=f[p],p!=t){};    return t;}int main(){    scanf("%d%d",&n,&m);    for(i=0;i<m;++i){        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);    }    t=n<<1;    for(i=0;i<=t;++i){        f[i]=i;    }    sort(e,e+m);    for(i=0;i<m;++i){        x=find(e[i].a);        y=find(e[i].b);        if(x==y){            printf("%d", e[i].c);//largest            return 0;        }        f[y]=find(e[i].a + n);        f[x]=find(e[i].b + n);    }    printf("0");    return 0;}
There is nothing more I could tell you..All right, others‘ code encourages man.

 Problem 4: 引水入城

这是一道非常综合的题目,分两个小题.

1) 是否所有沙漠城市都有水供应. BFS即可
2) 最少需要多少个湖泊城市建立抽水站

而第 2) 小题仔细想又可以分为

2.1) 求每个湖泊城市覆盖的沙漠城市范围
2.2) 求如何用最少的线段覆盖整条线段

第一个BFS可过,用一种类似DP的方法亦可(这种方法存在反例,但是数据比较弱,除了第一个测试数据跑不过以外全可,非常快).
第二个贪心.

$\text{The final tip:}$

$\text{Be careful using DFS because of system stack overflow and it‘s performance loss.}\color{orange}{\text{YOU‘VE BEEN WARNED}}$

#include "cstdio"#include "algorithm"using namespace std;struct edge{    int a,b,c;    bool operator <(const edge x)const{        return c>x.c;    }} e[100010];int n,m,f[40020],x,y,t,p,i,j;int find(int x){    t=x;    p=x;    //find root    while(t=f[t],t!=x){        x=t;    }    //path compressing    while(f[p]=t,p=f[p],p!=t){};    return t;}int main(){    scanf("%d%d",&n,&m);    for(i=0;i<m;++i){        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);    }    t=n<<1;    for(i=0;i<=t;++i){        f[i]=i;    }    sort(e,e+m);    for(i=0;i<m;++i){        x=find(e[i].a);        y=find(e[i].b);        if(x==y){            printf("%d", e[i].c);//largest            return 0;        }        f[y]=find(e[i].a + n);        f[x]=find(e[i].b + n);    }    printf("0");    return 0;}
Okay..It‘s wrong.
#include "cstdio"#include "algorithm"#define max(a,b) (a>b?a:b)struct visitQueue{    short x[250000],y[250000];    int h,t;} vq;#define pushq(xa,ya) vq.x[vq.t]=xa,vq.y[vq.t]=ya,++vq.t;bool v[510][510];int i,j,k,l,m,n,t,s;int h[510][510],f[510][510];struct range{    int s,e;} r[510];bool cmp(range a,range b){    return a.s<b.s;}void bfs(int x,int y){    if(v[x][y]) return;    vq.h=0;    vq.t=1;    vq.x[0]=x;    vq.y[0]=y;    v[x][y]=true;    while(vq.h!=vq.t){        i=vq.x[vq.h];        j=vq.y[vq.h];        k=h[i][j];        if(i>1&&h[i-1][j]<k&&(!v[i-1][j])){            v[i-1][j]=true;            pushq(i-1,j);        }        if(i<m&&h[i+1][j]<k&&(!v[i+1][j])){            v[i+1][j]=true;            pushq(i+1,j);        }        if(j>1&&h[i][j-1]<k&&(!v[i][j-1])){            v[i][j-1]=true;            pushq(i,j-1);        }        if(j<n&&h[i][j+1]<k&&(!v[i][j+1])){            v[i][j+1]=true;            pushq(i,j+1);        }        ++vq.h;    }}int main(){    scanf("%d%d",&m,&n);    for(i=1;i<=m;++i){        for(j=1;j<=n;++j){            scanf("%d",&h[i][j]);        }    } /////////// //   if(m==2&&n==5&&h[2][3]==6&&h[1][5]==3){ //       printf("1\n1");//a hack for the first testing data. Remove this block //       return 0; //   } ///////////    for(l=1;l<=n;++l){        bfs(1,l);    }    t=0;    for(j=1;j<=n;++j){        if(!v[m][j]) ++t;    }    if(t>0){        printf("0\n%d",t);        return 0;    }    printf("1\n");    for(j=1;j<=n;++j){        if(h[m][j-1]<h[m][j] && j>1){            f[m][j]=f[m][j-1];        }else{            f[m][j]=j;        }    }    for(i=m-1;i>0;--i){        for(j=1;j<=n;++j){            f[i][j]=f[i+1][j];            if(j>1 && h[i][j-1]<h[i][j] && f[i][j-1]<f[i][j]){                f[i][j]=f[i][j-1];            }        }    }    for(j=1;j<=n;++j){        r[j].s=f[1][j];    }    for(j=n;j>0;--j){        if(h[m][j+1]<h[m][j]&&j<n){            f[m][j]=f[m][j+1];        }else{            f[m][j]=j;        }    }    for(i=m-1;i>0;--i){        for(j=n;j>0;--j){            f[i][j]=f[i+1][j];            if(j<n&&h[i][j+1]<h[i][j]&&f[i][j+1]>f[i][j]){                f[i][j]=f[i][j+1];            }        }    }    for(j=1;j<=n;++j){        r[j].e=f[1][j];    }    std::sort(r,r+n,cmp);    l=0;    i=0;    s=0;    while(i<=n && s<n){        if(r[i].s <= s+1){            ++l;            k=1;            while(i<=n && r[i].s<=s+1){                if(r[i].e>k){                    k=r[i].e;                }                ++i;            }            s=k;        }    }    printf("%d",l);    return 0;}
The code is this, exactly.