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

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;
}


 

 

 

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久婷婷国产麻豆91天堂| 久久综合久久综合这里只有精品| 欧美激情bt| 欧美69视频| 这里只有精品丝袜| 亚洲一区二区三区四区视频| 国产视频久久网| 女同一区二区| 欧美视频不卡| 久久精品99国产精品| 久久人91精品久久久久久不卡 | 久久偷看各类wc女厕嘘嘘偷窃| 韩国美女久久| 亚洲高清一区二区三区| 欧美日韩一区二区在线| 久久九九久精品国产免费直播 | 日韩亚洲视频| 国产亚洲二区| 亚洲人精品午夜在线观看| 国产精品国产亚洲精品看不卡15| 久久国产福利| 欧美日韩国产一区二区三区| 久久久久久黄| 欧美午夜一区二区福利视频| 免费观看成人| 国产精品久久久久久久久| 牛夜精品久久久久久久99黑人 | 国产精品日本一区二区| 免费视频一区二区三区在线观看| 欧美视频在线观看一区二区| 久久视频在线免费观看| 欧美日韩在线一二三| 久色成人在线| 国产乱子伦一区二区三区国色天香| 欧美国产91| 国产日产亚洲精品系列| 99精品99久久久久久宅男| 影音先锋在线一区| 亚洲女同精品视频| 宅男噜噜噜66一区二区| 欧美1区2区3区| 媚黑女一区二区| 国产主播一区| 亚洲欧美电影院| 亚洲在线观看免费视频| 欧美日韩a区| 亚洲国产婷婷香蕉久久久久久99| 国产一区二区精品丝袜| 亚洲一区二区在线播放| 亚洲男人的天堂在线| 欧美日韩中文字幕日韩欧美| 91久久夜色精品国产九色| 一区久久精品| 久久久久se| 久久久精品一区二区三区| 国产精品综合久久久| 亚洲深夜福利视频| 亚洲欧美国产三级| 国产精品久久久久久久久搜平片| 99re亚洲国产精品| 亚洲视频你懂的| 欧美亚男人的天堂| 亚洲一区日韩| 久久av资源网| 狠狠综合久久av一区二区老牛| 午夜精品在线| 久久手机精品视频| 亚洲大胆人体在线| 欧美成人精品在线播放| 亚洲国产专区| 亚洲视频一起| 一区二区三区日韩欧美精品| 欧美夜福利tv在线| 亚洲品质自拍| 亚洲精品激情| 亚洲黄页一区| 亚洲深夜福利网站| 亚洲精品美女91| 亚洲欧洲一区二区天堂久久| 亚洲第一二三四五区| 1024亚洲| 亚洲一区欧美| 欧美91大片| av成人激情| 久久国产精品一区二区三区| 久久久噜噜噜久久中文字幕色伊伊| 久久久精品一区| 国产精品视频久久| 亚洲丰满少妇videoshd| 一本一本久久| 久久综合久久综合久久| 亚洲国产欧美在线人成| 亚洲一区二区在线看| 久久久久久香蕉网| 国产精品高潮呻吟久久| 亚洲第一在线综合在线| 久久精品国产69国产精品亚洲| 亚洲国产精品999| 久久久免费精品| 国产免费成人av| 亚洲一区区二区| 亚洲啪啪91| 欧美绝品在线观看成人午夜影视| 国产一区二区中文字幕免费看| 亚洲美女少妇无套啪啪呻吟| 欧美成人精品三级在线观看| 欧美一级片一区| 国产一区二区电影在线观看| 欧美亚洲视频一区二区| 亚洲欧美国产三级| 国产精品一区二区三区久久| 午夜精品剧场| 欧美专区在线观看| 国内久久精品| 亚洲国产精品一区二区久| 久久视频一区二区| 亚洲精品一二| 一区二区av在线| 国产欧美精品va在线观看| 欧美资源在线观看| 可以看av的网站久久看| 一区二区三区日韩欧美精品| 99精品国产高清一区二区| 国产精品久久午夜夜伦鲁鲁| 久久久精品一区二区三区| 久久综合亚州| 亚洲欧美国产精品桃花| 久久欧美肥婆一二区| 一本色道久久| 久久婷婷亚洲| 一本色道久久综合狠狠躁篇的优点| 美女主播精品视频一二三四| 欧美成人在线免费观看| 欧美在线观看www| 欧美国产乱视频| 另类天堂av| 国产一区清纯| 欧美亚洲网站| 欧美一区二区三区在线视频| 欧美日韩一卡二卡| 亚洲国产另类精品专区 | 影音先锋另类| 欧美一激情一区二区三区| 欧美一级淫片播放口| 国产精品播放| 亚洲专区欧美专区| 欧美在线免费观看亚洲| 国产欧美亚洲日本| 欧美一区亚洲一区| 免费看的黄色欧美网站| 在线观看av不卡| 欧美大片一区| 一本久道综合久久精品| 亚洲新中文字幕| 国产日韩欧美高清| 久久综合伊人| 日韩网站免费观看| 午夜精品视频在线观看一区二区| 国产精品日韩欧美综合| 久久精品五月| 亚洲狼人精品一区二区三区| 亚洲图片自拍偷拍| 国产午夜精品视频免费不卡69堂| 久久成年人视频| 中文精品视频一区二区在线观看| 午夜精品理论片| 日韩亚洲综合在线| 国产视频在线观看一区| 欧美极品在线视频| 欧美一区二区三区在线视频 | 久久久一区二区| 99热精品在线| 在线免费一区三区| 国产精品丝袜91| 欧美色大人视频| 欧美国产一区二区在线观看| 午夜久久影院| 亚洲综合精品一区二区| 亚洲精品免费在线观看| 欧美大片免费看| 久久夜色精品国产| 久久久久久久综合色一本| 香蕉久久国产| 久久激情中文| 久久精品成人| 欧美**人妖| 欧美成人福利视频| 欧美国产日韩视频| 亚洲国产精品精华液网站| 欧美国产精品专区| 免费不卡亚洲欧美| 久久精品亚洲国产奇米99| 午夜精品一区二区三区在线视| 一区二区高清| 午夜伦理片一区| 欧美ed2k| 宅男噜噜噜66一区二区| 性8sex亚洲区入口| 老牛嫩草一区二区三区日本 | 亚洲天堂激情|