题解B4424

Fume_shroom · 2025-10-21 17:52:48 · 题解

10月入门赛T8（虽然大概比T7简单一些，但是我赛时只能调到60pts）

第一部分：60pts

直接按照题意模拟即可，时间复杂度为O(n^2m)
大概步骤：
1.扫描每一个箱子的位置
2.模拟下落的过程，一格一格向下落
代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    char a[100005][15];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=n-1;i>0;i--){
        for(int j=1;j<=m;j++){
            if(a[i][j]>='A'&&a[i][j]<='Z'){
                int ii=i;
                while(ii<n&&a[ii+1][j]=='.'){
                    ii++;
                }
                swap(a[i][j],a[ii][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<a[i][j];
        }
        cout<<'\n';
    }
}

第二部分：100pts

过程中可以发现时间复杂度主要浪费在模拟下落的过程，我们可以使用一个变量bottom维护瓶底。一格一格向上走，遇到隔板就更新bottom到隔板上，遇到箱子就swap(瓶底位置，箱子位置)并把bottom减一。
代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    char a[100005][15];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int j=1;j<=m;j++){
        int bottem=n;
        for(int i=n;i>=1;i--){
            if(a[i][j]>='A'&&a[i][j]<='Z'){
                swap(a[i][j],a[bottem][j]);
                bottem--;
            }
            if(a[i][j]=='-') bottem=i-1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<a[i][j];
        cout<<'\n';
    }
}