|
|
Posted on 2008-01-09 14:11 oyjpart 阅读(7727) 评论(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(0, 0, n-1, laps);
58 }
59 num -= laps*n;
60 if(n-x >= num) {
61 add(0, x, x+num-1, 1);
62 }
63 else {
64 add(0, x, n-1, 1);
65 add(0, 0, (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
good pro
but cant follow you
# re: HOJ 11107 回复 更多评论
2008-05-25 20:31 by
如果我们把这个环放成直线（准确的说是一个区间）来看的话，放入某一个篮子并且按照顺时针旋转一直放num，相当于在这个区间插入很多条线段。而进一步说，我们可以考虑只有3中线段，比如
区间是[0,4] 从3开始插入长度为11的线段 则可以分成
[3,4]
[0,4] * 2
[0,0]
而逆时针的情况很好处理,如果你现算出最后停在哪个点上,换一下起始点和终点就是顺时针了.
最后是线段树了,我们把所有的线段都分别插入.最后统计询问中的点上有多少线段覆盖就可以了.
要进行点的线段覆盖查询,有很多种做法,我觉得比较好的就是从叶节点向上到根节点,去叠加覆盖数就可以了.
呵呵~~
# re: HOJ 11107 回复 更多评论
2008-06-03 14:01 by
建树可以非递归话吧
# re: HOJ 11107 回复 更多评论
2008-10-13 10:57 by
谢谢大牛了，我搞了半天终于弄懂了什么原理哈
# re: HOJ 11107 回复 更多评论
2008-10-13 14:14 by
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
Thx!~
# re: HOJ 11107 回复 更多评论
2009-03-23 20:41 by
绝对大牛
# re: HOJ 11107 回复 更多评论
2009-03-26 00:27 by
额
|