xth 砍树

2019-11-06 06:10:40

字体：大中小

来源：转载

供稿：网友

题目描述

在一个凉爽的夏夜，xth和rabbit来到花园里砍树。为啥米要砍树呢?是这样滴，小菜儿的儿子窄森要出生了。xth这个做伯伯的自然要做点什么。于是他决定带着rabbit去收集一些木材，给窄森做一个婴儿车……( xth早就梦想着要天天打菜儿他儿窄森的小PP，到时候在婴儿车里安装一个电子遥控手臂，轻轻一按，啪啪啪……“乌卡卡一一”xth牙区恶滴笑了，“不要告诉rabbit，她会说我缺德的……”xth如是说)。花园里共有n棵树。为了花园的整体形象，rabbit要求xth只能在m个区域砍伐，我们可以将这m个区域看成m个区间，树的间距相等，都是1，我们将每个区间设为[x,y]。那么长度为k的区间中就有k棵树。树木的高度不等。现在xth想测量一下，每个区间树木砍伐后所得的木材量是多少，而且每次测量后他都会砍下标号为(x+y)/2的那棵作为纪念。以方便他安排人手。(同一个区间的树木可以重复砍伐，我们认为被砍过的树木高度为0)每棵树的木材量=树的高度*3.14(注意是3.14不是π)。

输入

第一行，一个整数n。第二行，共n个整数，表示每棵树的高度。第三行，一个整数m，表示共m个区间。以下m行，每个区间[x, y]的左右端点x, y。

输出

共m行，每行一个数，表示每个区间的木材量。结果精确到小数点后两位。

样例输入

5 1 2 3 4 5 2 1 4 2 4

样例输出

31.40 21.98

提示

数据规模

对于30%的数据，有n ≤ 5000,m ≤ 5000; 对于100%的数据，有n ≤ 200000,m ≤ 200000;

样例解释

第一次砍[1,4] 的树后，森林变为：1 0 3 4 5

分析

做题前先思考这道题水不水，再来做。O(∩_∩)O … —zjf

测试链接

首先这点题还是用树状数组。（~~怎么还是树状数组~~，(⊙﹏⊙)b）然后我们把常用的几个函数加上。这点题其实有一个地方，如果稍微不仔细一点读题，会死得很惨。等一下我们再来说这个坑的地方。

#include<cstdio>#define lowbit(x) (x&-x)int tree[200005],f[200005];void update(int pos,int val){ while(pos<=n){ tree[pos]+=val; pos+=lowbit(pos); } }int getsum(int x){ int sum=0; while(x>0){ sum+=tree[x]; x-=lowbit(x); } return sum;}

.

回去链接–>这里看到了吧，前面一切都很顺利，因为坑的地方还没有来，我们可以很轻松的码下程序的主函数：

int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&f[i]); update(i,f[i]); } scanf("%d",&m); while(m--){ int x,y; scanf("%d%d",&x,&y); PRintf("%.2lf/n",(getsum(y)-getsum(x-1))*3.14); int p=(x+y)/2; update(p,-f[p]); }}

坑点

让我们来轻松（zuōsǐ）的来测一组数据。。。

5 1 1 1 1 1 3 1 5 2 4 3 3

然后呢……

（我写成一行是为了好观察输出~~~）

答案是 15.70 6.28 -3.14

what，负数是什么意思？肯定是哪里错了。。。请大家看到主函数第14行，直达–>这里

.

注意了：原题如下

花园里共有n棵树。为了花园的整体形象，rabbit要求xth只能在m个区域砍伐，我们可以将这m个区域看成m个区间，树的间距相等，都是1，我们将每个区间设为[x,y]。那么长度为k的区间中就有k棵树。树木的高度不等。现在xth想测量一下，每个区间树木砍伐后所得的木材量是多少，而且每次测量后他都会砍下标号为(x+y)/2的那棵作为纪念。以方便他安排人手。(同一个区间的树木可以重复砍伐，我们认为被砍过的树木高度为0)每棵树的木材量=树的高度*3.14(注意是3.14不是π)。

没有什么不对的呀。╮(╯_╰)╭ 在这里↓↓↓↓↓

同一个区间的树木可以重复砍伐

O(∩_∩)O哈哈哈~，所以我们要把源程序修改一下，加上下面的第14行。if(getsum(p)-getsum(p-1))，其实这是判断这个地方是否为0，然后在加减的。被坑了吧。。。我第一次也是因为这样一分都没有得到的。。。

int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&f[i]); update(i,f[i]); } scanf("%d",&m); while(m--){ int x,y; scanf("%d%d",&x,&y); printf("%.2lf/n",(getsum(y)-getsum(x-1))*3.14); int p=(x+y)/2; if(getsum(p)-getsum(p-1)) update(p,-f[p]); }}

下面是AC代码。

源代码

#include<cstdio>#define lowbit(x) (x&-x)int tree[200005],f[200005];int n,m;void update(int pos,int val){ while(pos<=n){ tree[pos]+=val; pos+=lowbit(pos); } }int getsum(int x){ int sum=0; while(x>0){ sum+=tree[x]; x-=lowbit(x); } return sum;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&f[i]); update(i,f[i]); } scanf("%d",&m); while(m--){ int x,y; scanf("%d%d",&x,&y); printf("%.2lf/n",(getsum(y)-getsum(x-1))*3.14); int p=(x+y)/2; if(getsum(p)-getsum(p-1)) update(p,-f[p]); }}

上一篇：hdu 2196 Computer（树形DP）

下一篇：38.表单