• <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ě)的線(xiàn)段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

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

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

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

            # re: pku1769 新寫(xiě)的線(xiàn)段樹(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ě)的線(xiàn)段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

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

            # re: pku1769 新寫(xiě)的線(xiàn)段樹(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ě)的線(xiàn)段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

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

            # re: pku1769 新寫(xiě)的線(xiàn)段樹(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ě)的線(xiàn)段樹(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ě)的線(xiàn)段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

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

            # re: pku1769 新寫(xiě)的線(xiàn)段樹(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),呵呵。
            最先還一直在想如果可以排序的話(huà)就用不著用點(diǎn)樹(shù)了,直接貪心!

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

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

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

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

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

            2010-12-01 20:36 by LSK
            請(qǐng)仔細(xì)讀題。。。ZJU哪個(gè)是multi case的
            中文字幕久久欲求不满| 欧美成人免费观看久久| 99久久精品影院老鸭窝| 99久久国产主播综合精品| 一级a性色生活片久久无少妇一级婬片免费放| 久久99精品久久久久久水蜜桃| 亚洲欧洲精品成人久久奇米网| 蜜臀久久99精品久久久久久小说 | 欧美久久综合性欧美| 老司机午夜网站国内精品久久久久久久久| 伊人热热久久原色播放www| 精品无码久久久久久午夜| 精品国产青草久久久久福利| 色综合久久无码中文字幕| 久久露脸国产精品| 精品国际久久久久999波多野| 日韩AV毛片精品久久久| 久久精品免费一区二区三区| 久久综合鬼色88久久精品综合自在自线噜噜 | 婷婷五月深深久久精品| 久久久久国产精品三级网| 国产精品久久影院| 老色鬼久久亚洲AV综合| 久久综合亚洲色HEZYO社区 | 久久综合亚洲色一区二区三区| 国产精品免费久久| 色综合久久精品中文字幕首页| 无码国内精品久久人妻蜜桃| 亚洲综合久久夜AV | 国产免费久久精品99久久| 欧美一区二区精品久久| 久久99国产综合精品女同| 少妇精品久久久一区二区三区| 亚洲欧洲久久久精品| 久久午夜综合久久| 国产精品无码久久四虎| 99久久99久久精品国产| 一本一道久久精品综合| 国产高清国内精品福利99久久| 久久婷婷久久一区二区三区| 久久久久久久综合日本亚洲 |