当前位置：首页 > news >正文

打卡信奥刷题（2759）用C++实现信奥题 P3740 [HAOI2014] 贴海报

news 2026/5/11 19:01:24

P3740 [HAOI2014] 贴海报

题目描述

Bytetown 城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的 electoral 墙。

张贴规则如下：

electoral 墙是一个长度为N NN个单位的长方形，每个单位记为一个格子；
所有张贴的海报的高度必须与 electoral 墙的高度一致的；
每张海报以A B表示，即从第A AA个格子到第B BB个格子张贴海报；
后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断，张贴完所有海报后，在 electoral 墙上还可以看见多少张海报。

输入格式

第一行，两个正整数N , M N,MN,M，分别表示 electoral 墙的长度和海报个数。

接下来M MM行，每行两个正整数A i , B i A_i,B_iAi,Bi，表示每张海报张贴的位置。

输出格式

输出贴完所有海报后，在 electoral 墙上还可以看见的海报数。

输入输出样例 #1

输入 #1

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

输出 #1

说明/提示

约束条件

10 ≤ N ≤ 10000000 , 1 ≤ M ≤ 1000 , 1 ≤ A i ≤ B i ≤ 10000000 10\le N \le 10000000,1\le M\le 1000,1\le A_i \le B_i \le 1000000010≤N≤10000000,1≤M≤1000,1≤Ai≤Bi≤10000000

所有的数据都是正整数，数据之间有一个空格。

C++实现

#include<cstdio>usingnamespacestd;constintN=10000005,M=1005;intn,m,Ans,cur,A[M],B[M];boolvis[M];intread(){intnow=0;charc=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar();returnnow;}voidSolve(inta,intb,intnow){if(vis[cur])return;while(now<=m&&(a>=B[now]||b<=A[now]))//需要等于++now;if(now>m)++Ans,vis[cur]=1;//printf("%d:%d--%d\n",Ans,a,b);if(a<A[now]&&A[now]<b)Solve(a,A[now],now+1);//不能等于if(b>B[now]&&B[now]>a)Solve(B[now],b,now+1);}intmain(){n=read();m=read();for(inti=1;i<=m;i++)A[i]=read(),B[i]=read(),++B[i];for(cur=m-1;cur>=1;cur--)Solve(A[cur],B[cur],cur+1);printf("%d",++Ans);return0;}