首页 > ACM题库 > HDU-杭电 > hdu 2692 Ball -线段树-[解题报告]C++
2014
02-13

hdu 2692 Ball -线段树-[解题报告]C++

Ball

问题描述 :

Members of Wuhan University ACM Team are fond of playing little games. Ball game is one of them, which is
played with a ball on a rectangle board. The ball should be rolled from the start point to the end point. The
game board is surrounded by walls and contains rectangular obstacles with known dimensions. Obstacles will
not overlap with each other. The ball cannot leave the board, nor can it fly.

Now, you’re one of the competitors. Can you find the radius of the largest ball to complete the task?

输入:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of
test cases.Each test case is on several lines. The first line contains four integers: N, L, W, H, indicating the
number of obstacles; the length, width of the board; and the height of walls.

The coordinate of the lower-left corner is (0,0), the upper-right one is (L, W).

Each of the following N lines consists of five integers: Xi, Yi, Li, Wi, Hi, indicating the coordinate of the
lower-left corner of an obstracle and it’s length, width and height. So the upper-right corner of the obstracle
is (Xi + Li, Yi + Wi).

The last line of a test case consists of four integers: Sx, Sy, Tx, Ty which indicate the coordinates of
start point:(Sx, Sy), and end point:(Tx, Ty).

[Technical Specification]
T is an integer, and T <= 50.
N is an integer, and 0 <= N <=10.
All integers EXCEPT N are in the range [1, 1000].
You can assume those obstracles? sides are parallel to OX, OY and OZ axis, the start point and end point are
rightful(not outside the board or inside an obstracle).
All part of an obstracle is in the board.
The integers on the same line are separated by ONE space.
The test cases are separated by ONE empty line.
NO other spaces or lines will appear in the test data.

输出:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of
test cases.Each test case is on several lines. The first line contains four integers: N, L, W, H, indicating the
number of obstacles; the length, width of the board; and the height of walls.

The coordinate of the lower-left corner is (0,0), the upper-right one is (L, W).

Each of the following N lines consists of five integers: Xi, Yi, Li, Wi, Hi, indicating the coordinate of the
lower-left corner of an obstracle and it’s length, width and height. So the upper-right corner of the obstracle
is (Xi + Li, Yi + Wi).

The last line of a test case consists of four integers: Sx, Sy, Tx, Ty which indicate the coordinates of
start point:(Sx, Sy), and end point:(Tx, Ty).

[Technical Specification]
T is an integer, and T <= 50.
N is an integer, and 0 <= N <=10.
All integers EXCEPT N are in the range [1, 1000].
You can assume those obstracles? sides are parallel to OX, OY and OZ axis, the start point and end point are
rightful(not outside the board or inside an obstracle).
All part of an obstracle is in the board.
The integers on the same line are separated by ONE space.
The test cases are separated by ONE empty line.
NO other spaces or lines will appear in the test data.

样例输入:

4 
3 1000 1000 42 
102 101 3 2 468 
106 104 2 3 335 
100 107 4 1 501 
101 106 106 100 

4 1000 1000 170 
108 103 2 3 725 
105 109 4 1 479 
101 104 1 4 359 
103 101 2 2 963 
100 100 105 106 

2 1000 1000 465 
102 100 2 3 706 
106 103 2 3 146 
100 103 110 103 

0 1000 1000 282 
100 100 102 102 

样例输出:

1.00 
1.58 
2.00 
100.00 

  • HOJ 2692 Nail
    IV(线段树最大值)



传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2692

题意:墙上有钉子,可以调整钉子的高度,然后在一个区间从无穷高出放下模板,求模板下落到的高度,就是求区间内最高的钉子。

输入:每个钉子的初试坐标,操作0 k
v表示将第k个钉子调整高度到v,1 s t表示在s和t之间放下木板。

输出:对每一个1操作,输出下落到的高度。

思路:还是线段树的应用,这次添加一个高度域,在每次更新的时候,当为叶子节点时候,则直接赋值,如果不是叶子节点,高度就是子节点中的最大值。

程序

#include
<cstdio>

class
LineTree {
private:
    int l, r;
    LineTree *left, *right;
    int max(const int x,const int y) { return x > y ? x : y; }
public:
    int height;
    LineTree(int ll, int rr) {
       
l = ll, r = rr;
       
if
(ll + 1 != rr) {
           
int
mm = (ll + rr) >>
1;
           
left = new LineTree(ll, mm);
           
right = new LineTree(mm, rr);
       
} else {
           
left = NULL;
           
right = NULL;
       
}
    }
    void init() {
       
if
(left != NULL) {
           
left->init();
       
}
       
height = 0;
       
if
(right != NULL) {
           
right->init();
       
}
    }
    void update(int ll, int rr, int hh) {
       
if
(ll <= l &&
r <= rr) {
           
height = hh;
       
} else {
           
int
mm = (l + r) >>
1;
           
if
(ll < mm) {
               
left->update(ll, rr, hh);
           
}
           
if
(rr > mm) {
               
right->update(ll, rr, hh);
           
}
           
height = max(left->height, right->height);
       
}
    }
    void query(int ll, int rr, int &ans) {
       
if
(ll <= l &&
r <= rr) {
           
ans = max(ans, height);
           
return;
       
}
       
int
mm = (l + r) >>
1;
       
if
(ll < mm) {
           
left->query(ll, rr, ans);
       
}
       
if
(rr > mm) {
           
right->query(ll, rr, ans);
       
}
    }
};

int
main() {
    int n, m;
    while (scanf(“%d %d”, &n, &m) == 2) {
       
LineTree tree(0, n);
       
tree.init();
       
for
(int
i = 0; i < n; i++) {
           
int
h;
           
scanf(“%d”, &h);
           
tree.update(i, i + 1, h);
       
}
       
for
(int
i = 0; i < m; i++) {
           
int
op;
           
scanf(“%d”, &op);
           
if
(op == 0) {
               
int
k, v;
               
scanf(“%d %d”, &k, &v);
               
tree.update(k - 1, k, v);
           
} else if (op == 1) {
               
int
s, t;
               
scanf(“%d %d”, &s, &t);
               
int
ans = 0;
               
tree.query(s - 1, t, ans);
               
printf(“%dn, ans);
           
}
       
}
    }
    return 0;
}

  • HOJ 2690 Nail
    II(区间最大值RMQ)



传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2690


思路:和上题一样吧!但是最好用RMQ的ST算法。

程序

#include
<cstdio>

class
LineTree {
private:
    int l, r;
    LineTree *left, *right;
    int max(const int x,const int y) { return x > y ? x : y; }
public:
    int height;
    LineTree(int ll, int rr) {
       
l = ll, r = rr;
       
if
(ll + 1 != rr) {
           
int
mm = (ll + rr) >>
1;
           
left = new LineTree(ll, mm);
           
right = new LineTree(mm, rr);
       
} else {
           
left = NULL;
           
right = NULL;
       
}
    }
    void init() {
       
if
(left != NULL) {
           
left->init();
       
}
       
height = 0;
       
if
(right != NULL) {
           
right->init();
       
}
    }
    void update(int ll, int rr, int hh) {
       
if
(ll <= l &&
r <= rr) {
           
height = hh;
       
} else {
           
int
mm = (l + r) >>
1;
           
if
(ll < mm) {
               
left->update(ll, rr, hh);
           
}
           
if
(rr > mm) {
               
right->update(ll, rr, hh);
           
}
           
height = max(left->height, right->height);
       
}
    }
    void query(int ll, int rr, int &ans) {
       
if
(ll <= l &&
r <= rr) {
           
ans = max(ans, height);
           
return;
       
}
       
int
mm = (l + r) >>
1;
       
if
(ll < mm) {
           
left->query(ll, rr, ans);
       
}
       
if
(rr > mm) {
           
right->query(ll, rr, ans);
       
}
    }
};

int
main() {
    int n, m;
    while (scanf(“%d %d”, &n, &m) == 2) {
       
LineTree tree(0, n);
       
tree.init();
       
for
(int
i = 0; i < n; i++) {
           
int
h;
           
scanf(“%d”, &h);
           
tree.update(i, i + 1, h);
       
}
       
for
(int
i = 0; i < m; i++) {
           
int
s, t;
           
scanf(“%d %d”, &s, &t);
           
int
ans = 0;
           
tree.query(s - 1, t, ans);
           
printf(“%dn, ans);
       
}
    }
    return 0;
}

  • HOJ 2803 Light
    Switching(区间异或操作)



传送门:http://acm.hit.edu.cn/hoj/problem/view?id=2803

题意:灯在开始的时候都是off状态,按下一次变为on状态,再按一下变为off状态。现在通过一段区间全部按下按钮的操作改变灯的状态。统计一段区间上灯为on状态的个数。

输入:operation s e,operation
= 0表示将s和e之间的开关按下一次,operation = 1表示求出s和e之间的灯为on的个数。

输出:对operation =
1输出个数。

思路:区间上的异或操作。需要注意的是每次更新的时间。


程序

#include
<cstdio>

class
LineTree {
private:
    int l, r;
    LineTree *left, *right;
public:
    bool pass;
    int cnt;
    LineTree(int ll, int rr) {
       
l = ll, r = rr;
       
if
(ll + 1 != rr) {
           
int
mm = (l + r) >>
1;
           
left = new LineTree(ll, mm);
           
right = new LineTree(mm, rr);
       
} else {
           
left = NULL;
           
right = NULL;
       
}
    }
    void init() {
       
if
(left != NULL) {
           
left->init();
       
}
       
pass = false, cnt = 0;
       
if
(right != NULL) {
           
right->init();
       
}
    }
    void pushdown() {
       
if
(pass) {
           
pass = !pass;
           
if
(l + 1 != r) {
               
left->pass = !left->pass, right->pass = !right->pass;
               
left->cnt = left->r - left->l - left->cnt;
               
right->cnt = right->r - right->l - right->cnt;
           
}
       
}
    }
    void update(int ll, int rr) {
       
pushdown();
       
if
(ll <= l &&
r <= rr) {
           
pass = !pass;
           
cnt = r - l - cnt;
       
} else {
           
int
mm = (l + r) >>
1;
           
if
(ll < mm) {
               
left->update(ll, rr);
           
}
           
if
(rr > mm) {
               
right->update(ll, rr);
           
}
           
cnt = left->cnt + right->cnt;
       
}
    }
    void query(int ll, int rr, int &ans) {
       
pushdown();
       
if
(ll <= l &&
r <= rr) {
           
ans += cnt;
       
} else {
           
int
mm = (l + r) >>
1;
           
if
(ll < mm) {
               
left->query(ll, rr, ans);
           
}
           
if
(rr > mm) {
               
right->query(ll, rr, ans);
           
}
       
}
    }
};

int
main() {
    int n, m;
    while (scanf(“%d %d”, &n, &m) == 2) {
       
LineTree tree(0, n);
       
tree.init();
       
while
(m) {
           
int
op, s, e;
           
scanf(“%d %d %d”, &op, &s, &e);
           
if
(op == 0) {
               
tree.update(s - 1, e);
           
} else if (op == 1) {
               
int
ans = 0;
               
tree.query(s - 1, e, ans);
               
printf(“%dn, ans);
           
}
       
}
    }
    return 0;
}

解题转自:http://blog.sina.com.cn/s/blog_8739c7c301015u5y.html


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。