大家好，欢迎来到IT知识分享网。

NOIP2011复赛——DAY1

1、铺地毯

【题目分析】
水题，有送分的觉悟！不过在刚开始读题的时候有点慌，一时没读懂，看来心理素质还是不行啊，不够淡定。
其实就是简单的if else语句。

【代码】

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int i,j,n,id=-1,x,y;
    scanf("%d",&n);
    scanf("%d %d",&x,&y);
    for(i=1;i<=n;i++){
        int a,b,g,k;
        scanf("%d %d %d %d",&a,&b,&g,&k);
        int zuoxiax=a;
        int zuoxiay=b;
        int youshangx=a+g;
        int youshangy=b+k;
        if(x>=zuoxiax&&x<=youshangx&&y>=zuoxiay&&y<=youshangy)id=i;
    }printf("%d\n",id);
    return 0;
}

2、选择客栈

【题目分析】
这是一道比较好玩的题目，情景感比较强。而问题的实质就是：
1、将同种颜色的客栈进行处理。
2、对于一个客栈，它有两种情况，费用超过p、费用不超过p。
3、超过p的找之后相同颜色且费用不超过p的。
4、不超过p的与之后相同颜色的随意组合。
既然是批量处理，自然想到了前缀和。（处理3的时候用到了后缀和）
想清楚了情况，那就开始模拟吧。

【代码】

#define N 52
#define M 200005
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt[N],L[M],R[M];
int n,k,p;
long long ans=0;
struct node{
    int c,val;
}a[M];
int main(){
    int i,j;
    scanf("%d %d %d",&n,&k,&p);
    for(i=1;i<=n;i++)scanf("%d %d",&a[i].c,&a[i].val);
    for(j=0;j<k;j++){
        int cnt=0;
        L[0]=R[n+1]=0;
        for(i=1;i<=n;i++){
            L[i]=L[i-1];
            if(a[i].c==j)L[i]++;
        }
        for(i=n;i>=1;i--){
            if(a[i].c==j)cnt++;
            R[i]=R[i+1];
            if(a[i].val<=p)R[i]=cnt;
        }
        for(i=1;i<=n;i++){
            if(a[i].c!=j)continue;
            if(a[i].val<=p)ans+=L[n]-L[i];
            else ans+=R[i+1];   
        }
    }cout<<ans<<endl;
    return 0;
}

3、Mayan 游戏

【题目分析】
这题与之前写过的天天爱消除十分的相似（想死）。
这题的最难点在于消除、下落与合并：
显然是用个while来操作不断消除与不断下落、不断合并，而消除、下落与合并又是相对独立的函数，
所以每个函数的衔接十分重要。（如果不是暴搜，起码还能水到部分分，但是在赛场上调暴搜是一件十分尴尬的事情，因为如果没调出来，真的就要爆炸了）

【代码】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
struct T{
    int x,y,ops;
}ans[10];
int n,st[10][10];
bool empty(){
    for(int i=0;i<5;i++){
        for(int j=0;j<7;j++){
            if(st[i][j])return 0;
        }
    }return 1;
}
void drop(){
    int num[10][10];
    memset(num,-1,sizeof(num));
    for(int x=0;x<5;x++){
        int h=0;
        for(int y=0;y<7;y++){
            if(st[x][y])num[x][h++]=y;
        }
    }
    for(int x=0;x<5;x++){
        for(int y=0;y<7;y++){
            if(num[x][y]==-1)st[x][y]=0;
            else st[x][y]=st[x][num[x][y]];
        }
    }
}
bool clear(){
    bool f=0;
    for(int x=0;x<3;x++){
        for(int y=0;y<7;y++){
            if(st[x][y]){
                int x2=x;
                while(x2<4&&st[x2+1][y]==st[x][y])x2++;
                if(x2-x>=2){
                    for(int tx=x;tx<=x2;tx++){
                        int Up=y,Dn=y;
                        while(Up+1<7&&st[tx][Up+1]==st[x][y])Up++;
                        while(Dn-1>=0&&st[tx][Dn-1]==st[x][y])Dn--;
                        if(Up-Dn>=2){
                            int ty;
                            for(ty=Dn;ty<=Up;ty++)st[tx][ty]=0;
                        }
                    }for(int tx=x;tx<=x2;tx++)st[tx][y]=0;
                    f=1;
                }
            }
        }
    }
    for(int x=0;x<5;x++){
        for(int y=0;y<5;y++){
            if(st[x][y]){
                int y2=y;
                while(y2<6&&st[x][y2+1]==st[x][y])y2++;
                if(y2-y>=2){
                    for(int ty=y;ty<=y2;ty++){
                        int Lf=x,Ri=x;
                        while(Lf-1>=0&&st[Lf-1][ty]==st[x][y])Lf--;
                        while(Ri+1<7&&st[Ri+1][ty]==st[x][y])Ri++;
                        if(Ri-Lf>=2){
                            int tx;
                            for(tx=Lf;tx<=Ri;tx++)st[tx][ty]=0;
                        }
                    }
                    for(int ty=y;ty<=y2;ty++)st[x][ty]=0;
                    f=1;
                }
            }
        }
    }return f;
}
bool H(){
    int sum[12];
    memset(sum,0,sizeof(sum));
    for(int x=0;x<5;x++){
        for(int y=0;y<7;y++)sum[st[x][y]]++;
    }
    for(int i=1;i<=10;i++){
        if(sum[i]!=0&&sum[i]<3)return 0;
    }return 1;
}
void dfs(int step){
    if(step>n){
        if(empty()){
            for(int i=1;i<=n;i++){
                if(ans[i].ops)printf("%d %d %d\n",ans[i].x+1,ans[i].y,-1);
                else printf("%d %d %d\n",ans[i].x,ans[i].y,1);
            }exit(0);
        }return;
    }if(!H())return;
    for(int x=0;x<4;x++){
        for(int y=0;y<7;y++){
            if(st[x][y]!=st[x+1][y]){
                ans[step].x=x;
                ans[step].y=y;
                ans[step].ops=(!st[x][y]);
                int temp[10][10];
                memcpy(temp,st,sizeof(temp));
                swap(st[x][y],st[x+1][y]);
                drop();
                while(clear())drop();
                dfs(step+1);
                ans[step].x=ans[step].y=ans[step].ops=0;
                memcpy(st,temp,sizeof(st));
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<5;i++){
        for(int j=0;;j++){
            scanf("%d",&st[i][j]);
            if(st[i][j]==0)break;
        }
    }dfs(1);
    puts("-1");
    return 0;
}

【思路】
1、无。
2、想法题。
3、搜索。

作为一个oier，一颗强大的心脏是必备的！