UVa 1609 – Foul Play

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4484

题意：

n支队伍（2≤n≤1024，且n是2的整数幂）打淘汰赛，每轮都是两两配对，胜者进入下一轮。
每支队伍的实力固定，并且已知每两支队伍之间的一场比赛结果（“实力固定”是指，例如，
队伍1曾经胜过队伍2，则二者在今后的交锋中队伍1总会获胜）。你喜欢1号队。虽然
它不一定是最强的，但是它可以直接打败其他队伍中的至少一半，并且对于每支1号队不能
直接打败的队伍t，总是存在一支1号队能直接打败的队伍t’使得t’能直接打败t。
问：如何安排比赛，使得1号队夺冠？

分析：

构造法。
用黑色代表强队（即1号队不能直接打败的队伍），再用灰色代表“有用的队”，
即能打败某个黑色队但不能打败1号队的队伍（说它们有用是因为可以间接打败黑色队）。
将每一轮比赛分为四个阶段，直到第logn轮：
阶段1：尽量“消灭”黑色队，即依次考虑每一个黑色队，选一个能打败且还没安排对手的灰色队。
阶段2：给1号队任选一个能打败的。这个选择一定可以成功，因为1号队能打败的队伍至少一半（题设）。
阶段3：把剩下的黑色队伍任意配对，任它们“自相残杀”，不管谁赢都无所谓。
阶段4：剩下的队伍任意配对。

代码：

 #include <cstdio>
 #include <vector>
 using namespace std; const int UP =  + ;
 char res[UP][UP]; int main(){
     int n;
     while(~scanf("%d", &n)){
         for(int i = ; i <= n; i++) scanf("%s", res[i] + );         vector<int> win, lose;
         for(int i = ; i <= n; i++){
             if(res[][i] == '') win.push_back(i);
             else lose.push_back(i);
         }         while(n > ){
             vector<int> win2, lose2, last;             for(int i = ; i < lose.size(); i++){
                 int lid = lose[i];
                 bool found = false;
                 for(int t = ; t < win.size(); t++){
                     int& wid = win[t];
                     if(wid && res[wid][lid] == ''){
                         printf("%d %d\n", wid, lid);
                         win2.push_back(wid);
                         wid = ;
                         found = true;
                         break;
                     }
                 }
                 if(!found) last.push_back(lid);
             }             bool first = true;
             for(int i = ; i < win.size(); i++){
                 int wid = win[i];
                 if(wid){
                     if(first) printf("1 %d\n", wid), first = false;
                     else last.push_back(wid);
                 }
             }             for(int i = ; i < last.size(); i += ){
                 printf("%d %d\n", last[i], last[i+]);
                 int wid = last[i+];
                 if(res[last[i]][wid] == '') wid = last[i];
                 if(res[][wid] == '') win2.push_back(wid);
                 else lose2.push_back(wid);
             }             win = win2;
             lose = lose2;
             n >>= ;
         }
     }
     return ;
 }