首页 > ACM题库 > HDU-杭电 > HDU 2781-HOJ-Tanks a Lot-线段树-[解题报告]C++
2014
02-14

HDU 2781-HOJ-Tanks a Lot-线段树-[解题报告]C++

Tanks a Lot

问题描述 :

Imagine you have a car with a very large gas tank – large enough to hold whatever amount you need. You are traveling on a circular route on which there are a number of gas stations. The total gas in all the stations is exactly the amount it takes to travel around the circuit once. When you arrive at a gas station, you add all of that station’s gas to your tank. Starting with an empty tank, it turns out there is at least one station to start, and a direction (clockwise or counter-clockwise) where you can make it around the circuit. (On the way home, you might ponder why this is the case – but trust us, it is.)

Given the distance around the circuit, the locations of the gas stations, and the number of miles your car could go using just the gas at each station, find all the stations and directions you can start at and make it around the circuit.

输入:

There will be a sequence of test cases. Each test case begins with a line containing two positive integers c and s , representing the total circumference, in miles, of the circle and the total number of gas stations. Following this are s pairs of integers t and m . In each pair, t is an integer between 0 and c – 1 measuring the clockwise location (from some arbitrary fixed point on the circle) around the circumference of one of the gas stations and m is the number of miles that can be driven using all of the gas at the station. All of the locations are distinct and the maximum value of c is 100,000. The last test case is followed by a pair of 0′s.

输出:

There will be a sequence of test cases. Each test case begins with a line containing two positive integers c and s , representing the total circumference, in miles, of the circle and the total number of gas stations. Following this are s pairs of integers t and m . In each pair, t is an integer between 0 and c – 1 measuring the clockwise location (from some arbitrary fixed point on the circle) around the circumference of one of the gas stations and m is the number of miles that can be driven using all of the gas at the station. All of the locations are distinct and the maximum value of c is 100,000. The last test case is followed by a pair of 0′s.

样例输入:

10 4 
2 3 4 3 6 1 9 3 
5 5 
0 1 4 1 2 1 3 1 1 1 
0 0

样例输出:

Case 1: 2 C 4 CC 9 C 
Case 2: 0 CCC 1 CCC 2 CCC 3 CCC 4 CCC

http://acm.hdu.edu.cn/showproblem.php?pid=2871

线段树的各种综合

单点更新,区间合并

 

#include <cstdio> 
 using namespace std; 
 
 #define lch (rt<<1) 
 #define rch (rt<<1|1) 
 const int N=50010; 
 int u[N],v[N],se; 
 struct node 
 { 
 int l,r; 
 int len() {return r-l+1;} 
 int s,ls,rs,cnt,c; 
 }st[N*4]; 
 int max(int x,int y,int z) 
 { 
 int t=x>y?x:y; 
 return t>z?t:z; 
 } 
 void build(int l,int r,int rt) 
 { 
 st[rt].l=l; st[rt].r=r; 
 st[rt].s=st[rt].ls=st[rt].rs=r-l+1; 
 st[rt].cnt=0; st[rt].c=-1; 
 if(l==r) return; 
 int m=(l+r)/2; 
 build(l,m,lch); 
 build(m+1,r,rch); 
 } 
 void pushdown(int rt) 
 { 
 if(st[rt].c==-1) return; 
 st[lch].c=st[rch].c=st[rt].c; 
 if(st[rt].c==0) 
 { 
 st[lch].s=st[lch].ls=st[lch].rs=st[lch].len(); 
 st[rch].s=st[rch].ls=st[rch].rs=st[rch].len(); 
 } 
 else st[lch].s=st[lch].ls=st[lch].rs=st[rch].s=st[rch].ls=st[rch].rs=0; 
 st[rt].c=-1; 
 } 
 void pushup(int rt) 
 { 
 st[rt].s=max(st[lch].s,st[rch].s,st[lch].rs+st[rch].ls); 
 st[rt].ls=st[lch].ls; 
 if(st[lch].ls==st[lch].len()) st[rt].ls+=st[rch].ls; 
 st[rt].rs=st[rch].rs; 
 if(st[rch].rs==st[rch].len()) st[rt].rs+=st[lch].rs; 
 } 
 void update(int a,int b,int x,int rt) 
 { 
 int l=st[rt].l, r=st[rt].r; 
 if(a<=l && r<=b) 
 { 
 st[rt].c=x; 
 if(x==0) st[rt].s=st[rt].ls=st[rt].rs=st[rt].len(); 
 else st[rt].s=st[rt].ls=st[rt].rs=0; 
 return; 
 } 
 pushdown(rt); 
 int m=(l+r)/2; 
 if(a<=m) update(a,b,x,lch); 
 if(b>m) update(a,b,x,rch); 
 pushup(rt); 
 } 
 void update2(int a,int x,int rt) 
 { 
 int l=st[rt].l, r=st[rt].r; 
 if(l==r) 
 { 
 st[rt].cnt=x; 
 return; 
 } 
 int m=(l+r)/2; 
 if(a<=m) update2(a,x,lch); 
 else update2(a,x,rch); 
 st[rt].cnt=st[lch].cnt+st[rch].cnt; 
 } 
 int query1(int x,int rt) 
 { 
 int l=st[rt].l, r=st[rt].r; 
 if(l==r) return l; 
 pushdown(rt); 
 if(st[lch].s>=x) return query1(x,lch); 
 if(st[lch].rs+st[rch].ls>=x) return st[lch].r-st[lch].rs+1; 
 return query1(x,rch); 
 } 
 int query2(int x,int rt) 
 { 
 int l=st[rt].l, r=st[rt].r; 
 if(l==r) return st[rt].c; 
 pushdown(rt); 
 int m=(l+r)/2; 
 if(x<=m) return query2(x,lch); 
 else return query2(x,rch); 
 } 
 int query3(int x,int rt) 
 { 
 int l=st[rt].l, r=st[rt].r; 
 if(l==r) return l; 
 if(x>st[lch].cnt) return query3(x-st[lch].cnt,rch); 
 else return query3(x,lch); 
 } 
 int main() 
 { 
 int n,m; 
 while(~scanf("%d%d",&n,&m)) 
 { 
 se=0; 
 build(1,n,1); 
 st[1].c=0; 
 while(m--) 
 { 
 char op[10]; 
 scanf("%s",op); 
 if(op[0]=='R') 
 { 
 printf("Reset Now\n"); 
 update(1,n,0,1); 
 for(int i=1;i<=se;i++) update2(u[i],0,1); 
 se=0; 
 } 
 else if(op[0]=='N') 
 { 
 int x; 
 scanf("%d",&x); 
 if(x<=st[1].s) 
 { 
 int k=query1(x,1); 
 printf("New at %d\n",k); 
 se++; 
 u[se]=k; v[se]=k+x-1; 
 update(u[se],v[se],se,1); 
 update2(u[se],1,1); 
 } 
 else printf("Reject New\n"); 
 } 
 else if(op[0]=='F') 
 { 
 int x; 
 scanf("%d",&x); 
 int k=query2(x,1); 
 if(k!=0) 
 { 
 printf("Free from %d to %d\n",u[k],v[k]); 
 update(u[k],v[k],0,1); 
 update2(u[k],0,1); 
 } 
 else printf("Reject Free\n"); 
 } 
 else if(op[0]=='G') 
 { 
 int x; 
 scanf("%d",&x); 
 if(st[1].cnt>=x) 
 { 
 int k=query3(x,1); 
 printf("Get at %d\n",k); 
 } 
 else printf("Reject Get\n"); 
 } 
 } 
 printf("\n"); 
 } 
 return 0; 
 }

 

解题参考:http://www.cnblogs.com/yangcl/archive/2012/04/08/2437304.html


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3