• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設(shè)計空間

            // 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 閱讀(7761) 評論(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) // 獲得點的覆蓋次數(shù)
            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   回復(fù)  更多評論   

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

            # re: HOJ 11107   回復(fù)  更多評論   

            2008-05-25 20:31 by sicheng[I am oyjpArt]
            如果我們把這個環(huán)放成直線(準(zhǔn)確的說是一個區(qū)間)來看的話,放入某一個籃子并且按照順時針旋轉(zhuǎn)一直放num,相當(dāng)于在這個區(qū)間插入很多條線段。而進一步說,我們可以考慮只有3中線段,比如
            區(qū)間是[0,4] 從3開始插入長度為11的線段 則可以分成
            [3,4]
            [0,4] * 2
            [0,0]
            而逆時針的情況很好處理,如果你現(xiàn)算出最后停在哪個點上,換一下起始點和終點就是順時針了.

            最后是線段樹了,我們把所有的線段都分別插入.最后統(tǒng)計詢問中的點上有多少線段覆蓋就可以了.

            要進行點的線段覆蓋查詢,有很多種做法,我覺得比較好的就是從葉節(jié)點向上到根節(jié)點,去疊加覆蓋數(shù)就可以了.

            呵呵~~

            # re: HOJ 11107   回復(fù)  更多評論   

            2008-06-03 14:01 by w
            建樹可以非遞歸話吧

            # re: HOJ 11107   回復(fù)  更多評論   

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

            # re: HOJ 11107   回復(fù)  更多評論   

            2008-10-13 14:14 by re: HOJ 11107
            int get(int x) { // 獲得點的覆蓋次數(shù)
            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}

            貌似這里有個錯誤,你的代碼對這組數(shù)據(jù)通不過:
            5 3
            C 1 5
            Q 1
            Q 5

            應(yīng)改為:

            int get(int x) { // 獲得點的覆蓋次數(shù)
            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   回復(fù)  更多評論   

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

            # re: HOJ 11107   回復(fù)  更多評論   

            2009-03-23 20:41 by 成大才子
            絕對大牛

            # re: HOJ 11107   回復(fù)  更多評論   

            2009-03-26 00:27 by alpc12
            精品国际久久久久999波多野| 亚洲欧美一级久久精品| 香蕉久久夜色精品升级完成| 久久狠狠高潮亚洲精品| 97精品伊人久久久大香线蕉| 久久香综合精品久久伊人| 久久精品国产秦先生| 国产成人精品久久| 久久九色综合九色99伊人| 丁香五月网久久综合| 熟妇人妻久久中文字幕| 久久国产精品久久精品国产| 欧美伊人久久大香线蕉综合69| 国产午夜精品理论片久久影视| 国产精品永久久久久久久久久| 久久精品九九亚洲精品天堂| 久久久久久噜噜精品免费直播| 99久久99久久精品国产片果冻| 久久久久综合网久久| 久久青青草原国产精品免费| 午夜精品久久久久久| 日本福利片国产午夜久久| 亚洲愉拍99热成人精品热久久| 99久久亚洲综合精品成人| 欧美大香线蕉线伊人久久| 99久久精品毛片免费播放| 色天使久久综合网天天| 66精品综合久久久久久久| 97久久精品无码一区二区天美 | 日韩va亚洲va欧美va久久| 久久精品国产亚洲AV电影 | 久久99精品国产99久久6男男| 久久久久久久免费视频| 久久无码高潮喷水| 久久综合伊人77777麻豆| 伊人久久大香线蕉综合5g| 88久久精品无码一区二区毛片 | 四虎国产精品免费久久5151| 久久精品国产亚洲av水果派 | 成人精品一区二区久久| 99国产欧美久久久精品蜜芽|