洛谷P1514 [NOIP 2010 提高組] 引水入城

洛谷題目傳送門

題目背景

NOIP2010 提高組 T4

題目描述

在一個遙遠的國度，一側是風景秀美的湖泊，另一側則是漫無邊際的沙漠。該國的行政區劃十分特殊，剛好構成一個 $N$ 行 $M$ 列的矩形，如上圖所示，其中每個格子都代表一座城市，每座城市都有一個海拔高度。

為了使居民們都盡可能飲用到清澈的湖水，現在要在某些城市建造水利設施。水利設施有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。

因此，只有與湖泊毗鄰的第 $1$ 行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經建有水利設施。由于第 $N$ 行的城市靠近沙漠，是該國的干旱區，所以要求其中的每座城市都建有水利設施。那么，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求干旱區中不可能建有水利設施的城市數目。

輸入格式

每行兩個數，之間用一個空格隔開。輸入的第一行是兩個正整數 $N,M$，表示矩形的規模。接下來 $N$ 行，每行 $M$ 個正整數，依次代表每座城市的海拔高度。

輸出格式

兩行。如果能滿足要求，輸出的第一行是整數 $1$，第二行是一個整數，代表最少建造幾個蓄水廠；如果不能滿足要求，輸出的第一行是整數 $0$，第二行是一個整數，代表有幾座干旱區中的城市不可能建有水利設施。

輸入輸出樣例 #1

輸入 #1

2 5
9 1 5 4 3
8 7 6 1 2

輸出 #1

1
1

輸入輸出樣例 #2

輸入 #2

3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2

輸出 #2

1
3

說明/提示

樣例 1 說明

只需要在海拔為 $9$ 的那座城市中建造蓄水廠，即可滿足要求。

樣例 2 說明

上圖中，在 $3 $ 個粗線框出的城市中建造蓄水廠，可以滿足要求。以這 $3 $ 個蓄水廠為源頭在干旱區中建造的輸水站分別用 $3$ 種顏色標出。當然，建造方法可能不唯一。

數據范圍

本題有 10 個測試數據，每個數據的范圍如下表所示：

測試數據編號	能否滿足要求	$N\le$	$M\le$
1	不能	$10$	$10$
2	不能	$100$	$100$
3	不能	$500$	$500$
4	能	$1$	$10$
5	能	$10$	$10$
6	能	$100$	$20$
7	能	$100$	$50$
8	能	$100$	$100$
9	能	$200$	$200$
10	能	$500$	$500$

對于所有 10 個數據，每座城市的海拔高度都不超過 $10^6$。

思路詳解

我們發現，一條河流可以流到的干旱城市是固定的，考慮直接將他預處理出來。我們發現倘使一條河流對應一個連續區間，那我們直接貪心即可，但如果不呢？？？如果問題不能解決，那考慮如何解決掉問題。考慮如何證明一定是一條連續區間。

連續區間

對于無解的情況，我們肯定不需要討論，因為我們可以直接標記。那對于有解的情況，如何證明每個河流對應的一定是一個連續區間的。考慮使用反證法，如下圖：

假如$x$可以流到下端藍線除了紅點的城市，由于有解，則必有如下城市可以到達紅點：

我們發現$x$，$y$的流徑一定有交點，不然$y$不可能憑空到達紅點。那么你$y$都可以走，則$x$肯定可以走到，那$x$流經地區一定是一個連續區間，那接下來就好辦了。

大致思路

大致思路如下：

1. 我們先以每個河流為起點，深搜求解每個河流可以流經的區間。
2. 然后在檢查干旱城市是否都可以被灌溉，如果不是統計有多少個，輸出即可。
3. 如果都可以，則對應每個區間，我們以已有區間右邊界的右邊一個為起點，若新區間的的左端點小于等于起點，則取右端點的最大值為新的右邊界。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
int a[N][N],vis[N][N];
struct node{int x,y;
}c[N][N];//c[i][j]為從(i,j)開始可以流到的區間
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
int jsq=0;
void dfs(int bx,int by){//深搜求解vis[bx][by]=1;for(int i=0;i<4;i++){auto [qx,qy]=(node){bx+dx[i],by+dy[i]};if(qx<1||qx>n||qy<1||qy>m||a[qx][qy]>=a[bx][by])continue;if(!vis[qx][qy]){//注意，訪問過的點也可以更新他的值vis[qx][qy]=1;dfs(qx,qy);}c[bx][by].x=min(c[bx][by].x,c[qx][qy].x);c[bx][by].y=max(c[bx][by].y,c[qx][qy].y);}
}
int ans=0;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)c[i][j].x=0x3f3f3f3f;}//賦初值for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(i==n)c[i][j]={j,j};//邊界}}for(int i=1;i<=m;i++){//枚舉并深搜if(!vis[1][i])dfs(1,i);}for(int i=1;i<=m;i++)if(!vis[n][i])ans++;//記錄有多少個點流不到if(ans>0){//有城市流不到cout<<0<<'\n'<<ans;}else{cout<<1<<'\n';ans=0;int l=1,r=0;while(l<=m){//貪心for(int i=1;i<=m;i++){if(c[1][i].x<=l)r=max(r,c[1][i].y);}l=r+1;ans++;}cout<<ans;}return 0;
}