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
4说明/提示
约束条件
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;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
