• <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://www.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久久| 亚洲精品国产综合久久一线| 久久精品国产久精国产思思| 青青青青久久精品国产h久久精品五福影院1421 | 亚洲人成网站999久久久综合| 久久人妻无码中文字幕| 国产精自产拍久久久久久蜜| 亚洲中文字幕无码一久久区| 久久人人爽人人爽人人片AV东京热| 中文字幕久久波多野结衣av| 久久午夜综合久久| 99久久精品久久久久久清纯| 久久夜色精品国产噜噜亚洲AV| 久久免费视频一区| 国产亚州精品女人久久久久久| 久久精品无码专区免费东京热| 四虎国产精品成人免费久久| 欧美精品丝袜久久久中文字幕| 久久精品国产69国产精品亚洲| 色综合久久中文字幕无码| 亚洲午夜无码久久久久小说| 国产精品免费久久久久电影网| 国产精品美女久久久久网| 久久99精品久久只有精品| 久久久久av无码免费网| 久久精品成人欧美大片| 要久久爱在线免费观看| 久久久久亚洲AV无码专区网站 | 久久亚洲精品国产精品| 久久无码AV中文出轨人妻| 欧美伊人久久大香线蕉综合69 | 亚洲精品无码久久久| 性做久久久久久久久久久| 亚洲国产成人精品91久久久| 中文字幕精品无码久久久久久3D日动漫| 国产成人99久久亚洲综合精品 | 99久久精品无码一区二区毛片|