注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

NOIP2010  

2010-11-22 18:19:00|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

最后一次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;

}

 

  评论这张
 
阅读(657)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018