链接：
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 ;
}