• <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

            pku3667 hotel

            Posted on 2008-07-27 19:49 oyjpart 閱讀(2934) 評論(1)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            Hotel

            Time Limit: 3000MS

             

            Memory Limit: 65536K

            Total Submissions: 478

             

            Accepted: 129

            Description

            The cows are journeying north to in to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

            The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

            Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ XiN-Di+1). Some (or all) of those rooms might be empty before the checkout.

            Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

            Input

            * Line 1: Two space-separated integers: N and M
            * Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

            Output

            * Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

            Sample Input

            10 6

            1 3

            1 3

            1 3

            1 3

            2 5 5

            1 6

            Sample Output

            1

            4

            7

            0

            5

            Source

            USACO 2008 February Gold

             

             

            這是一個線段樹的題目:

             

            1.     題意建模:

            關(guān)鍵點:找出最靠左的一個長度至少為K的線段可以用線段樹來做。

            對任意一個線段樹中的節(jié)點(x,y) 維護3個信息:

            1.     (x, y) 中最長的線段的長度

            2.     x點開始向右的線段長度

            3.     y點開始向左的線段長度

            題目要求我們對一個(0, 50000)長的區(qū)間做以下操作:

            A.   對任意區(qū)間 (x, y) 使 F(x, y) = 0

            B.   對任意區(qū)間 (x, y) 使 F(x, y) = 1

            C.   查詢?nèi)我庖粋€區(qū)間 (x, y) 中最長的線段的長度,

            D.   維護每個節(jié)點的3種信息

             

            2.難點解析:

                  1.實現(xiàn)A, B 操作:

            要把某個節(jié)點覆蓋為0,或者1,不需要向下擴展。只有在需要查詢到兒子區(qū)間的狀態(tài)的時候才需要擴展(參考spread函數(shù))

            2.實現(xiàn)D的維護:

            每次改變了左右兒子區(qū)間的信息的時候,就需要更新當前節(jié)點的信息(參考update函數(shù))

             

            3.代碼實現(xiàn):

             

            #include <stdio.h>

             

            #define Max(a, b) ((a)>(b)?(a):(b))

             

            const int N = 50010;

             

            struct ST {int i,j,m,l,r,c,lc,rc;} st[2*N]; //区间宽度的2�

            int up, n;

             

            void bd(int d, int x, int y) {

                  st[d].i = x, st[d].j = y, st[d].m = (x+y)/2;

                  st[d].c = st[d].lc = st[d].rc = y-x;

                  if(x < y-1) {

                       st[d].l = ++up; bd(up, x, st[d].m);

                       st[d].r = ++up; bd(up, st[d].m, y);

                  }

            }

             

            void spread(int d) {

                  if(st[d].c == st[d].j-st[d].i) {

                       int& l = st[d].l, &r = st[d].r;

                       st[l].c = st[l].lc = st[l].rc = st[l].j-st[l].i;

                       st[r].c = st[r].lc = st[r].rc = st[r].j-st[r].i;

                  } else if(st[d].c == 0) {

                       int& l = st[d].l, &r = st[d].r;

                       st[l].c = st[l].lc = st[l].rc = 0;

                       st[r].c = st[r].lc = st[r].rc = 0;

                  }

            }

             

            void update(int d) {

                  st[d].c = Max(Max(st[st[d].l].c, st[st[d].r].c), st[st[d].l].rc + st[st[d].r].lc);

                  if(st[st[d].l].c == st[st[d].l].j-st[st[d].l].i) {

                       st[d].lc = st[st[d].l].c + st[st[d].r].lc;

                  } else st[d].lc = st[st[d].l].lc;

                  if(st[st[d].r].rc == st[st[d].r].j-st[st[d].r].i) {

                       st[d].rc = st[st[d].r].rc + st[st[d].l].rc;

                  } else st[d].rc = st[st[d].r].rc;

            }

             

            void Empty(int d, int x, int y) {

                  if(x <= st[d].i && y >= st[d].j) {

                       st[d].c = st[d].lc = st[d].rc = 0;

                       return;

                  }

             

                  spread(d);

             

                  if(x < st[d].m) Empty(st[d].l, x, y);

                  if(y > st[d].m) Empty(st[d].r, x, y);

             

                  update(d);

            }

             

            void Fill(int d, int x, int y) {

                  if(x <= st[d].i && y >= st[d].j) {

                       st[d].c = st[d].lc = st[d].rc = st[d].j-st[d].i;

                       return;

                  }

             

                  spread(d);

             

                  if(x < st[d].m) Fill(st[d].l, x, y);

                  if(y > st[d].m) Fill(st[d].r, x, y);

             

                  update(d);

            }

             

            int Get(int d, int l) {

                 

                  spread(d);

             

                  if(st[d].c < l) return -1;

                  if(st[st[d].l].c >= l)

                       return Get(st[d].l, l);

                  else if(st[st[d].l].rc + st[st[d].r].lc >= l) {

                       return st[st[d].l].j-st[st[d].l].rc;

                  }

                  return Get(st[d].r, l);

            }

             

            int main()

            {

                  int i, nq, cmd, x, l, y;

                  up = 0;

                  scanf("%d%d", &n, &nq);

                  bd(0, 0, n);

                  while(nq--) {

                       scanf("%d", &cmd);

                       if(cmd == 1) {

                             scanf("%d", &l);

                             x = Get(0, l);

                             if(x != -1)

                                  Empty(0, x, x+l);

                             printf("%d\n", x+1);

                       } else {

                             scanf("%d%d", &x, &l);

                             Fill(0, x-1, x+l-1);

                       }

                  }

                  return 0;

            }



            Feedback

            # re: pku3667 hotel  回復  更多評論   

            2008-09-26 10:59 by AngelClover
            還是大牛的思路比較清晰~
            久久精品亚洲男人的天堂| 亚洲欧美日韩久久精品| 91精品国产综合久久久久久| 亚洲AV无码久久精品色欲| 精品乱码久久久久久久| 久久青青草原亚洲av无码 | 欧美黑人又粗又大久久久| 国产激情久久久久影院老熟女免费| 久久黄视频| 少妇久久久久久久久久| 大蕉久久伊人中文字幕| 亚洲中文字幕无码久久精品1| AA级片免费看视频久久| 欧美伊人久久大香线蕉综合| 国产精品99久久久久久宅男| 久久久久亚洲AV无码观看| 久久亚洲中文字幕精品一区四| 久久久久免费精品国产| 777久久精品一区二区三区无码| 国产精品一区二区久久不卡| 四虎久久影院| 麻豆久久久9性大片| 婷婷久久综合九色综合九七| 久久精品视频免费| 久久se精品一区精品二区| 性做久久久久久久久久久| 亚洲国产精品久久久久| 国产精品女同久久久久电影院| 亚洲中文字幕无码久久精品1| 亚洲精品99久久久久中文字幕| 国产精品激情综合久久| 国产精品久久久久影院色| 久久精品中文无码资源站| 久久香蕉超碰97国产精品| 久久久久亚洲精品日久生情| 久久精品视频一| 久久综合色老色| 午夜精品久久久久久99热| 久久久老熟女一区二区三区| 国产99久久精品一区二区| 精品久久久久久中文字幕|