校門外的樹

描述

某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個(gè)數(shù)軸，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù)軸上的每個(gè)整數(shù)點(diǎn)，即0，1，2，……，L，都種有一棵樹。

由于馬路上有一些區(qū)域要用來建地鐵。這些區(qū)域用它們在數(shù)軸上的起始點(diǎn)和終止點(diǎn)表示。 已知任一區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分。現(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點(diǎn)處的兩棵樹）移走。你的任務(wù)是計(jì)算將這些樹都移走后，馬路上還有多少棵樹。

格式

輸入格式

輸入的第一行有兩個(gè)整數(shù)：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區(qū)域的數(shù)目，L和M之間用一個(gè)空格隔開。接下來的M行每行包含兩個(gè)不同的整數(shù)，用一個(gè)空格隔開，表示一個(gè)區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)。

輸出格式

輸出包括一行，這一行只包含一個(gè)整數(shù)，表示馬路上剩余的樹的數(shù)目。

樣例1

樣例輸入1

500 3 150 300 100 200 470 471

樣例輸出1

298

限制

每個(gè)測試點(diǎn)1s

來源

NOIP2005普及組第二題

題目鏈接：https://vijos.org/p/1103

思路：我估計(jì)也是智障了，這題明顯可以用模擬做，我TM竟然用線段樹寫，還RE了兩發(fā)，數(shù)組開了四倍你還要我怎樣，結(jié)果我開了八倍過了QAQ！

下面給出線段樹寫法：

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=20010; 4 int n,m,ans=1; 5 struct Node 6 { 7 int l,r,sum; 8 }tree[N<<2]; 9 inline void buildtree(int l,int r,int pos) 10 { 11 tree[pos].l=l; 12 tree[pos].r=r; 13 if(l==r) 14 { 15 tree[pos].sum=1; 16 return; 17 } 18 int mid=(tree[pos].l+tree[pos].r)/2; 19 buildtree(l,mid,pos*2); 20 buildtree(mid+1,r,pos*2+1); 21 tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum; 22 } 23 inline int query(int l,int r,int pos) 24 { 25 if(tree[pos].l==l&&tree[pos].r==r) 26 return tree[pos].sum; 27 if(tree[pos].r<l||tree[pos].l>r) 28 return 0; 29 return query(l,r,pos*2)+query(l,r,pos*2+1); 30 } 31 inline void update(int l,int r,int pos) 32 { 33 if(tree[pos].l==l&&tree[pos].r==r) 34 { 35 tree[pos].sum=0; 36 return; 37 } 38 if(tree[pos].l>r||tree[pos].r<l) 39 return; 40 update(l,r,pos*2); 41 update(l,r,pos*2+1); 42 tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum; 43 } 44 int main() 45 { 46 cin>>n>>m; 47 buildtree(1,n,1); 48 for(int i=1;i<=m;i++) 49 { 50 int l,r; 51 scanf("%d%d",&l,&r); 52 if(!l) 53 ans=0; 54 update(!l?1:l,r,1); 55 } 56 cout<<query(1,n,1)+ans<<endl; 57 return 0; 58 }

模擬做法：簡單解釋一下，做法就是在【0,r】我們?nèi)抠x值為1，然后for一遍刪去重復(fù)部分，非常簡單，智障的我開始沒想到，但是如果這題L的數(shù)據(jù)是1000000，線段樹依然是正解！QAQ

下面給出模擬的代碼：

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=10010; 4 int a[N]; 5 int main() 6 { 7 int n,m; 8 cin>>n>>m; 9 for(int i=0;i<=n;i++) 10 a[i]=1; 11 for(int i=1;i<=m;i++) 12 { 13 int l,r; 14 cin>>l>>r; 15 for(int j=l;j<=r;j++) 16 { 17 a[j]=0; 18 } 19 } 20 int sum=0; 21 for(int i=0;i<=n;i++) 22 { 23 if(a[i]) 24 sum++; 25 } 26 cout<<sum<<endl; 27 return 0; 28 }

?

總結(jié)

以上是生活随笔為你收集整理的Vijos P1103 校门外的树【线段树，模拟】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。