NOIP2010题解

显然原来都写过，都重新写一遍。

机器翻译 translate

一道很容易的模拟题，直接使用一个队列维护一下顺序就好了。

#include
    
     #include
     
      #include
      
       using namespace std;inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}bool vis[1050];int Q[1050],h,t,ans,n,m;int main(){    m=read();n=read();h=1;t=0;    for(int i=1;i<=n;++i)    {        int x=read();if(vis[x])continue;        Q[++t]=x;++ans;vis[x]=true;        if(t-h+1>m)vis[Q[h++]]=false;    }    printf("%d\n",ans);    return 0;}
      
     
    

乌龟棋 tortoise

一个不难想的\(dp\)是设\(f[i][a1][a2][a3][a4]\)表示当前在\(i\)位置，四种卡牌分别用的张数为\(a1,a2,a3,a4\)时的最大收益。不难发现\(i\)可以通过后面四个数算出来，显然是一个多余状态，去掉后直接\(dp\)即可。

#include
    
     #include
     
      #include
      
       using namespace std;#define MAX 400void cmax(int &x,int y){if(x
       
        '9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int n,m;int a[MAX],b[5];int f[45][45][45][45];int main(){    n=read();m=read();    for(int i=1;i<=n;++i)a[i]=read();    for(int i=1;i<=m;++i)b[read()]+=1;    memset(f,-63,sizeof(f));    f[0][0][0][0]=a[1];    for(int i=0;i<=b[1];++i)        for(int j=0;j<=b[2];++j)            for(int k=0;k<=b[3];++k)                for(int l=0;l<=b[4];++l)                {                    int s=1*i+2*j+3*k+4*l+1;                    if(i)cmax(f[i][j][k][l],f[i-1][j][k][l]+a[s]);                    if(j)cmax(f[i][j][k][l],f[i][j-1][k][l]+a[s]);                    if(k)cmax(f[i][j][k][l],f[i][j][k-1][l]+a[s]);                    if(l)cmax(f[i][j][k][l],f[i][j][k][l-1]+a[s]);                }    printf("%d\n",f[b[1]][b[2]][b[3]][b[4]]);    return 0;}
       
      
     
    

关押罪犯 prison

很妙的题目，如果没有做过类似题目的话自己基本不可能做出来。

不难想到的一点是这样的，我们把所有限制按照权值从大往小排序，因为要最大值最小，所以显然竟可能的满足权值较大的限制。但是我们发现限制是\(x,y\)不能在一个集合。那么对于每一个点拆成两个，一个表示和它在一个集合，一个表示和它不在一个集合。对于一个限制，如果\(x,y\)已经在一个集合内，显然这个限制的权值就是答案了。否则合并\(x\)和\(y\)的集合关系，即把\(x\)合并到和\(y\)不在一个集合内的集合中去，\(y\)同理。并查集实现即可。

#include
    
     #include
     
      #include
      
       using namespace std;#define MAX 40040#define MAXL 100100inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int n,m;struct Line{int u,v,w;}e[MAXL];bool operator<(Line a,Line b){return a.w>b.w;}int f[MAX];int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}int main(){    n=read();m=read();    for(int i=1;i<=m;++i)e[i].u=read(),e[i].v=read(),e[i].w=read();    sort(&e[1],&e[m+1]);    for(int i=1;i<=n+n;++i)f[i]=i;    for(int i=1;i<=m;++i)    {        int u=e[i].u,v=e[i].v;        if(getf(u)==getf(v))        {            printf("%d\n",e[i].w);            return 0;        }        f[getf(u)]=getf(v+n);        f[getf(v)]=getf(u+n);    }    printf("0\n");    return 0;}
      
     
    

引水入城 flow

也是一道很不错的题目。

对于判定性问题，不用多想，在每一个位置都建立蓄水场，\(bfs\)一遍判定是否能够满足所有位置。如果不行就直接输出。否则考虑如何计算最小值。

继续观察，发现当可以满足所有位置的时候，在每个位置建立蓄水场，那么它影响的范围一定是一段连续区间。证明不难。如果不是一段区间的话，假设\(x\)为其中的一个分割位置，因为有解，所以\(x\)必定能被\(x-1,x+1\)和\(x\)上一行这三个格子中的一个影响到，而\(x\)割开了一个线段，那么必定跨越\(x\)这一列，所以不可能不影响到\(x\)位置。所以必定是一段连续区间。

那么问题转化成给定若干线段，选出最少的线段覆盖所有区间，贪心即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX 505inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}int d[4][2]={1,0,-1,0,0,1,0,-1};int a[MAX][MAX];int n,m,tot,ans;struct effect{int l,r;}p[MAX];bool operator<(effect a,effect b){if(a.l!=b.l)return a.l
          
           b.r;}bool vis[MAX][MAX];namespace check{ queue
           
             Qx,Qy; void bfs() { for(int i=1;i<=m;++i)Qx.push(1),Qy.push(i),vis[1][i]=true; while(!Qx.empty()) { int x=Qx.front(),y=Qy.front();Qx.pop(),Qy.pop(); for(int i=0;i<4;++i) { int xx=x+d[i][0],yy=y+d[i][1]; if(xx<1||yy<1||xx>n||yy>m)continue; if(vis[xx][yy])continue; if(a[xx][yy]>=a[x][y])continue; vis[xx][yy]=true; Qx.push(xx);Qy.push(yy); } } } void work() { bfs();int sum=0; for(int i=1;i<=m;++i) if(!vis[n][i])++sum; if(sum){printf("0\n%d\n",sum);exit(0);} puts("1"); }}namespace Get{ void bfs(int Sx,int Sy) { memset(vis,0,sizeof(vis));queue
            
              Qx,Qy; Qx.push(Sx);Qy.push(Sy);vis[Sx][Sy]=true; while(!Qx.empty()) { int x=Qx.front(),y=Qy.front();Qx.pop(),Qy.pop(); for(int i=0;i<4;++i) { int xx=x+d[i][0],yy=y+d[i][1]; if(xx<1||yy<1||xx>n||yy>m)continue; if(vis[xx][yy])continue; if(a[xx][yy]>=a[x][y])continue; vis[xx][yy]=true; Qx.push(xx);Qy.push(yy); } } } void work() { for(int i=1;i<=m;++i) { bfs(1,i);int mx=0,mn=1e9; for(int j=1;j<=m;++j) if(vis[n][j])mx=j,mn=mn
             
              p[i-1].r)p[++sum]=p[i]; tot=sum; for(int i=1,j;i<=tot;i=j) { int nr=r;j=i; while(j<=tot&&p[j].l<=r+1)nr=max(nr,p[j++].r); ans+=1;r=nr; } printf("%d\n",ans); return 0;}