题解 [COCI2006-2007#6] KAMEN

xiaolilsq · 2020-04-12 17:05:54 · 题解

题目链接

刚开始看到这道题目没有任何思路，但是如果知道一个性质这题就很好做了：如果从第x列下落的路径为a_1\dots a_y，那么经过若干轮后，必然只有后面经过的一段连续路径会被石子覆盖。

考虑反证法，如果存在一个t，使得a_t被石子覆盖而a_{t+1}没有被覆盖，那么由于可以从a_t下落到a_{t+1}，a_{t+1}必然也被石子覆盖，与假设a_{t+1}没有被覆盖相矛盾，所以经过若干轮后，必然只有后面经过的一段连续路径会被石子覆盖。

那么我们可以想出一种算法：先保留从每一行下降的路径，进行某行的操作的时候，先把路径被占的部分退回去，然后再寻找一条其他的路径进行下落。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
template<typename T>void read(T &x){
    x=0;int f(1);char c(getchar());
    for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
    for(; isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c-'0');
    x*=f;
}
template<typename T>void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x/10)write(x/10),x%=10;
    putchar(x+'0');
}
char map[30005][35];
int sap[35][30005],cn[35],r,c;
void push(int x){//下落函数
    while(true){
        int t=sap[x][cn[x]];
        if(map[cn[x]][t]=='O')--cn[x];//如果被占领则将路径退回
        else if(cn[x]==r)break;//到底了
        else if(map[cn[x]+1][t]=='X')break;//有墙壁不再下落
        else if(map[cn[x]+1][t]=='.')sap[x][++cn[x]]=t;//往下走
        else if(t>1&&map[cn[x]][t-1]=='.'&&map[cn[x]+1][t-1]=='.')sap[x][++cn[x]]=t-1;//往左走
        else if(t<c&&map[cn[x]][t+1]=='.'&&map[cn[x]+1][t+1]=='.')sap[x][++cn[x]]=t+1;//往右走
        else break;//无路可走
    }
    map[cn[x]][sap[x][cn[x]]]='O';//占领最后的格子
}
int main(){
    read(r),read(c);
    for(int i=1;i<=r;++i){//读入
        for(int j=1;j<=c;++j){
            char c=getchar();
            while(c!='X'&&c!='.')
                c=getchar();
            map[i][j]=c;
        }
    }
    for(int j=1;j<=c;++j)
        sap[j][0]=j;//初始每列从该列开始下落
    int n;read(n);
    while(n--){
        int tmp;read(tmp);
        push(tmp);//下落
    }
    for(int i=1;i<=r;++i,putchar('\n'))
        for(int j=1;j<=c;++j)
            putchar(map[i][j])//输出;
    return 0;
}

复杂度为什么是对的？其实我也不会证呜呜呜。

希望有大佬可以证明复杂度。