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