题解：P7029 [NWRRC 2017] Kotlin Island

lvweisi · 2025-11-25 08:46:59 · 题解

题目大意

给定高为 h 且宽为 w 的网格，初始时全为陆地，你需要在上面构造任意条横贯网格的水渠使得会有 k 个陆地不连通。

解题思路

不难发现放置得到最多陆地的最优解，就是陆地是一个间隔一个的时候放置的最多，如图所示：

所以最终的答案一定可以在这上面的基础上增添水渠得到，于是我们可以枚举横向可放置的数量 i 以及纵向可放置的数量 j，若出现二者相乘等于 k 那么一定是答案的一种，只需要保留 i\times j 的陆地数量，其余的全部修改成水渠即可！

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
char mp[200][200];
void sc(int x,int y){
    int h=0,s=0;//只保留x*y，其余的全部设置为"#"
    for(int i=1;i<=n;i++){
        int gs=0;
        h+=(i%2==1);
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='.'&&gs<y&&h<=x)cout<<mp[i][j],gs++;
            else cout<<"#";
        }
        cout<<'\n';
    }
    return ;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i+=2)for(int j=1;j<=m;j+=2)mp[i][j]='.';//预处理出以上图片中的样子
    int nn=ceil(n/2.0),mm=ceil(m/2.0);//横向和纵向可放置的最多个
    for(int i=1;i<=nn;i++){
        for(int j=1;j<=mm;j++){//枚举出符合答案的i,j
            if(i*j==k){
                sc(i,j);
                return 0;
            }
        }
    }
    cout<<"Impossible";
    return 0;
}