NOIP2010

最后一次NOIP了,390(最后一个程序dfs改快一点就可以400最后一个题有更好的算法,O(n^2)的)。


代码贴在这里,题解网上已经有了,就不必写了。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-11-20


DESCRIPTION:


$DESCRIPTION


*/


#include <stdio.h>


 


#define PROBLEM “translate”


FILE* file;


 


const int QUEUE_SIZE=1<<20;


int M,N;


int queue[QUEUE_SIZE];


bool in_queue[QUEUE_SIZE];


int head,tail;


int answer;


 


int main()


{


    file=fopen(PROBLEM“.in”,“r”);


    fscanf(file,“%d%d”,&M,&N);


    for (int i=0;i<N;i++)


    {


        int word;


        fscanf(file,“%d”,&word);


        if (!in_queue[word])


        {


           in_queue[queue[tail++]=word]=true;


           if (tail-head>M)


              in_queue[queue[head++]]=false;


           answer++;


        }


    }


    fclose(file);


    file=fopen(PROBLEM“.out”,“w”);


    fprintf(file,“%d\n”,answer);


    fclose(file);


    return 0;


}


 


#include <stdio.h>


 


#define PROBLEM “tortoise”


FILE* file;


const int MAXN=1<<10;


const int MAXCARD=1<<6;


const int MAXCARD_NUMBER=1<<3;


int N,M;


int a[MAXN];


int card[MAXCARD_NUMBER];


int f[MAXCARD][MAXCARD][MAXCARD][MAXCARD];


 


int main()


{


    file=fopen(PROBLEM“.in”,“r”);


    fscanf(file,“%d%d”,&N,&M);


    for (int i=0;i<N;i++)


        fscanf(file,“%d”,a+i);


    for (int i=0;i<M;i++)


    {


        int b;


        fscanf(file,“%d”,&b);


        card[b]++;


    }


    fclose(file);


    for (int i1=0;i1<=card[1];i1++)


        for (int i2=0;i2<=card[2];i2++)


            for (int i3=0;i3<=card[3];i3++)


                for (int i4=0;i4<=card[4];i4++)


                {


                    int get=a[1*i1+2*i2+3*i3+4*i4];


                    if (i1>0&&f[i1][i2][i3][i4]<f[i1-1][i2][i3][i4])


                       f[i1][i2][i3][i4]=f[i1-1][i2][i3][i4];


                    if (i2>0&&f[i1][i2][i3][i4]<f[i1][i2-1][i3][i4])


                       f[i1][i2][i3][i4]=f[i1][i2-1][i3][i4];


                    if (i3>0&&f[i1][i2][i3][i4]<f[i1][i2][i3-1][i4])


                       f[i1][i2][i3][i4]=f[i1][i2][i3-1][i4];


                    if (i4>0&&f[i1][i2][i3][i4]<f[i1][i2][i3][i4-1])


                       f[i1][i2][i3][i4]=f[i1][i2][i3][i4-1];


                    f[i1][i2][i3][i4]+=get;


                }


    file=fopen(PROBLEM“.out”,“w”);


    fprintf(file,“%d\n”,f[card[1]][card[2]][card[3]][card[4]]);


    fclose(file);


    return 0;


}


 


#include <stdio.h>


 


#define PROBLEM “prison”


FILE* file;


const int MAXN=1<<20;


const int MAXM=1<<20;


const int UNCOLORED=-1,RED=0,BLUE=1;


struct Prison{int a,b,c;};


struct struct_edge{int v;struct_edge* n;};


typedef struct_edge* Edge;


int N,M;


Prison prison[MAXM];


Edge adj[MAXN];


struct_edge pool[MAXM*2];


Edge top;


int color[MAXN];


int answer=(~0u)>>1;


 


void quick_sort(int l,int r)


{


     int i=l,j=r,mid=prison[(l+r)>>1].c;


     while (i<=j)


     {


           while (i<=j&&prison[i].c>mid) i++;


           while (i<=j&&prison[j].c<mid) j–;


           if (i<=j)


           {


              Prison swap;


              swap=prison[i],prison[i]=prison[j],prison[j]=swap;


              i++,j–;


           }


     }


     if (l<j) quick_sort(l,j);


     if (i<r) quick_sort(i,r);


}


void add_edge(int u,int v)


{


     top->v=v,top->n=adj[u],adj[u]=top++;


     top->v=u,top->n=adj[v],adj[v]=top++;


}


void build_graph(int end)


{


     top=pool;


     for (int i=1;i<=N;i++) adj[i]=0;


     for (int i=0;i<=end;i++)


         add_edge(prison[i].a,prison[i].b);


}


bool color_node(int u,int which_color=RED)


{


     if (color[u]!=UNCOLORED) return color[u]==which_color;


     else


     {


         color[u]=which_color;


         for (Edge i=adj[u];i;i=i->n)


             if (!color_node(i->v,!which_color)) return false;


         return true;


     }


}


bool is_binary_graph()


{


     for (int i=1;i<=N;i++) color[i]=UNCOLORED;


     for (int i=1;i<=N;i++)


         if (color[i]==UNCOLORED)


            if (!color_node(i)) return false;


     return true;


}


 


int main()


{


    file=fopen(PROBLEM“.in”,“r”);


    fscanf(file,“%d%d”,&N,&M);


    for (int i=0;i<M;i++)


        fscanf(file,“%d%d%d”,&prison[i].a,&prison[i].b,&prison[i].c);


    fclose(file);


    quick_sort(0,M-1);


    int L=0,R=M;


    while (L+1!=R)


    {


          int mid=(L+R)>>1;


          build_graph(mid);


          if (is_binary_graph()) L=mid;


          else R=mid;


    }


    if (R!=M) answer=prison[R].c;


    else answer=0;


    file=fopen(PROBLEM“.out”,“w”);


    fprintf(file,“%d\n”,answer);


    fclose(file);


    return 0;


}


 


#include <stdio.h>


 


#define PROBLEM “flow”


FILE* file;


const int MAXN=1<<10;


const int MAXM=1<<10;


const int oo=(~0u)>>1;


int N,M;


int height[MAXN][MAXM];


int color[MAXN][MAXM];


int adjs[MAXM];


int adj[MAXM][MAXM];


bool watered[MAXM];


int unwatered;


int begin[MAXM];


int end[MAXM];


int f[MAXM][MAXM];


int need;


 


void dfs(int x,int y,int start)


{


     if (color[x][y]!=start)


     {


        color[x][y]=start;


        if (height[x+1][y]<height[x][y]) dfs(x+1,y,start);


        if (height[x-1][y]<height[x][y]) dfs(x-1,y,start);


        if (height[x][y+1]<height[x][y]) dfs(x,y+1,start);


        if (height[x][y-1]<height[x][y]) dfs(x,y-1,start);


        if (x==N) adj[start][adjs[start]++]=y;


     }


}


 


int main()


{


    file=fopen(PROBLEM“.in”,“r”);


    fscanf(file,“%d%d”,&N,&M);


    for (int i=1;i<=N;i++)


        for (int j=1;j<=M;j++)


            fscanf(file,“%d”,height[i]+j);


    fclose(file);


    file=fopen(PROBLEM“.out”,“w”);


    for (int i=1;i<=N;i++) height[i][0]=height[i][M+1]=oo;


    for (int i=1;i<=M;i++) height[0][i]=height[N+1][i]=oo;


    for (int i=1;i<=M;i++)


        dfs(1,i,i);


    for (int i=1;i<=M;i++)


        for (int j=0;j<adjs[i];j++) watered[adj[i][j]]=true;


    for (int i=1;i<=M;i++)


        if (!watered[i]) unwatered++;


    if (unwatered)


       fprintf(file,“%d\n%d\n”,0,unwatered);


    else


    {


        for (int i=1;i<=M;i++)


        {


            begin[i]=oo,end[i]=0;


            for (int j=0;j<adjs[i];j++)


                begin[i]=begin[i]<adj[i][j]?begin[i]:adj[i][j],


                end[i]=end[i]>adj[i][j]?end[i]:adj[i][j];


        }


        f[0][0]=true;


        for (int i=1;i<=M;i++)


            if (begin[i]<=end[i])


               for (int k=1;k<=M;k++)


               {


                   if (f[k-1][end[i]]) f[k][end[i]]=true;


                   for (int j=begin[i]-1;j<=end[i];j++)


                       if (f[k-1][j]) f[k][end[i]]=true;


               }


        for (int i=1;i<=M;i++)


            if (f[i][M])


            {


               need=i;


               break;


            }


        fprintf(file,“%d\n%d\n”,1,need);


    }


    fclose(file);


    return 0;


}


 

留下评论

电子邮件地址不会被公开。