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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

            題目地址:

            http://acm.hdu.edu.cn/showproblem.php?pid=1512

            題目描述 :

            代碼
            Monkey King

            Time Limit: 
            10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
            Total Submission(s): 
            914    Accepted Submission(s): 426


            Problem Description
            Once 
            in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.

            Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that 
            is10 will be reduced to 5 and 5 will be reduced to 2).

            And we also assume that every monkey knows himself. That 
            is, when he is the strongest one in all of his friends, he himself will go to duel.
             

            Input
            There are several test cases, and each 
            case consists of two parts.

            First part: The first line contains an integer N(N
            <=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768).

            Second part: The first line contains an integer M(M
            <=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.

             

            Output
            For each of the conflict, output 
            -1 if the two monkeys know each other, otherwise output the strongness value of the strongest monkey in all friends of them after the duel.
             

            Sample Input
            5
            20
            16
            10
            10
            4
            5
            2 3
            3 4
            3 5
            4 5
            1 5
             

            Sample Output
            8
            5
            5
            -1
            10
             

             

             

            題目分析:

            /*
            Mail to   : miyubai@gamil.com
            My Blog   : www.baiyun.me
            Link      : http://www.cnblogs.com/MiYu  || http://m.shnenglu.com/MiYu
            Author By : MiYu
            Test      : 1
            Complier  : g++ mingw32-3.4.2
            Program   : HDU_1512
            Doc Name  : Monkey King
                
                
            題目意思: 

            有N只猴子, 每只都有一個力量值. 開始的時候互不認識, 它們之間會發生M次斗爭. 每次發生a, b的斗爭時, a, b都會從各自的朋友圈里拉出一個最強的, 之后兩只猴子打, 打完后這兩只猴子的力量值各減半. 并且打完后, 兩只猴子的朋友圈的所有人都互相認識(也就是不會再打).

            你的任務就是對于每個斗爭, 若a, b是朋友, 那么輸出-1, 否則輸出打完后它們的朋友圈的最強猴子的力量值.

             使用 普通 優先隊列的話 估計會超時, 因為數據量很大 100000 ! !, 等下有空試試看. 

            對于每一個節點, 定義dis 表示X節點到最右邊的空節點的距離的最小值

            對于每個節點X, 要求X的左兒子的dis >= 右兒子的dis, 那么容易發現, 對于N個節點的左偏樹, 其右兒子最多只有logN個節點.

            合并操作就是讓復雜度落在右兒子上, 從而達到logN的合并復雜度.

            首先對于兩個堆, 若其中一個為空, 返回另一個.

            否則(這里以大根堆為例), a指向堆頂較大的堆, b指向另一個. 讓a的右兒子和b合并, 合并后的子樹作為a的右兒子.

            接下來, 檢查a的兩個兒子是否滿足dis, 不滿足就交換兩個兒子.

            最后, 更新a的dis.

            這樣就容易實現堆的其他操作 ( 比如插入, 刪除頂等 ).

            另外 還需要用到 并查集.    
                
                
            */
            //#pragma warning( disable:4789 )
            #include <iostream>
            #include <fstream>
            #include <sstream>
            #include <algorithm>
            #include <string>
            #include <set>
            #include <map>
            #include <utility>
            #include <queue>
            #include <stack>
            #include <list>
            #include <vector>
            #include <cstdio>
            #include <cstdlib>
            #include <cstring>
            #include <cmath>
            #include <ctime>
            using namespace std;
            const int MM = 100010;
            struct left {
                    int l,r,dis,val,dad;
            } heap[MM];

            int N, M;

            inline int max ( const int &a, const int &b) {
                   return a > b ? a : b;
            }

            inline int find ( int &x ) {
                return heap[x].dad == x ? x : heap[x].dad = find ( heap[x].dad );
            }

            inline void swap(int &a, int &b) {
                 a ^= b ^= a ^= b;
            }

            inline int merge ( int x, int y ) {
                if ( x == 0 ) return y;
                if ( y == 0 ) return x;
                if ( heap[y].val > heap[x].val ) swap ( x, y );    
                heap[x].r = merge ( heap[x].r, y );
                heap[heap[x].r].dad = x;
                if ( heap[ heap[x].l ].dis < heap[ heap[x].r ].dis ) 
                     swap ( heap[x].l, heap[x].r );
                if ( heap[x].r == 0 ) heap[x].dis = 0;
                else heap[x].dis = heap[ heap[x].r ].dis + 1;
                return x;
            }

            inline int push ( int x, int y ) {
                   return merge ( x, y );       
            }

            inline int pop ( int &x ) {
                   int l = heap[x].l; 
                   int r = heap[x].r; 
                   heap[l].dad = l;
                   heap[r].dad = r;
                   heap[x].l = heap[x].r = heap[x].dis = 0;   
                   return merge ( l, r );  
            }

            inline bool scan_d(int &num) {
                    char in;bool IsN=false;
                    in=getchar();
                    if(in==EOF) return false;
                    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
                    if(in=='-'){ IsN=true;num=0;}
                    else num=in-'0';
                    while(in=getchar(),in>='0'&&in<='9'){
                            num*=10,num+=in-'0';
                    }
                    if(IsN) num=-num;
                    return true;
            }

            int main() {
                while ( scan_d ( N ) ) {
                     for ( int i = 1; i <= N; ++ i ) {
                          scan_d ( heap[i].val );
                          heap[i].l = heap[i].r = heap[i].dis = 0;
                          heap[i].dad = i;    
                     }
                     scan_d ( M );
                     int a, b, x, y;
                     while ( M -- ) {
                            scan_d (a); scan_d (b);
                            x = find ( a );
                            y = find ( b ); 
                            if ( x == y ) {
                                puts ( "-1" );     
                            } else {
                                heap[x].val /= 2;
                                int xx = push ( pop ( x ), x );  
                                heap[y].val /= 2;
                                int yy = push ( pop ( y ), y );  
                                
                                printf ( "%d\n", heap[ merge ( xx, yy ) ].val );      
                            }    
                     } 
                }
                return 0;
            }


             

             

             

            久久青草国产手机看片福利盒子| 青青热久久综合网伊人| 亚洲美日韩Av中文字幕无码久久久妻妇| 99久久精品无码一区二区毛片| 免费一级做a爰片久久毛片潮| 一本色道久久88—综合亚洲精品| 久久er国产精品免费观看2| 久久精品国产第一区二区| 中文字幕久久波多野结衣av| 亚洲国产精品婷婷久久| 久久无码高潮喷水| 久久99精品久久久久久不卡| 久久婷婷五月综合色奶水99啪| 国产福利电影一区二区三区,免费久久久久久久精 | 久久亚洲中文字幕精品一区四| 人妻久久久一区二区三区| 久久久久久无码国产精品中文字幕 | 久久AⅤ人妻少妇嫩草影院| 久久婷婷国产剧情内射白浆| 久久亚洲综合色一区二区三区| 无码久久精品国产亚洲Av影片| 人妻少妇精品久久| 精品无码久久久久久国产| 91超碰碰碰碰久久久久久综合| 久久国产乱子伦免费精品| 亚洲国产视频久久| 欧美日韩中文字幕久久久不卡 | 久久久久久一区国产精品| 久久精品国产一区| 久久久久一区二区三区| 人妻无码αv中文字幕久久| 精品伊人久久大线蕉色首页| 中文国产成人精品久久亚洲精品AⅤ无码精品| 国产精品美女久久久| 国产情侣久久久久aⅴ免费| 精品国产VA久久久久久久冰 | 激情五月综合综合久久69| 狠狠精品久久久无码中文字幕| 国产综合免费精品久久久| 久久久久女教师免费一区| 久久青青草原精品国产软件|