• <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 | 卡卡
            亚洲AV无码久久精品色欲| 91超碰碰碰碰久久久久久综合| 久久久精品无码专区不卡| 精品乱码久久久久久久| 91精品国产91久久久久久青草| 久久黄视频| 欧美精品久久久久久久自慰| 久久夜色精品国产亚洲| 亚洲美日韩Av中文字幕无码久久久妻妇 | 7777久久亚洲中文字幕| 成人精品一区二区久久久| 麻豆精品久久久久久久99蜜桃| av午夜福利一片免费看久久| 一本色道久久综合狠狠躁篇 | 久久精品国产69国产精品亚洲 | 一本色道久久综合狠狠躁| 久久国产精品久久国产精品| 精品伊人久久久| 久久精品亚洲欧美日韩久久| 99久久久国产精品免费无卡顿| 精品久久久久久久久免费影院| 99久久国产热无码精品免费久久久久| 久久WWW免费人成一看片| 欧美午夜精品久久久久久浪潮| aaa级精品久久久国产片| 久久婷婷五月综合97色| 亚洲国产成人久久综合区| 91久久精品国产91性色也| 国产欧美一区二区久久| 国产成年无码久久久免费| 亚洲日韩欧美一区久久久久我| 香蕉久久一区二区不卡无毒影院 | 久久国产免费观看精品| 亚洲AV无码一区东京热久久| 国产精品久久久久久久人人看| 中文字幕亚洲综合久久菠萝蜜| 久久综合视频网站| 老司机午夜网站国内精品久久久久久久久 | 久久91精品国产91久| 久久久久久久波多野结衣高潮| 午夜精品久久久内射近拍高清|