青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

ACM___________________________

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

常用鏈接

留言簿(24)

隨筆分類(332)

隨筆檔案(182)

FRIENDS

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜

MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

 

題目地址:

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

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

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

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

對于每個節(jié)點X, 要求X的左兒子的dis >= 右兒子的dis, 那么容易發(fā)現(xiàn), 對于N個節(jié)點的左偏樹, 其右兒子最多只有l(wèi)ogN個節(jié)點.

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

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

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

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

最后, 更新a的dis.

這樣就容易實現(xiàn)堆的其他操作 ( 比如插入, 刪除頂?shù)?).

另外 還需要用到 并查集.    
    
    
*/
//#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;
}


 

 

 

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲一区黄色| 亚洲直播在线一区| 欧美风情在线观看| 日韩午夜在线播放| 亚洲免费观看| 国产精品区一区二区三| 欧美在线视频一区二区| 久久久精品999| 亚洲国产天堂久久综合网| 亚洲精品资源美女情侣酒店| 欧美视频在线免费看| 久久精品视频免费观看| 久久一区视频| 亚洲一区二区日本| 久久久91精品国产| 一本一道久久综合狠狠老精东影业| 一本综合久久| 一区二区三区自拍| 99国产精品久久久久久久| 国产日韩欧美综合| 亚洲国产精品激情在线观看| 欧美午夜精品久久久久久人妖| 欧美一区日本一区韩国一区| 久热精品视频在线观看一区| 亚洲一区二区三区视频| 久久久99免费视频| 亚洲综合第一页| 美女图片一区二区| 欧美一区二区三区免费观看| 欧美国产精品| 久久人人97超碰国产公开结果| 欧美日韩不卡在线| 麻豆精品传媒视频| 国产精品入口麻豆原神| 亚洲欧洲日韩女同| 激情综合激情| 亚洲欧美中文另类| aa级大片欧美| 你懂的国产精品| 久久精品一本久久99精品| 新片速递亚洲合集欧美合集| 久久超碰97人人做人人爱| 亚洲午夜电影网| 免费一级欧美在线大片| 久久久99精品免费观看不卡| 欧美吻胸吃奶大尺度电影| 亚洲大片精品永久免费| 黄色欧美日韩| 午夜欧美理论片| 午夜精品99久久免费| 欧美美女日韩| 国产日韩精品一区二区三区| 亚洲精品少妇网址| 亚洲精品久久在线| 免播放器亚洲| 欧美护士18xxxxhd| 亚洲第一天堂无码专区| 久久精品视频网| 久久米奇亚洲| 黄色工厂这里只有精品| 久久久国产精品一区二区三区| 久久精品官网| 国产亚洲精品久| 欧美中文在线观看国产| 久久久爽爽爽美女图片| 精品999日本| 久久视频在线视频| 欧美国产国产综合| 亚洲日韩成人| 欧美久久精品午夜青青大伊人| 亚洲精品一区二区三区不| 一本久久综合亚洲鲁鲁五月天 | 亚洲一二三区在线观看| 欧美另类久久久品| 亚洲天堂第二页| 欧美一区二区三区视频| 国模叶桐国产精品一区| 久久久久国产免费免费| 亚洲福利在线看| 99精品欧美| 国产精品乱码人人做人人爱| 国产精品99久久不卡二区| 欧美在线三级| 亚洲电影免费观看高清完整版在线| 久久综合九色| 亚洲精品欧美极品| 欧美在线看片a免费观看| 一区免费观看视频| 欧美日韩裸体免费视频| 亚洲一区国产一区| 欧美国产综合一区二区| 宅男精品导航| 国产一区三区三区| 欧美成人综合一区| 亚洲在线视频观看| 欧美激情视频在线播放| 亚洲男女毛片无遮挡| 影音先锋另类| 欧美午夜片欧美片在线观看| 久久精品免视看| 99re8这里有精品热视频免费| 久久久久国产免费免费| 日韩一区二区高清| 国内精品99| 国产精品久久久91| 蜜桃av一区| 午夜一区二区三视频在线观看| 欧美大片免费观看| 欧美主播一区二区三区| 亚洲精品日韩久久| 国产在线拍揄自揄视频不卡99| 欧美日韩免费高清一区色橹橹| 久久国产99| 中国女人久久久| 亚洲国产日韩欧美在线99| 久久福利电影| 亚洲一区二区在线| 亚洲免费高清视频| 精品成人a区在线观看| 国产精品一区一区| 欧美日韩在线播放三区| 欧美aa在线视频| 久久久精品2019中文字幕神马| 亚洲一区精品电影| 日韩小视频在线观看专区| 欧美国产1区2区| 久久综合中文字幕| 久久久.com| 欧美在线free| 欧美一级专区免费大片| 亚洲欧美高清| 亚洲一级在线| 亚洲一区二区毛片| 一区二区三区日韩欧美精品| 亚洲精品一区二| 亚洲日本精品国产第一区| 在线视频国产日韩| 在线日韩中文| 亚洲成人在线视频播放| 禁久久精品乱码| 在线成人av网站| 影音先锋另类| 亚洲人成在线观看一区二区| 亚洲国产三级| 亚洲免费成人| 一区二区三区日韩精品视频| 亚洲午夜av| 欧美一区二区黄| 久久精品国产清自在天天线| 久久九九精品| 欧美成人按摩| 亚洲国产日韩欧美在线99| 亚洲欧洲日本一区二区三区| 亚洲精品日韩一| 亚洲无线视频| 久久av一区二区三区| 久久一本综合频道| 欧美精品少妇一区二区三区| 欧美日韩视频在线| 国产精自产拍久久久久久| 国产亚洲日本欧美韩国| 亚洲福利av| 99riav国产精品| 午夜精品久久久久久久蜜桃app| 欧美中在线观看| 欧美成在线视频| 日韩亚洲一区二区| 亚洲欧美中日韩| 鲁大师影院一区二区三区| 欧美精品九九| 国产视频久久网| 亚洲日韩第九十九页| 亚洲女ⅴideoshd黑人| 久久性色av| 日韩一本二本av| 久久久精品五月天| 欧美日韩视频在线| 好吊一区二区三区| 亚洲专区欧美专区| 麻豆精品一区二区综合av| 日韩视频一区| 久久人人爽爽爽人久久久| 欧美日韩精品免费看| 激情视频一区二区| 亚洲伊人第一页| 欧美成在线观看| 午夜久久影院| 欧美日韩a区| 亚洲国产精品一区二区www在线 | 国产一区二区三区四区hd| 日韩一二三区视频| 久久一区视频| 亚洲欧美资源在线| 欧美三日本三级三级在线播放| 樱桃成人精品视频在线播放| 亚洲欧美综合国产精品一区| 亚洲国产日韩欧美一区二区三区| 欧美中文在线观看| 国产乱码精品一区二区三区五月婷 | 国产一区二区三区在线观看网站 |