题解：P16489 [GKS 2014 #C] Tetris

· · 题解

P16489 [GKS 2014 #C] Tetris 题解

题目大意

场地宽 W、高 H，N 个四格骨牌从上方依次落下。每个骨牌给定类型 t、旋转 r、水平位置 x。骨牌碰到已有方块或地面立即停止；放置成功后，若有整行被填满就消除（可能连消多行），消除后上方整体下移一行，悬空方块不继续下落。某块骨牌停止时若顶边超出场地上界，游戏立即结束，输出 Game Over!；否则输出最终场地。

一、直接模拟

就纯粹模拟题面莫。

  1. 下落：骨牌从场地上方逐行往下试，每试一个位置检查骨牌覆盖的格子是否碰撞。骨牌最多 4 格，每步检查 O(1)，最多落 H 步，所以每块 O(H)。
  2. 消行：每次放完骨牌，从底往上扫 H 行，每行数 W 个格判断是否满，满了就把上方所有行逐格拷贝下移。

总复杂度 O(TNHW)。本题数据 W, H \le 100，N \le 5000，T \le 100。

二、优化：每行维护已填格数

直接模拟慢在消行时每行都要数 W 个格，不管满没满都白数一遍。

维护一个数组 ton[i]，表示第 i 行当前已填的 'x' 数：

这样“找满行”从 O(HW) 降到扫 H 行看计数的 O(H)。

下移仍然逐格拷贝 W 列，看似还是 O(HW) 每次，但用摊还分析：

每消一行，该行必须有 W 个 x 被填满；所有骨牌总共最多贡献 4N 个 x。所以整个游戏总消行数 \le 4N/W。

于是下移总代价：

\sum_{\text{所有消行}} O(HW) = O\left(\frac{4N}{W}HW\right) = O(NH)

三、复杂度

部分 代价 性质
下落 O(NH) 每块最坏落 H 步
放置更新 O(N) 每块 4 格
扫 H 行找满行 O(NH) 每次放置后扫一遍，O(1) 判满
下移 O(NH) 总消行数 \le 4N/W，每次 O(HW)
输出 O(HW) 一次

单组 O(NH) 摊还，T 组 O(TNH) 摊还。

有一个 16 的常数。

四、关键实现细节

1. 游戏结束判定

骨牌下落停止后，若其顶边的行坐标 < 0，说明放不下，特判一下 _=true。

2. 地面

地图第 H+1 行预置为 x 作为地面，让骨牌下落有阻挡。

3. 消行重查

消掉第 i 行后，上方整体下移，第 i 行变成原来第 i-1 行，可能又是满的。所以消行后要让循环变量回退（j++ 抵消 j--），重查同一位置，实现连消。

五、参考代码

:::info[点击查看代码]


#include<bits/stdc++.h>
#define for1(i,x,y,k) for(int i=x;i<=y;i+=k)
#define for2(i,x,y,k) for(int i=x;i>=y;i-=k)
#define md (t[p].l+t[p].r>>1)
#define mi (lc+rc>>1)
#define mid (l+r>>1)
#define pii pair<int,int>
#define pf push_front
#define pb push_back
#define int long long
using namespace std;
const int N=1e2+5;
int T,w,h,n,t,r,x;
int ton[N],pre[N];
int k[10][10][10][10];
bool _;
bool dp[N][N];
void init(){
    k[1][0][1][0]=1;k[1][0][1][1]=1;k[1][0][2][0]=2;k[1][0][2][1]=1;k[1][0][3][0]=2;k[1][0][3][1]=2;k[1][0][4][0]=3;k[1][0][4][1]=2;
    k[1][1][1][0]=2;k[1][1][1][1]=1;k[1][1][2][0]=2;k[1][1][2][1]=2;k[1][1][3][0]=1;k[1][1][3][1]=2;k[1][1][4][0]=1;k[1][1][4][1]=3;
    k[1][2][1][0]=1;k[1][2][1][1]=1;k[1][2][2][0]=2;k[1][2][2][1]=1;k[1][2][3][0]=2;k[1][2][3][1]=2;k[1][2][4][0]=3;k[1][2][4][1]=2;
    k[1][3][1][0]=2;k[1][3][1][1]=1;k[1][3][2][0]=2;k[1][3][2][1]=2;k[1][3][3][0]=1;k[1][3][3][1]=2;k[1][3][4][0]=1;k[1][3][4][1]=3;

    k[2][0][1][0]=1;k[2][0][1][1]=2;k[2][0][2][0]=2;k[2][0][2][1]=1;k[2][0][3][0]=2;k[2][0][3][1]=2;k[2][0][4][0]=3;k[2][0][4][1]=1;
    k[2][1][1][0]=1;k[2][1][1][1]=1;k[2][1][2][0]=1;k[2][1][2][1]=2;k[2][1][3][0]=2;k[2][1][3][1]=2;k[2][1][4][0]=2;k[2][1][4][1]=3;
    k[2][2][1][0]=1;k[2][2][1][1]=2;k[2][2][2][0]=2;k[2][2][2][1]=1;k[2][2][3][0]=2;k[2][2][3][1]=2;k[2][2][4][0]=3;k[2][2][4][1]=1;
    k[2][3][1][0]=1;k[2][3][1][1]=1;k[2][3][2][0]=1;k[2][3][2][1]=2;k[2][3][3][0]=2;k[2][3][3][1]=2;k[2][3][4][0]=2;k[2][3][4][1]=3;

    k[3][0][1][0]=1;k[3][0][1][1]=1;k[3][0][2][0]=2;k[3][0][2][1]=1;k[3][0][3][0]=3;k[3][0][3][1]=1;k[3][0][4][0]=3;k[3][0][4][1]=2;
    k[3][1][1][0]=2;k[3][1][1][1]=1;k[3][1][2][0]=2;k[3][1][2][1]=2;k[3][1][3][0]=1;k[3][1][3][1]=3;k[3][1][4][0]=2;k[3][1][4][1]=3;
    k[3][2][1][0]=1;k[3][2][1][1]=1;k[3][2][2][0]=1;k[3][2][2][1]=2;k[3][2][3][0]=2;k[3][2][3][1]=2;k[3][2][4][0]=3;k[3][2][4][1]=2;
    k[3][3][1][0]=1;k[3][3][1][1]=1;k[3][3][2][0]=2;k[3][3][2][1]=1;k[3][3][3][0]=1;k[3][3][3][1]=2;k[3][3][4][0]=1;k[3][3][4][1]=3;

    k[4][0][1][0]=1;k[4][0][1][1]=2;k[4][0][2][0]=2;k[4][0][2][1]=2;k[4][0][3][0]=3;k[4][0][3][1]=1;k[4][0][4][0]=3;k[4][0][4][1]=2;
    k[4][1][1][0]=1;k[4][1][1][1]=1;k[4][1][2][0]=1;k[4][1][2][1]=2;k[4][1][3][0]=1;k[4][1][3][1]=3;k[4][1][4][0]=2;k[4][1][4][1]=3;
    k[4][2][1][0]=1;k[4][2][1][1]=1;k[4][2][2][0]=2;k[4][2][2][1]=1;k[4][2][3][0]=3;k[4][2][3][1]=1;k[4][2][4][0]=1;k[4][2][4][1]=2;
    k[4][3][1][0]=1;k[4][3][1][1]=1;k[4][3][2][0]=2;k[4][3][2][1]=1;k[4][3][3][0]=2;k[4][3][3][1]=2;k[4][3][4][0]=2;k[4][3][4][1]=3;

    k[5][0][1][0]=1;k[5][0][1][1]=1;k[5][0][2][0]=2;k[5][0][2][1]=2;k[5][0][3][0]=1;k[5][0][3][1]=2;k[5][0][4][0]=2;k[5][0][4][1]=1;
    k[5][1][1][0]=1;k[5][1][1][1]=1;k[5][1][2][0]=2;k[5][1][2][1]=2;k[5][1][3][0]=1;k[5][1][3][1]=2;k[5][1][4][0]=2;k[5][1][4][1]=1;
    k[5][2][1][0]=1;k[5][2][1][1]=1;k[5][2][2][0]=2;k[5][2][2][1]=2;k[5][2][3][0]=1;k[5][2][3][1]=2;k[5][2][4][0]=2;k[5][2][4][1]=1;
    k[5][3][1][0]=1;k[5][3][1][1]=1;k[5][3][2][0]=2;k[5][3][2][1]=2;k[5][3][3][0]=1;k[5][3][3][1]=2;k[5][3][4][0]=2;k[5][3][4][1]=1;

    k[6][0][1][0]=1;k[6][0][1][1]=1;k[6][0][2][0]=2;k[6][0][2][1]=1;k[6][0][3][0]=3;k[6][0][3][1]=1;k[6][0][4][0]=4;k[6][0][4][1]=1;
    k[6][1][1][0]=1;k[6][1][1][1]=1;k[6][1][2][0]=1;k[6][1][2][1]=2;k[6][1][3][0]=1;k[6][1][3][1]=3;k[6][1][4][0]=1;k[6][1][4][1]=4;
    k[6][2][1][0]=1;k[6][2][1][1]=1;k[6][2][2][0]=2;k[6][2][2][1]=1;k[6][2][3][0]=3;k[6][2][3][1]=1;k[6][2][4][0]=4;k[6][2][4][1]=1;
    k[6][3][1][0]=1;k[6][3][1][1]=1;k[6][3][2][0]=1;k[6][3][2][1]=2;k[6][3][3][0]=1;k[6][3][3][1]=3;k[6][3][4][0]=1;k[6][3][4][1]=4;

    k[7][0][1][0]=1;k[7][0][1][1]=2;k[7][0][2][0]=2;k[7][0][2][1]=1;k[7][0][3][0]=2;k[7][0][3][1]=2;k[7][0][4][0]=2;k[7][0][4][1]=3;
    k[7][1][1][0]=2;k[7][1][1][1]=1;k[7][1][2][0]=2;k[7][1][2][1]=2;k[7][1][3][0]=1;k[7][1][3][1]=2;k[7][1][4][0]=3;k[7][1][4][1]=2;
    k[7][2][1][0]=1;k[7][2][1][1]=1;k[7][2][2][0]=2;k[7][2][2][1]=2;k[7][2][3][0]=1;k[7][2][3][1]=2;k[7][2][4][0]=1;k[7][2][4][1]=3;
    k[7][3][1][0]=1;k[7][3][1][1]=1;k[7][3][2][0]=2;k[7][3][2][1]=2;k[7][3][3][0]=2;k[7][3][3][1]=1;k[7][3][4][0]=3;k[7][3][4][1]=1;
}
void luo(int zhong,int d,int wei){
    int minx=N;
    for1(i,1,4,1){
        for1(j,1,h+1,1){
            if(dp[j][wei+k[zhong][d][i][1]])
                minx=min(minx,j-k[zhong][d][i][0]);
        }
    }
    for1(i,1,4,1){
        int xi=minx-1+k[zhong][d][i][0],yi=wei+k[zhong][d][i][1];
        if(xi<1){
            _=true;
            return;
        }
        dp[xi][yi]=true;
        ton[xi]++;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    cin>>T;
    for1(ti,1,T,1){
        _=false;
        cin>>w>>h>>n;
        memset(dp,false,sizeof(dp));
        memset(ton,0,sizeof(ton));
        for1(i,1,w,1)
            dp[h+1][i]=true;
        for1(i,1,n,1){
            cin>>t>>r>>x;
            luo(t,r,x);
            for2(j,h,1,1){
                if(ton[j]==w){
                    for2(y,j,1,1){
                        ton[y]=ton[y-1];
                        for1(xx,1,w,1)
                            dp[y][xx]=dp[y-1][xx];
                    }
                    j++;
                }
            }
        }
        cout<<"Case #"<<ti<<":"<<'\n';
        if(_){
            cout<<"Game Over!"<<'\n';
            continue;
        }
        for1(i,1,h,1){
            for1(j,1,w,1)
                cout<<(dp[i][j]?"x":".");
            cout<<'\n';
        }
    }
    return 0;
}

:::

AI 使用说明：本文在写作完成后使用 DeepSeek 进行了文字润色，包括格式调整和语句通顺化。题目的思路、复杂度分析及代码均由本人完成。