• <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
            數(shù)據(jù)加載中……

            POJ 1733 Parity game 牛題 -> 并查集+hash

            思路:

            這題是道好題!
            假比確定了 [2, 4]、[5, 6]、[7, 8] 的奇偶性
            [4, 5] 的奇偶性無法得知
            [2, 6] 的奇偶性是知道的
            所以只有詢問的區(qū)間符合以下要求:
            1. 頭部和某個已知區(qū)間的頭部重合
            2. 尾部和某個已知區(qū)間的尾部重合
            3. 區(qū)間內(nèi)每一段都是已知的
            才能得出結(jié)論

            我只想到這一步,然后用鏈表寫了一遍,TLE 了。上網(wǎng)搜解題報告,看到“并查集”三字,恍然大悟。嗎的太牛逼了。

            我們把首尾相接的多個已知區(qū)間歸為一類。
            將這多個區(qū)間的尾部的點歸在同一個集合中。
            它們的父親就是最左邊區(qū)間頭部。
            它們的權(quán)值就是從左邊區(qū)間頭部的到自己的這段區(qū)間的奇偶性。

            插入?yún)^(qū)間 [i, j] 的時候,首先查找 i, j 對應(yīng)的父親。就是 find 操作。
            如果它們的父親相同,則表明它們處在同一個段的多個已知區(qū)間中。
            那么 i, j 的權(quán)值相減,就很容易得出 [i, j] 的奇偶性了。
            如果它們的父親不同,則需要將 i, j 分別對應(yīng)的區(qū)間段關(guān)聯(lián)起來。也就是 union 操作。
            這時候要注意判斷 i, j 父親的位置先后。因為這個 WA 了一次。

            由于節(jié)點的位置分得很散,用 hash 存放。

            #include <stdio.h>

            #define HASH_SIZE (1 << 18)
            #define NODES_NR 65536

            struct node {
                
            struct node *root, *next;
                
            int idx, val;
            }
            ;

            struct node *hash[HASH_SIZE], nodes[NODES_NR];
            int nodes_cnt;

            inline 
            void find(struct node *t)
            {
                
            static struct node *stk[NODES_NR];
                
            int i;

                
            for (i = 0; t->root != t; t = t->root)
                    stk[i
            ++= t;
                
            for (i--; i >= 0; i--{
                    stk[i]
            ->val += stk[i]->root->val;
                    stk[i]
            ->root = t;
                }

            }


            inline 
            struct node *insert(int idx)
            {
                
            int h;
                
            struct node *t;

                h 
            = idx & (HASH_SIZE - 1);
                
            for (t = hash[h]; t; t = t->next) {
                    
            if (t->idx == idx)
                        
            break;
                }

                
            if (!t) {
                    t 
            = &nodes[nodes_cnt++];
                    t
            ->root = t;
                    t
            ->idx = idx;
                    t
            ->next = hash[h];
                    hash[h] 
            = t;
                }

                
            return t;
            }


            inline 
            int solve(int start, int end, int val)
            {
                
            struct node *a, *b;

                a 
            = insert(start);
                b 
            = insert(end);
                find(a);
                find(b);

                
            if (a->root == b->root)
                    
            return ((b->val - a->val) & 1== val;

                val 
            -= b->val;
                val 
            += a->val;
                a 
            = a->root;
                b 
            = b->root;
                
            if (a->idx < b->idx) {
                    b
            ->root = a;
                    b
            ->val = val;
                }
             else {
                    a
            ->root = b;
                    a
            ->val = -val;
                }


                
            return 1;
            }


            int main()
            {
                
            int n, i, x, a, b;
                
            char str[16];

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

                scanf(
            "%d%d"&n, &x);
                
            for (i = 0; i < x; i++{
                    scanf(
            "%d%d%s"&a, &b, str);
                    
            if (!solve(a, b + 1, str[0== 'o'))
                        
            break;
                }

                printf(
            "%d\n", i);

                
            return 0;
            }



            posted on 2010-04-22 21:38 糯米 閱讀(884) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            91性高湖久久久久| 精品久久久久久综合日本| 亚洲国产高清精品线久久 | 国内精品久久久久久99| 国产精品无码久久综合网| 久久人人爽人人人人爽AV| 国产毛片欧美毛片久久久| 久久久亚洲欧洲日产国码二区| 久久青青草原综合伊人| 亚洲精品无码久久不卡| 99久久精品影院老鸭窝| 漂亮人妻被中出中文字幕久久 | 国产精品久久久香蕉| 久久久久亚洲精品无码蜜桃 | 久久亚洲国产成人精品性色| 成人妇女免费播放久久久| 天天影视色香欲综合久久| 国产欧美久久久精品| 亚洲国产精品无码久久久秋霞2| 国产亚洲美女精品久久久| 97久久香蕉国产线看观看| 国产成人精品综合久久久久 | 久久影院综合精品| 污污内射久久一区二区欧美日韩| 国产91色综合久久免费| 国产毛片欧美毛片久久久| 伊人色综合久久天天网| 久久精品国产WWW456C0M| 秋霞久久国产精品电影院| 精品熟女少妇av免费久久| 久久久无码精品亚洲日韩按摩 | 国产精品久久久久AV福利动漫| 久久婷婷五月综合成人D啪| 久久综合久久鬼色| 久久最新免费视频| 亚洲国产天堂久久综合| 一本大道久久香蕉成人网| 色综合久久夜色精品国产| 久久久精品国产免大香伊 | 99精品国产在热久久无毒不卡| 精品久久久一二三区|