题解：P7029 [NWRRC 2017] Kotlin Island

题目大意

给定高为

h

且宽为

w

的网格，初始时全为陆地，你需要在上面构造任意条横贯网格的水渠使得会有

k

个陆地不连通。

解题思路

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

所以最终的答案一定可以在这上面的基础上增添水渠得到，于是我们可以枚举横向可放置的数量

i

以及纵向可放置的数量

j

，若出现二者相乘等于

k

那么一定是答案的一种，只需要保留

i\times j

的陆地数量，其余的全部修改成水渠即可！

代码如下

CPP

#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;
}

题解：P7029 [NWRRC 2017] Kotlin Island

文章操作

题目大意

解题思路

代码如下

相关推荐

评论

题解：P7029 [NWRRC 2017] Kotlin Island