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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 2843 Cutting Cake 并查集

            思路:

            這題目非常牛逼!是道月賽的題目!看完題目我就放棄了。。直接看解題報告。
            解法果然牛逼!

            解題報告鏈接在此:
            http://acm.pku.edu.cn/JudgeOnline/images/contestreport/200606/G.htm

            代碼是照著解題報告寫的,不過還是很爛,好像3000+ms,實在佩服那些1000ms內的神牛們!

            #include <stdio.h>

            #define MAX_N 1024

            struct queue_node {
                
            int y, x;
            }
            ;

            int set[MAX_N][MAX_N], cut[MAX_N][MAX_N];
            int N, M;
            int left, top, right, bottom;

            struct queue_node queue[MAX_N * MAX_N];
            int head, tail;

            inline 
            int find(int *arr, int idx)
            {
                
            static int stk[MAX_N * MAX_N], sp;

                
            for (sp = 0; arr[idx]; idx = arr[idx])
                    stk[sp
            ++= idx;
                
            for (sp--; sp >= 0; sp--)
                    arr[stk[sp]] 
            = idx;

                
            return idx;
            }


            inline 
            void push(int y, int x)
            {
                
            if (x < left || x > right || y < top || y > bottom)
                    
            return ;
                
            if (cut[y][x])
                    
            return ;
                
                cut[y][x] 
            = 1;
                
            if (cut[y][x - 1&& cut[y][x + 1]) {
                    
            set[y][x] = x + 1;
                    
            set[y][x - 1= x + 1;
                }
             else if (cut[y][x - 1]) 
                    
            set[y][x - 1= x;
                
            else if (cut[y][x + 1])
                    
            set[y][x] = x + 1;
                
                queue[tail].y 
            = y;
                queue[tail].x 
            = x;
                tail
            ++;
            }


            inline 
            int bfs(int y, int x)
            {
                x 
            = find(set[y], x);
                
            if (cut[y][x])
                    x
            ++;
                
            if (x > right)
                    
            return 0;

                head 
            = tail = 0;
                push(y, x);
                
            while (head != tail) {
                    y 
            = queue[head].y;
                    x 
            = queue[head].x;
                    head
            ++;
                    push(y 
            - 1, x);
                    push(y 
            + 1, x);
                    push(y, x 
            - 1);
                    push(y, x 
            + 1);
                }


                
            return 1;
            }


            int main()
            {
                
            int i, j, ans;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d%d"&N, &M);
                
            while (M--{
                    scanf(
            "%d%d%d%d"&left, &top, &right, &bottom);
                    ans 
            = 0;
                    
            for (i = top; i <= bottom; i++)
                        
            while (bfs(i, left))
                            ans
            ++;
                    printf(
            "%d\n", ans);
                }


                
            return 0;
            }

            posted on 2010-04-06 22:40 糯米 閱讀(319) 評論(1)  編輯 收藏 引用 所屬分類: POJ

            評論

            # re: POJ 2843 Cutting Cake 并查集  回復  更多評論   

            請問你上面e:\test\in.txt里面是什么內容,我也在想這個問題,但是沒弄明白,想用你代碼運行一下,謝謝了 我郵箱:236602203@qq.com
            2010-04-10 00:46 | 卡卡
            久久影视国产亚洲| 国产三级观看久久| 久久99久久99精品免视看动漫| 成人综合久久精品色婷婷| 久久精品aⅴ无码中文字字幕重口| 欧美久久综合性欧美| 18禁黄久久久AAA片| 久久久九九有精品国产| 18禁黄久久久AAA片| 999久久久免费国产精品播放| 99久久综合狠狠综合久久止| 久久久久久久免费视频| 国产成人无码精品久久久久免费 | 韩国三级中文字幕hd久久精品| 国产精品乱码久久久久久软件| 国产精品久久久天天影视| 色综合久久中文字幕无码| 久久久久久久久66精品片| 66精品综合久久久久久久| 国内精品久久久久久久久电影网| 亚洲婷婷国产精品电影人久久| 久久久精品波多野结衣| 免费观看成人久久网免费观看| 免费精品久久天干天干| 久久精品国产精品亜洲毛片| 久久精品国产99国产精品澳门| 狠色狠色狠狠色综合久久| 四虎国产精品成人免费久久| 欧美精品丝袜久久久中文字幕| 国产精品成人精品久久久| 久久夜色精品国产亚洲| 色综合久久精品中文字幕首页| 国产精品青草久久久久婷婷| 精品久久8x国产免费观看| 99久久99久久精品国产| 色综合久久综精品| 国产福利电影一区二区三区,免费久久久久久久精 | 久久久国产视频| 中文无码久久精品| 久久九九精品99国产精品| 伊人色综合久久|