2011noip提高组复赛题解

《2011noip提高组复赛题解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Noip2011提高组（Day1）解题报告及程序一、铺地毯正着扫一遍判断每个矩形是否覆盖询问的点，覆盖则更新结果或者倒着扫一遍，找到第一个覆盖询问点的矩形，输出即可，时间复杂度O（n）Procedure:#include#defineMaxLength10000inlineintGetint(){      charc=getchar();      while(c<'0'

2、

3、c>'9')c=getchar();      intret=0;      while(c>='0'&&c<='

4、9')      {          ret=ret*10+(c-'0');          c=getchar();      }      returnret;}intsx[MaxLength+5],sy[MaxLength+5],ex[MaxLength+5],ey[MaxLength+5],n;voidInit(){    n=Getint();    for(inti=1;i<=n;i++)    {        sx[i]=Getint(),sy[i]=Getint(),ex[i]=Ge

5、tint(),ey[i]=Getint();        ex[i]+=sx[i],ey[i]+=sy[i];    }    return;}intx0,y0,ans=-1;voidSolve(){    x0=Getint(),y0=Getint();    for(inti=n;i;i--)        if(x0>=sx[i]&&x0<=ex[i]&&y0>=sy[i]&&y0<=ey[i])        {            ans=i;            break;      

6、  }    printf("%d",ans);    return;}intmain(){   Init();   Solve();   getchar();getchar();   return0;}二、选择客栈f[i][j]表示前i个客栈以第j种颜色的方案数，先以客栈划分第一阶段，以颜色划分第二阶段，如果颜色相同的客栈，则以前一客栈相同颜色的方案数+1，否则同其一样；计算答案时记一下前一个比最高消费限制低的客栈编号pos[i]，路径压缩，时间复杂度O（nm）Procedure: #include

7、stdio>#defineMaxNode200000#defineMaxType50inlineintGetint(){      charc=getchar();      while(c<'0'

8、

9、c>'9')c=getchar();      intret=0;      while(c>='0'&&c<='9')      {          ret=ret*10+(c-'0');          c=getchar();      }      returnret;}intcolor[Max

10、Node+5],price[MaxNode+5],n,m,low;voidInit(){    n=Getint(),m=Getint(),low=Getint();    for(inti=1;i<=n;i++)color[i]=Getint(),price[i]=Getint();    return;}intf[MaxNode+5][MaxType+5],pos[MaxNode+5],ans=0;voidDp(){    for(inti=1;i<=n;i++)        for(intj=0;

11、j

12、i-1];            ans+=f[pos[i]][color[i]];        }    printf("%d",ans);    return;}intmain(){   Init();   Dp();   getchar();getchar();   return0;} 三、 Mayan纯暴力DFS，加可行性剪枝，如同一种颜色小于3块无法消除，同一颜色交换无意义，下落无法完成左右移动，再加模拟其过程时间