• <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è)計(jì)空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6
            Minimizing maximizer
            Time Limit: 5000MS Memory Limit: 30000K
            Total Submissions: 1004 Accepted: 280

            Description
            The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs.

            Maximizer is implemented as a pipeline of sorters Sorter(i1, j1), ... , Sorter(ik, jk). Each sorter has n inputs and n outputs. Sorter(i, j) sorts values on inputs i, i+1,... , j in non-decreasing order and lets the other inputs pass through unchanged. The n-th output of the last sorter is the output of the Maximizer.

            An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values?

            Task
            Write a program that:

            reads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline,
            computes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data,
            writes the result.

            Input
            The first line of the input contains two integers n and m (2 <= n <= 50000, 1 <= m <= 500000) separated by a single space. Integer n is the number of inputs and integer m is the number of sorters in the pipeline. The initial sequence of sorters is described in the next m lines. The k-th of these lines contains the parameters of the k-th sorter: two integers ik and jk (1 <= ik < jk <= n) separated by a single space.

            Output
            The output consists of only one line containing an integer equal to the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data.

            Sample Input

            40 6
            20 30
            1 10
            10 20
            20 30
            15 25
            30 40
            

             

            Sample Output

            4
            

             

            Hint
            Huge input data, scanf is recommended.

            Source
            Central Europe 2003

            //pku1769
            /*
             * trival DP dp[i] = dp[j] + 1 (if there is a segment starting from a->i && a <= j)  o(n^2)
             * 考慮到轉(zhuǎn)移的時(shí)候選擇的是一段內(nèi)的最小dp值,運(yùn)用點(diǎn)樹(shù)可以解決
             */
            #include <string.h>
            #include <stdio.h>

            const int N = 50010;
            const int MAXINT = 1000000000;

            int n, l;

            struct ST {int i,j,m,l,r,c;} st[2*N];
            int up, cnt;

            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 = MAXINT;
             if(x < y) {
              st[d].l = ++up; bd(up, x, st[d].m);
              st[d].r = ++up; bd(up, st[d].m+1, y);
             }
            }

            void ins(int d, int x, int c) {
             if(c < st[d].c)
              st[d].c = c;
             if(st[d].i != st[d].j) {
              if(x <= st[d].m)
               ins(st[d].l, x, c);
              else
               ins(st[d].r, x, c);
             }
            }

            int getmin(int d, int x, int y) {
             if(x <= st[d].i && y >= st[d].j)
              return st[d].c;
             int min = MAXINT;
             if(x <= st[d].m) {
              int now = getmin(st[d].l, x, y);
              if(now < min) min = now;
             }
             if(y > st[d].m) {
              int now = getmin(st[d].r, x, y);
              if(now < min) min = now;
             }
             return min;
            }

            int main() {
             int i, a, b;
             up = 0;
             scanf("%d %d ", &l, &n);
             bd(0, 1, l);
             ins(0, 1, 0);
             int max = 0;
             for(i = 0; i < n; ++i) {
              scanf("%d%d", &a, &b);
              if(a < b) {
               int min = getmin(0, a, b-1);
               ins(0, b, min+1);
              }
             }
             printf("%d\n", getmin(0, l, l));
             return 0;
            }

            Feedback

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2007-12-04 16:33 by je
            題目沒(méi)看懂,能解釋下么?

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2007-12-05 11:47 by oyjpart
            給定一個(gè)線段集,要求選擇其中一個(gè)最小的子集來(lái)覆蓋整個(gè)區(qū)域。
            要求選定的子集是按照題目給的序來(lái)覆蓋。

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-01-18 08:46 by Littleye
            很多測(cè)試好像得不到正確答案,例如:
            40 4
            10 30
            14 29
            25 30
            30 40
            答案應(yīng)該是2,你的程序給的是1000000000(你的初始值)
            類(lèi)似的例子還有不少

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-01-18 12:40 by oyjpart
            你的樣例是無(wú)解的,沒(méi)有線段覆蓋【0,10】的區(qū)間。

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-01-19 02:33 by Littleye
            I understand now. I don't think I understood the problem thoroughly before. Although the problem description doesn't clearly indicate that all the segments given should cover the whole segment(1,N), it is the right situation or else we can't get the right output from the maximizer. Now the problem description says that we can get the right output, so the subsequences given must cover the whole segments. Thanks a lot!

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-01-19 12:34 by oyjpart
            you are welcome

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-04-18 10:44 by l-y-p
            向大牛學(xué)習(xí)學(xué)習(xí),“運(yùn)用點(diǎn)樹(shù)可以解決”,好思想,很好很強(qiáng)大。但是還有一個(gè)疑點(diǎn):在DP的時(shí)候應(yīng)該從小到大進(jìn)行,但是沒(méi)發(fā)現(xiàn)你對(duì)y坐標(biāo)進(jìn)行排序就直接進(jìn)行,那如果是考慮這樣兩組數(shù)據(jù):
            10 40
            0 10
            從10到40先確定到40的DP值為maxint+1,然后再由0~10確定10的值為1,這樣是不是有問(wèn)題??你的程序我沒(méi)調(diào)試過(guò),不曉得你是怎么處理的?

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-04-18 10:58 by l-y-p
            果然啊,剛調(diào)試了下,直接運(yùn)行數(shù)據(jù):
            40 2
            10 40
            0 10
            結(jié)果是1000000000,不知道是我沒(méi)看清楚還是程序的bug?

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-04-18 12:19 by oyjpart
            題目是有這樣的要求的:
            要求選定的子集是按照題目給的序來(lái)覆蓋。
            嘿嘿 如果我沒(méi)有理解錯(cuò)你的意思的話

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2008-04-18 22:02 by l-y-p
            汗!
            What is the length of the shortest subsequence of the given sequence of sorters
            把排序一去掉就AC了,多謝大牛指點(diǎn),呵呵。
            最先還一直在想如果可以排序的話就用不著用點(diǎn)樹(shù)了,直接貪心!

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2009-08-25 10:39 by demo
            你的程序過(guò)不了zoj 2451

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2009-09-07 23:58 by oyjpart
            題目是一樣的嗎

            # re: pku1769 新寫(xiě)的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

            2010-12-01 20:36 by LSK
            請(qǐng)仔細(xì)讀題。。。ZJU哪個(gè)是multi case的
            国产产无码乱码精品久久鸭| 精品久久久久久久中文字幕| 亚洲国产另类久久久精品 | 精品综合久久久久久88小说 | 人人狠狠综合久久亚洲88| 91久久精品电影| 99久久国产精品免费一区二区 | 国产精品久久久香蕉| 久久久久久国产精品免费无码| 大蕉久久伊人中文字幕| 精品久久人人爽天天玩人人妻| 88久久精品无码一区二区毛片| 午夜精品久久久内射近拍高清| yellow中文字幕久久网| 色狠狠久久AV五月综合| 少妇人妻88久久中文字幕| 久久99久久99精品免视看动漫| 久久免费视频1| 7777精品久久久大香线蕉| 日本福利片国产午夜久久| 久久99国产综合精品免费| 亚洲欧洲日产国码无码久久99| 久久精品一区二区影院| 日韩亚洲欧美久久久www综合网| 国内精品久久久久久久97牛牛| 亚洲级αV无码毛片久久精品| 99久久夜色精品国产网站| 欧美激情精品久久久久久久 | 亚洲国产精品久久久久| 国产成人久久精品二区三区| 亚洲精品高清国产一久久| 色99久久久久高潮综合影院| 久久天天躁夜夜躁狠狠| 国产午夜免费高清久久影院| 伊人色综合久久天天| 久久狠狠爱亚洲综合影院| 亚洲日本va中文字幕久久| 久久久精品国产免大香伊| 少妇久久久久久久久久| 久久人人爽人人爽人人片AV麻烦 | 99久久精品国产高清一区二区|