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 ;

 }

巴特西

UVa 1609 - Foul Play

最新文章

热门文章