题解 P3740 【[HAOI2014]贴海报】
Azazеl
·
·
题解
#### 1.简介
$\ \ \ \ \ \ \ $这个算法的受众面似乎很小呢,目前好像除了**区间染色问题**之外没有什么其他的题可用了。但它可以节省不少码量的,调试难度更小一些。~~想想区间染色问题一般是什么算法~~
#### 2.大致思路
$\ \ \ \ \ \ \ $我们先放一道 ~~板~~ 例题[浴谷链接](https://www.luogu.com.cn/problem/P3740)
$\ \ \ \ \ \ \ $上面这道题浮水法的思路其实很简单。我们只要把整个看成一池池水。（雾
$\ \ \ \ \ \ \ $具体的话,我们举个例子。
```
100 3
1 9
2 4
6 8
```
$\ \ \ \ \ \ \ $首先建一个平面直角坐标系,每一个整点我们都可以放上一个数字表示那是第几幅海报。
$\ \ \ \ \ \ \ $倒序(最后贴上去的一定是能看到的)遍历每一幅海报,把第 $i$ 幅海报先在 $y=i$ 这条直线上对应的位置放好。
$\ \ \ \ \ \ \ $举个例子,最后两幅海报放上去就会成这个样子。
$\ \ \ \ \ \ \ $由于棕色海报前面没有任何遮挡,因此它是可以被看见的,$ans+1$ 。
$\ \ \ \ \ \ \ $再放一幅上去,图就是这个样子.
$\ \ \ \ \ \ \ $由于紫色海报一部分前面还是没有遮挡,因此它可以被看见。
$\ \ \ \ \ \ \ $可惜电脑不像人一样,能够一眼看出来之前有没有遮挡。所以对于每一幅海报,我们可以将它没有被上一幅海报覆盖的区间上浮,其余的留在原处.最后只要有任意一部分浮到最顶端就可以判断它能被看到.
$\ \ \ \ \ \ \ $刚刚那幅图上浮一次变成
$\ \ \ \ \ \ \ $再上浮一次变成
$\ \ \ \ \ \ \ $然后由于它已经上浮到最表面了,因此它是可以被记入答案的.
$\ \ \ \ \ \ \ $对于之后的每一幅海报,我们都做一次这样的上浮即可.
#### 3.实际实现
$\ \ \ \ \ \ \ $首先先声明,这个算法其实是玄学复杂度( $\Theta(N+$很小的常数$)$ )(不会证明),但是它跟线段树是差不多的.请放心食用。
$\ \ \ \ \ \ \ $对于每一幅先贴上去的海报,它最多有三种情况,**左半部分、被挡住部分、右半部分**
$\ \ \ \ \ \ \ $所以我们用 $while$ 循环不停地对比它是否能整体直接上浮并进行操作,如果不能就只能把它拆成两部分(**左半部分、右半部分**)进行上浮,依次类推,直到上浮至最高层.
$\ \ \ \ \ \ \ $所以这个操作也告诉我们这是**递归**。
$\ \ \ \ \ \ \ $具体操作时还有两个注意事项:
$\ \ \ \ \ \ \ 1.$如果有线段刚好端点相接的情况也是要算覆盖的,但是实际时不会被计算,因此我们让右端点延长 $1$ 个单位长度即可.
$\ \ \ \ \ \ \ 2.$它有可能会在递归过程中多次上浮同一条线段的不同部分,因此我们需要开 $vis
\mathcal{CODE}
#include <cstdio>
bool vis[1005];
int n,m,ans,A[1005],B[1005];
void Solve(int a,int b,int now,int num)
{
if(vis[num]) return;//Warning 2
while(now<=m&&(a>=B[now]||b<=A[now])) now++;
if(now>m) ans++,vis[num]=1;
if(a<A[now]&&A[now]<b) Solve(a,A[now],now+1,num);
if(b>B[now]&&B[now]>a) Solve(B[now],b,now+1,num);
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&A[i],&B[i]);
B[i]++;//Warning 1
}
for(int i=m-1;i>=1;i--) Solve(A[i],B[i],i+1,i);
printf("%d",ans+1);
return 0;
}