专栏文章

题解：P1514 [NOIP 2010 提高组] 引水入城

IIGA_Indigo
P1514题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mipopv4x
此快照首次捕获于
2025/12/03 15:27
3 个月前
此快照最后确认于
2025/12/03 15:27
3 个月前
查看原文

题目大意

有一个 n×mn\times m 的格子，第一行可以建造蓄水池，最后一行是沙漠，询问最少建造多少个蓄水池可以滋润到所有的沙漠土地，如果不能滋润到所有的沙漠土地，就输出有多少个沙漠土地不能被灌溉。

大体思路

just 避雷

这里有个比较典型的错误思路，注意不要掉进坑里，就是不要从蓄水池行贪心找最大值，这看上去很对，但是我们一旦找一个例子你就傻了。
我们其实选择 66 这个点就可以灌溉所有的沙漠块，但是选择 77 只能灌溉一个，原因是被相同点数的块卡住了。
这种方式或许在无论什么块都需要滋润的题中有效，但在这个题中是不行的。

正确思路

首先我们先从每一个蓄水区开始深搜，由于题目数据比较小，我们无需进行一些记忆化的操作，用 sfsf 数组记录每一个沙漠块能否被灌溉到，用 edgeedge 二维数组记录当前蓄水池能否灌溉到对应沙漠块（像一条条边一样的，能否连接）。当然了，我们这里还可以记录左端点右端点来优化，但还是由于题目数据较小，我们可以朴素的写连边的方式。
这样 DFS 后，我们就判断能不能全部滋润，如果不能就赶紧给出不能的答案，前面我们已经处理过了。
观察可以得到（看到题解区都有所证明，我就不进行证明了），每一个蓄水池在沙漠块的灌溉是一个连通块，没错是连续的，这样引诱着我们想到一个做法——从沙漠块开始贪心。
我的方法是，先找到灌溉最长的从第一个沙漠块开始的蓄水池，并选择他，记录他能滋润到的最远沙漠块，然后进入循环。
在循环中，我们从能滋润到的最远沙漠块的后一个块从后向前开始询问，选择它能够滋润到的最远沙漠块是哪里，记录最大值，并选择，就这样循环一直到最后一个块被滋润。
这里就有各种实现方式可以选择，我比较喜欢朴素的实现方式，如果实在想不到实现方式的，可以看下面的代码及每一步的优化建议。

Code

题解区题解各有所长，方法也不尽相同，为了不显得那么平平无奇，我的长处就是朴素且详细注释的代码！力求每一个新手都能看得懂。
（以及优化建议）
CPP
#include<bits/stdc++.h>
using namespace std;
long long read(){
	long long x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void write(long long x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
	return ;
}
int n,m;
int tu[505][505];
bool vis[505][505];//当前蓄水池的遍历有没有走过这个点 
bool sf[505];//标记这个点是否能被滋润
bool edge[505][505];//第一维是蓄水池，第二维是沙漠，连接表示该蓄水池能滋润对应沙漠 
int xx;
void dfs(int x,int y){//深搜找每个沙漠地带会被哪几个蓄水厂滋润到 
	vis[x][y]=1;//打上标记，这一次遍历中不会再来了 
	if(x==n){
		sf[y]=1;
		edge[xx][y]=1;
	}
	
	if(x-1>=1&&y>=1&&!vis[x-1][y]&&tu[x-1][y]<tu[x][y]){//可以向四个方向搜索 
		dfs(x-1,y);
	}
	if(x>=1&&y-1>=1&&!vis[x][y-1]&&tu[x][y-1]<tu[x][y]){
		dfs(x,y-1);
	}
	if(x>=1&&y+1<=m&&!vis[x][y+1]&&tu[x][y+1]<tu[x][y]){
		dfs(x,y+1);
	}
	if(x+1<=n&&y>=1&&!vis[x+1][y]&&tu[x+1][y]<tu[x][y]){
		dfs(x+1,y);
	}
}
void pans(){//找一片净土来累加答案吧（全写循环里真的太丑了） 
	int sum=0;
	for(int i=1;i<=m;i++){
		if(!sf[i]){
			sum++;
		}
	}
	write(sum);
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			tu[i][j]=read();
		}
	}
	for(int i=1;i<=m;i++){
		xx=i;
		dfs(1,i);//时间给的足，我们并不需要记忆化 
		for(int j=1;j<=n;j++){
			for(int k=1;k<=m;k++){
				vis[j][k]=0;//下一次遍历我们仍需记录，所以还得去 
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(!sf[i]){
			puts("0");
			pans();//不可以全部滋润就直接输出答案（译为puts ans(?)） ，可以优化 
			return 0;
		}
	}
	xx=1;//没用的变量重复使用一下吧，记录一下现在在的点坐标
	for(int v=1;v<=m;v++){//时间给的足，不需要提前记录 
		if(!edge[v][1]){
			continue ;
		}
		for(int i=2;i<=m;i++){
			if(edge[v][i]){
				xx=max(xx,i);
			}
			else{
				break ;
			}
		}
	}
	int ans=1;//我们已经选了上一个了，ans初始化为 1 
	while(xx<m){//时间给的足，不需要提前预处理左端点和右端点 
		int xxnext=xx;
		for(int i=xx+1;i>=1;i--){
			for(int k=1;k<=m;k++){//暴力的询问每一个蓄水池是否能到达当前沙漠块（可以优化） 
				if(edge[k][i]){
					for(int j=xxnext+1;j<=m;j++){//我们优化掉无法更新答案的情况 
						if(edge[k][j]){
							xxnext=j;//我们保证小于xxnext的j进不去循环，就能优化更新 
						}
						else{
							break ;
						}
					}			
				}
			}
		}
		xx=xxnext;//前进！ 
		ans++; 
	}//如果已经可以灌溉到最后一寸土地了，那么就跳出循环 
	puts("1");
	write(ans);
	return 0;//程序中所谓“时间给的足”都是可以优化的点，比较简单，这里不在过多说明，本道题也不必要 
}

The End!

评论

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

正在加载评论...