题解：P11120 [ROIR 2024 Day 1] 登机

cff_0102 · 2024-09-28 01:15:43 · 题解

首先根据输入找出所有必须被安排的座位，并计算它的数量（设为 cnt）。如果这个数大于 m 则肯定不行，输出 Impossible。

否则，先把 cnt 个乘客安排好，剩下 m'=m-cnt 个乘客。因为座位必须是对称的，所以左边有一个座位，右边就必须也有一个，即如果有安排的方案，m' 必须是偶数。如果是奇数就无解。

接下来就直接模拟，从飞机第一排开始往后分别给乘客排好座位即可，记得判断最后会不会有飞机座位不够的情况。

#include<bits/stdc++.h>
using namespace std;
bool a[1145][7];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=6;j++){
            char c;cin>>c;
            if(c=='X')a[i][j]=1;
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=6;j++){
            if(a[i][j]&&!a[i][7-j])cnt++,a[i][7-j]=1;
        }
    }
    if(cnt>m)cout<<"Impossible",exit(0);
    m-=cnt;
    if(m%2)cout<<"Impossible",exit(0);
    for(int i=1;i<=n&&m;i++){
        for(int j=1;j<=6&&m;j++){
            if(a[i][j]==0)m-=2,a[i][j]=a[i][7-j]=1;
        }
    }
    if(m)cout<<"Impossible",exit(0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=6;j++){
            cout<<((a[i][j])?('X'):('.'));
        }cout<<endl;
    }
    return 0;
}

注：代码中 m-=cnt; 前后两行的判断删去也能 AC，这是因为在后面的模拟中，如果 m' 不符合要求，则代码中的变量 m 一定不会被减到 0。