P1047
题目描述
某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,…,L,都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。
输入输出格式
解法1:循环打表
思路:
第一遍,利用0和1标记,若已经移树,则为1.
第二遍,直接在输入的循环里判断、标记。
第三遍,最后再过一遍,计数。
【代码】
#include <bits/stdc++.h> using namespace std; int main(){ int i,j,k,m,n,l,sum=0; int a[10001],q,z; cin>>l>>m; for(i=0;i<=l;i++) a[i]=0; for(i=1;i<=m;i++){ cin>>q>>z; for(j=q;j<=z;j++) if(a[j]==0) a[j]++; } for(i=0;i<=l;i++) if(a[i]==0) sum++; cout<<sum; return 0; }
解法2:差分数组
思路:
tree记录每个人砍树的开头和结尾。
cut记录一棵树被多少人砍。
把不同次数的砍树看做不同的人砍树
第一步:输入,并记录每次砍树的开头和结尾。
第二步:扫描,同时更新cut。
如果cut==0,那么说明这棵树没有被(残暴的人类)砍伐。
否则,则有人砍这棵树,这棵树活不下来。
由于这里把区间计算变成了端点的计算,所以是差分法。
差分法利用范围比较广,只要可以把区间计算变成端点计算,都可以用差分法,而且时间复杂度一般比较小,实用性强。
【代码】
#include<bits/stdc++.h> using namespace std; int main() { int tree[10010]; int leight=0,moved=0,result=0; cin>>leight>>moved; for(int i=0;i<10010;i++) tree[i]=0; while(moved--) { int start=0,end=0; cin>>start>>end; tree[start]++; tree[end+1]--; } for(int i=0,cut=0;i<=leight;i++) { cut+=tree[i]; if(cut<=0) result++; } cout<<result<<endl; return 0; }
解法3:线段树
【代码】
#include <bits/stdc++.h> #define re register #define FOR(i,l,r) for(re int i=l;i<=r;++i) using namespace std; int a[100001],ans[100001],tag[100001],m,n,k,l,t,cnt,x,y; inline int in(){ char ch; int a=0; while(!(((ch=getchar())>='0')&&(ch<='9'))); a*=10;a+=ch-'0'; while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0'; return a; } inline void out(int a){ if(a>=10)out(a/10); putchar(a%10+'0'); } inline int ls(int ss){ return ss<<1; } inline int rs(int ss){ return (ss<<1)|1; } inline void push_up(int k){ ans[k]=ans[ls(k)]+ans[rs(k)]; } inline void push_down(int i){ if(tag[i]){ tag[i]=0; tag[ls(i)]=1; tag[rs(i)]=1; ans[ls(i)]=0; ans[rs(i)]=0; } } inline void build(int p,int l,int r){ if(l==r){ ans[p]=1; return; } int mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p); } inline void update(int nl,int nr,int l,int r,int p){ if(nl<=l&&r<=nr){ tag[p]=1; ans[p]=0; return; } push_down(p); int mid=(l+r)>>1; if(nl<=mid) update(nl,nr,l,mid,ls(p)); if(nr>mid) update(nl,nr,mid+1,r,rs(p)); push_up(p); } int main(){ n=in(),m=in(); build(1,1,n+1); FOR(i,1,m){ x=in(),y=in(); update(x+1,y+1,1,n+1,1); } out(ans[1]); puts(""); }
解法4:分块
【代码】
#include<bits/stdc++.h> #define maxn 500010 #define re register #define FOR(i,l,r) for(re int i=l;i<=r;++i) using namespace std; int n,m,c,r,t,x,y,z,sq,anss; int a[maxn],b[maxn],tag[maxn],ans[maxn]; inline void in(int &x){ x=0;char c=getchar(); while(c<'0'||c>'9'){ c=getchar(); } while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+(c^'0'); c=getchar(); } } inline void out(int a){ if(a>=10)out(a/10); putchar(a%10+'0'); } void doit(int x,int y){ if(tag[b[x]]!=1) FOR(i,x,min(y,b[x]*sq)) ans[b[x]]-=a[i],a[i]=0; if(b[x]!=b[y]&&tag[b[y]]!=1) FOR(i,(b[y]-1)*sq+1,y) ans[b[y]]-=a[i],a[i]=0; FOR(i,b[x]+1,b[y]-1) tag[i]=1,ans[i]=0; } int main(){ in(n),in(m); sq=sqrt(n); FOR(i,0,n) a[i]=1,b[i]=(i-1)/sq+1,++ans[b[i]]; FOR(i,1,m){ in(x),in(y); doit(x,y); } FOR(i,1,b[n]) anss+=ans[i]; out(anss); puts(""); }
解法5:树状数组
思路:
树状数组的经典应用二:区间更新、单点查询,维护的是数列的差分数组(t[i]=a[i]-a[i-1]),区间加就显得很方便,log n 求一遍前缀和就是单点查询了了,巧妙的转化了问题。
唯一需要注意的点是,由于二进制的特殊性,树状数组中 0 下标是不能用的,然而这道题需要 0,所以我们需要将整个树状数组向右平移一位。
【代码】
#include<cstdio> int l,t[10005]; //树状数组经典函数,没什么好说的 void add(int x,int y){ if(!x)return; for(;x<=l+1;x+=x&-x)//平移一位 t[x]+=y; } int query(int x){ int s=0; for(;x;x-=x&-x) s+=t[x]; return s; } int main(){ int m,x,y; scanf("%d%d",&l,&m); while(m--){ scanf("%d%d",&x,&y); add(x+1,1);//原来应该是 [x..n]++, [y+1..n]-- 实现区间加,这里平移一位以凸显 0,无伤大雅。 add(y+2,-1); } int ans=0; for(int i=1;i<=l+1;i++)//同样 [0..l] 平移至 [1..l+1] ans+=query(i)==0;//如果为 0 则说明这里没有被砍伐过,累计入答案 printf("%d ",ans); return 0; }
解法6:珂朵莉树
解释:
珂朵莉树是一种基于set的暴力数据结构
珂朵莉树的关键在于推平一段区间,即把一段区间的数变的一样(似乎所有珂朵莉树的讲解里面都说了这一句话)
对每一个点建立一个集合
当需要修改的时候,就把要修改区间分成两部分,一部分是需要修改的,一部分是不需要修改的,返回需要修改的地址;
然后把这一段区间内所有的集合都删掉,用一个大集合代替之就可以了。
【代码】
1 #include <bits/stdc++.h> 2 #define re register 3 #define FOR(i,l,r) for(re int i=l;i<=r;++i) 4 #define IT set<node>::iterator 5 using namespace std; 6 7 int n,m,x,y; 8 9 inline void in(re int &x){ 10 x=0;char c=getchar(); 11 while(c<'0'||c>'9'){ 12 c=getchar(); 13 } 14 while(c<='9'&&c>='0'){ 15 x=(x<<1)+(x<<3)+(c^'0'); 16 c=getchar(); 17 } 18 } 19 20 inline void out(re int a){ 21 if(a>=10)out(a/10); 22 putchar(a%10+'0'); 23 } 24 25 struct node{ 26 int l,r; 27 mutable int v; 28 node(int L,int R=-1,int V=0):l(L),r(R),v(V) {} 29 bool operator <(const node &o)const{ 30 return l<o.l; 31 } 32 }; 33 34 set<node> s; 35 36 inline IT split(re int pos){ 37 IT it=s.lower_bound(node(pos)); 38 if(it!=s.end()&&it->l==pos) 39 return it; 40 --it; 41 int L=it->l; 42 int R=it->r; 43 int V=it->v; 44 s.erase(it); 45 s.insert(node(L,pos-1,V)); 46 return s.insert(node(pos,R,V)).first; 47 } 48 49 inline void assign_val(re int l,re int r,re int val=0){ 50 IT itr=split(r+1),itl=split(l); 51 s.erase(itl,itr); 52 s.insert(node(l,r,val)); 53 } 54 55 inline int query(re int l,re int r){ 56 int res=0; 57 IT itr=split(r+1),itl=split(l); 58 for(;itl!=itr;++itl) 59 res+=(itl->r-itl->l+1)*(itl->v); 60 return res; 61 } 62 63 int main(){ 64 in(n),in(m); 65 s.insert(node(0,n,1)); 66 FOR(i,1,m){ 67 in(x),in(y); 68 assign_val(x,y,0); 69 } 70 out(query(0,n)); 71 puts(""); 72 } 73