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

打卡信奥刷题（2540）用C++实现信奥 P2070 [USACO13JAN] 刷墙 Painting the Fence B

news 2026/7/27 19:20:55

P2070 [USACO13JAN] 刷墙 Painting the Fence B

题目描述

Farmer John 已经设计了一种方法来装饰谷仓旁边的长栅栏（把栅栏认为是一根一维的线）。他把一只画刷绑在他最喜爱的奶牛 Bessie 身上，之后就去喝一杯冰水，而 Bessie 隔着栅栏来回走，当她走过某个地方，这里的一段栅栏就被刷上了涂料。

Bessie 从栅栏上的位置000开始，并且遵循着一个NNN次移动的次序（1≤N≤1051\le N\le10^51≤N≤105）。例如10 L表示 Bessie 向左移动了101010个单位长度，15 R表示 Bessie 向右移动了151515个单位长度。现给出 Bessie 所有移动的列表，Farmer John 想要知道哪些区域的栅栏至少涂了两层涂料（只涂一层涂料的区域可能在大雨中被洗掉）。Bessie 在她的行走中最远到达距起始点10910^9109个单位长度。

输入格式

第111行：一个整型数NNN。

第2∼N+12 \sim N+12∼N+1行：每行描述了 Bessie 的NNN次移动中的一次，例如15 L。

输出格式

111行：被至少涂了两层涂料的区域总数。

输入输出样例 #1

输入 #1

6 2 R 6 L 1 R 8 L 1 R 2 R

输出 #1

说明/提示

【样例解释】

Bessie 从位置000开始，向右移动222个单位长度，向左移动666个单位长度，向右移动111个单位长度，向左移动888个单位长度，最后向右移动333个单位长度。

666个单位区域至少被涂了两层涂料，是[−11,−8],[−4,−3],[0,2][-11,-8],[-4,-3],[0,2][−11,−8],[−4,−3],[0,2]这些区域。

C++实现

#include<bits/stdc++.h>usingnamespacestd;template<typenameT>inlinevoidread(T&FF){T RR=1;FF=0;charCH=getchar();for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);FF*=RR;}//快读template<typenameT>voidwrite(T x){if(x<0)putchar('-'),x*=-1;if(x>9)write(x/10);putchar(x%10+48);}//快写constintMAXN=1e5+10;structnode{intl,r;//每次染色的左端点和右端点booloperator<(constnode&b)const{returnl<b.l;//按左端点从小到大排序}}a[MAXN];intposition,ans,lft,rgt,n;intmain(){read(n);for(inti=1;i<=n;i++){intx;chary;read(x);cin>>y;a[i].l=position;if(y=='L')position-=x;//Bessie往左走elseposition+=x;//Bessie往右走a[i].r=position;if(a[i].l>a[i].r)swap(a[i].l,a[i].r);}sort(a+1,a+n+1);//排序lft=a[1].l;rgt=a[1].r;//给lft和rgt赋上初值for(inti=2;i<=n;i++)if(a[i].r>lft){//如果跟可能被覆盖到的区间有交a[i].l=max(a[i].l,lft);//这里是使得之后的代码可以少写一点，因为显然，a[i].l<lft，a[i].l~lft这1段也没有用了if(a[i].r>rgt){//比之前的右端点大ans+=rgt-a[i].l;//从rgt到a[i].llft=rgt;//之前的右端点显然就是左端点，显然，新的可能被覆盖到的区间就是之前的rgt~a[i].rrgt=a[i].r;//更新右端点}else{//比之前的右端点小ans+=a[i].r-a[i].l;//从a[i].r到a[i].llft=a[i].r;//更新左端点}}write(ans);//输出return0;}