oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

HOJ 11107

Posted on 2008-01-09 14:11 oyjpart 阅读(7721) 评论(8)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛
Number of stones
Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:32768KB
Total submit users: 13, Accepted users: 1
Problem 11107 : No special judgement
Problem description
There are N baskets rounded in a circle, and numbered as 1、2、3、…….、N-1、N, in clockwise. At the beginning, all of the baskets are empty. Some workers go to the moutain to collect stones. When they are back,they put their stones to some baskets. The workers have a habit, Once a worker come back, he choose a baskets, and choose a direction(clockwise or anticlockwise), he put one stone to this basket and move to the next basket according to the direction he has chosen, he continues doing this until all of the stones they have collected have been put down.
Sometimes the workers ask you how many stone it is in the basket, as there are too many baskets, You are to wirte a program to calculate this.


Input
The input test file will contain multiple cases. Each test case:
In the first line of the input contain two integers N,M(3 <= N <= 100000, 0 <= M <= 300000). Following M lines,each line represents an event. There are only three kinds of events: Q, C, U. And the format is:
“Q x”, query the number of stones in the basket x.
“C x num”, a worker comes back and the number of the stones he has picked up is num, he puts down stones from the basket x in clockwise.
“U x num”, a worker comes back and the number of the stone he has picked up is num, he puts down stones from the basket x in anticlockwise.
(x, num are both integers, 1 <= x <= N, 1 <= num <= 10000)


Output
For each query “Q x”, print the current number of stones in basket x.

Sample Input
5 8
            C 5 8
            Q 5
            Q 4
            U 5 3
            C 2 6
            Q 2
            Q 1
            U 2 8
            
Sample Output
2
            1
            4
            3
            
Problem Source
birdman


上次比赛没有做..补做一个..挺好的题..重写了点树模板
 1/*
 2 * 主程序要作的事情
 3 * 1.确定N :必须是2^n,可以取实际n的上界
 4 * 2.build(left, right);
 5 *
 6 */

 7
 8#include <cstdio>
 9#include <cstring>
10
11const int N = 131072;                //必须是2^n,可以取实际n的上界
12
13int upperbound;
14
15struct Node {
16    int i, j, c, m;                    //left, right
17}
 T[N*2];
18
19void bd(int d, int left, int right) {
20    T[d].i = left, T[d].j = right, T[d].c = 0;
21    if(right > left) {
22        bd(d*2+1, left, T[d].m = (left+right)>>1);
23        bd(d*2+2, T[d].m+1, right);
24    }

25}

26
27void build(int left, int right) {
28    upperbound = 1;
29    while(upperbound < right-left+1) upperbound <<= 1;
30    bd(0, left, left + upperbound-1);
31}

32
33void add(int d, int left, int right, int c) {
34    if(left <= T[d].i && right >= T[d].j) {
35        T[d].c += c;
36    }

37    else {
38        if(left <= T[d].m) add(d*2+1, left, right, c);
39        if(right > T[d].m) add(d*2+2, left, right, c);
40    }

41}

42
43int get(int x) // 获得点的覆盖次数
44    int idx = upperbound+x-1, sum = 0;
45    do {
46        sum += T[idx].c;
47        idx = (idx-1)>>1;
48    }
 while(idx != 0);
49    return sum;
50}

51
52int n, m;
53
54void Add(int x, int num) {
55    int laps = (num-(n-x))/n;
56    if(laps > 0{
57        add(00, n-1, laps);
58    }

59    num -= laps*n;
60    if(n->= num) {
61        add(0, x, x+num-11);
62    }

63    else {
64        add(0, x, n-11);
65        add(00, (x+num-1)%n, 1);
66    }

67}

68
69int main() {
70    while(scanf("%d %d"&n, &m) != EOF) {
71        build(0, n-1);
72        while(m--{
73            char cmd;
74            int x, num;
75            scanf(" %c"&cmd);
76            if(cmd == 'Q'{
77                scanf("%d"&x); 
78                --x;
79                printf("%d\n", get(x));
80            }

81            else if(cmd == 'C'{
82                scanf("%d %d"&x, &num);
83                --x;
84                Add(x, num);
85            }

86            else if(cmd == 'U'{
87                scanf("%d %d"&x, &num);
88                --x;
89                int y = (x-num+1% n;
90                if(y < 0) y += n;
91                Add(y, num);
92            }

93        }

94    }

95
96    return 0;
97}

Feedback

# re: HOJ 11107   回复  更多评论   

2008-05-24 21:25 by terence_zhao
good pro
but cant follow you

# re: HOJ 11107   回复  更多评论   

2008-05-25 20:31 by sicheng[I am oyjpArt]
如果我们把这个环放成直线(准确的说是一个区间)来看的话,放入某一个篮子并且按照顺时针旋转一直放num,相当于在这个区间插入很多条线段。而进一步说,我们可以考虑只有3中线段,比如
区间是[0,4] 从3开始插入长度为11的线段 则可以分成
[3,4]
[0,4] * 2
[0,0]
而逆时针的情况很好处理,如果你现算出最后停在哪个点上,换一下起始点和终点就是顺时针了.

最后是线段树了,我们把所有的线段都分别插入.最后统计询问中的点上有多少线段覆盖就可以了.

要进行点的线段覆盖查询,有很多种做法,我觉得比较好的就是从叶节点向上到根节点,去叠加覆盖数就可以了.

呵呵~~

# re: HOJ 11107   回复  更多评论   

2008-06-03 14:01 by w
建树可以非递归话吧

# re: HOJ 11107   回复  更多评论   

2008-10-13 10:57 by re: HOJ 11107
谢谢大牛了,我搞了半天终于弄懂了什么原理哈

# re: HOJ 11107   回复  更多评论   

2008-10-13 14:14 by re: HOJ 11107
int get(int x) { // 获得点的覆盖次数
44 int idx = upperbound+x-1, sum = 0;
45 do {
46 sum += T[idx].c;
47 idx = (idx-1)>>1;
48 } while(idx != 0);
49 return sum;
50}

貌似这里有个错误,你的代码对这组数据通不过:
5 3
C 1 5
Q 1
Q 5

应改为:

int get(int x) { // 获得点的覆盖次数
44 int idx = upperbound+x-1, sum = 0;
45 do {
46 sum += T[idx].c;
47 idx -= 1;
if(idx != -1) idx >>= 1;
48 } while(idx >= 0);
49 return sum;
50}

# re: HOJ 11107   回复  更多评论   

2008-10-16 02:30 by oyjpart
Thx!~

# re: HOJ 11107   回复  更多评论   

2009-03-23 20:41 by 成大才子
绝对大牛

# re: HOJ 11107   回复  更多评论   

2009-03-26 00:27 by alpc12

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理