专栏文章

题解B4424

FFume_shroom
B4424题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjlsox
此快照首次捕获于
2025/12/02 03:29
3 个月前
此快照最后确认于
2025/12/02 03:29
3 个月前
查看原文
10月入门赛T8（虽然大概比T7简单一些，但是我赛时只能调到60pts）

第一部分：60pts

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

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...