姑且把它归类为一道博弈吧，毕竟这也是在找必胜方案。
十分有意思的一道题目，设计一种方案让你支持的1队获胜。
题目给出了两个很重要的条件：
- 1队能打败至少一半的队伍
- 对于1队不能打败的黑队，一定存在一个1队能打败的灰队，使得这支灰队能够打败黑队。也就是说1队可以通过灰队间接打败黑队
一共有2支队伍，每轮比赛会刷掉一半的队伍，紫书上巧妙的做法就是每轮比赛后让题目给的两个性质依然成立，这样1队最终一定能胜出。
方案如下，大致分为3个阶段：
- 物尽其用。依次考虑每个黑队，如果有能够打败他的灰队的话，便让这两只队伍进行比赛。当然，灰队会晋级下一轮。如果没有能够打败当前黑队而且还没有进行比赛的灰队，那么这支黑队进入后面的混战。
- 让1队胜出。在1队能够打败的队伍中找到一支还未进行比赛的队伍。对于其他未匹配的队伍，也进入下一步的混战。
- 自由混战。黑队和黑队混战，这样能保证至少消灭一半的黑队，顶多有一个黑队剩下。然后剩下的队伍继续混战。
至于为什么这样一定会成功，还请参考紫书。
#include <cstdio>
#include <vector>
using namespace std; const int maxn = ; char table[maxn][maxn]; int main()
{
//freopen("in.txt", "r", stdin); int n;
while(scanf("%d", &n) == && n)
{
for(int i = ; i <= n; i++) scanf("%s", table[i] + );
vector<int> win, lose;
for(int i = ; i <= n; i++)
{
if(table[][i] == '') win.push_back(i);
else lose.push_back(i);
} int T = n;
while(T >>= )
{
vector<int> win2, lose2, final;//进入下一轮1能打败和被打败，以及这一轮混战的队伍
bool match;
//阶段1:尽可能多的用灰队消灭黑队
for(int i = ; i < lose.size(); i++)
{
int black = lose[i];
match = false;
for(int j = ; j < win.size(); j++)
{
int& gray = win[j];
if(gray > && table[gray][black] == '')
{
printf("%d %d\n", black, gray);
match = true;
win2.push_back(gray);//灰队进入下一轮
gray = ;
break;
}
}
if(!match) final.push_back(black);//进入后面的混战
}
//阶段2:给1队找个对手
match = false;
for(int i = ; i < win.size(); i++)
{
int team = win[i];
if(team > )
{
if(!match) { printf("1 %d\n", team); match = true; }
else final.push_back(team);//1已经匹配到对手，该队进入混战
}
}
//阶段3:自由混战，注意到黑队在final中都是挨在一起的
for(int i = ; i < final.size(); i += )
{
printf("%d %d\n", final[i], final[i + ]);
int survive = final[i];
if(table[final[i + ]][final[i]] == '') survive = final[i + ];
if(table[][survive] == '') win2.push_back(survive);
else lose2.push_back(survive);
}
win = win2;
lose = lose2;
/*for(int i = 0; i < win.size(); i++) printf("%d ", win[i]);
puts("");
for(int i = 0; i < lose.size(); i++) printf("%d ", lose[i]);*/
}
} return ;
}
代码君