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

            国产日韩久久免费影院| 国内精品久久久久久不卡影院 | 国产精品青草久久久久婷婷| 青青草原精品99久久精品66| 久久精品国产精品青草| 久久综合亚洲色HEZYO国产| 亚洲中文久久精品无码| 99久久精品国产综合一区| 人妻丰满?V无码久久不卡| 久久精品蜜芽亚洲国产AV| 欧美久久久久久午夜精品| 无码人妻久久一区二区三区免费| 91久久九九无码成人网站| 国产成人久久精品一区二区三区| 亚洲国产成人久久综合一 | 久久久精品午夜免费不卡| 色妞色综合久久夜夜| 国产成人精品久久亚洲高清不卡 | 一本久久a久久精品亚洲| 久久99精品久久久久久水蜜桃| 久久亚洲私人国产精品| 精品久久久久久久久免费影院| 久久精品九九亚洲精品天堂| 午夜人妻久久久久久久久| 中文国产成人精品久久亚洲精品AⅤ无码精品| 久久不见久久见免费视频7| 中文字幕无码免费久久| 久久久亚洲裙底偷窥综合| 久久人人爽人人爽人人片AV麻豆| 久久香蕉综合色一综合色88| 久久久久久人妻无码| 性欧美丰满熟妇XXXX性久久久| 97香蕉久久夜色精品国产| 久久国产精品无| 久久99久国产麻精品66| 久久精品国产亚洲αv忘忧草 | 欧美久久久久久午夜精品| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 一本综合久久国产二区| 尹人香蕉久久99天天拍| 久久人人爽人人爽人人av东京热|