[NOIP2010 提高组] 引水入城

做题的时候最后一个点怎么调都调不对，所以写一篇题解庆祝一下AC

题目描述

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 \(N\) 行 \(M\) 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此，只有与湖泊毗邻的第 \(1\) 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 \(N\) 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

数据范围

\(1 \le N,M \le 500\)

对于所有 10 个数据，每座城市的海拔高度都不超过 \(10^6\)。

解题思路

这个数据范围很明显了，直接爆搜。

搜索就是 dfs 模板，只是递归的时候条件要加上只能走到更低的地方，这个不是本题重点。

重点是怎么判断是否可以满足要求。

让我们先分情况讨论：

如果不符合要求，只需要在搜索的时候用 vis 数组记录下是否抵达了最后一行的所有点。最后一行中没被搜索到的点的个数即为不可能建有水利设施的数量。

如果符合要求，可以证明从一个点出发，能抵达的最后一行上的点一定是连续的。

证明：

假设不是连续的，那么中间空过去的点所在连通块（下称E点）一定被这个点（下称S点）发出的水流包围，又因为符合要求，所以从别的点一定有一条路径可以到达E点，那么这条路径一定与S点发出的路径有交点，所以从S点出发也能到达E点，与假设矛盾，所以假设不成立。

证毕。

那么思路就很明显了，先判断能否满足要求，如果可以，就找到每个点能抵达的最后一行的区间两端点，对于这些点贪心的进行一个线段覆盖就好了。

对于线段覆盖我感觉这篇讲的很详细。

当然，这题的细节还是有的（要不然我也不会WA那么多次）。

首先，判断能否满足要求的时候应该通过 dfs 能否抵达全部最后一行为标准，上文的证明是在满足要求的前提下，不能用线段覆盖的结果去判断能否全部抵达

不然你会喜提

byd ，这题最离谱的是在洛谷上它报了 WA，我下载数据本地报了RE

Code

// Problem: 
//     P1514 [NOIP2010 提高组] 引水入城
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1514
// Problem Solving Time: 2023-12-08 14:32:22
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pos{
	int x,y;
};
struct line{
	int l,r;
	line(){
		l=INT_MAX,r=INT_MIN;//初始化函数
	}
}lin[505];
int n,m,dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int mp[505][505];
bool vis[505][505],vp[505];
bool cmp(line lhs,line rhs){//排序，线段覆盖的时候用的
	return lhs.l<rhs.l||(lhs.r>rhs.r&&lhs.l==rhs.l);
}
void dfs(int k,pos p){
	if(p.x==n){
		lin[k].l=min(lin[k].l,p.y);
		lin[k].r=max(lin[k].r,p.y);
		vp[p.y]=1;//记录最后一行能否全部抵达
	}
	for(int i=0;i<4;i++){
		int x=dir[i][0]+p.x,y=dir[i][1]+p.y;
		if(!vis[x][y]&&mp[x][y]<mp[p.x][p.y]){
			vis[x][y]=1;
			dfs(k,(pos){x,y});
		}
	}
}
int main(){
	cin>>n>>m;
	memset(mp,0x3f,sizeof(mp));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mp[i][j];
	for(int i=1;i<=m;i++)
		if(!vis[1][i]){//递归，别忘了清空记录
			memset(vis,0,sizeof(vis));
			dfs(i,(pos){1,i});
		}
	sort(lin+1,lin+1+m,cmp);
	int cnt=0;
	bool flag=1;
	for(int i=1;i<=m;i++)//先判断是否成立
		if(!vp[i]){
			cnt++;
			flag=0;
		}
	if(!flag){
		cout<<"0\n"<<cnt;
		return 0;
	}
	int len=1;
	while(len<=m){//线段覆盖贪心
		int ep=len;
		int i=1;
		while(lin[i].l<=len&&i<=m)
			ep=max(ep,lin[i].r),i++;
		cnt++,len=ep+1;
	}
	cout<<1<<endl<<cnt;
	return 0;
}