考虑最后赢的情况，一定是1和某一个它能打败的队。因此，如果始终保持原始的条件，即1能打败至少一半的队伍，且不能直接打败的队伍都能被间接打败，那么直到最后决赛，2支队伍中必定有一个是1能打败的。则1获得冠军。
构造题
- 对于所有1不能打败的队伍，将他们尽可能地与1能打败的队伍配对。因为题目条件，所以最终被配对的能被1打败的队伍一定可以打败所有的不能被1打败的队伍。将选中的能被1打败的队伍留到下一轮，则可以确保不能被1打败的队伍始终可以被间接打败。
- 给1随便分配一个未被配对的能被1打败的队伍。
- 剩下的不能被1打败的队伍内部打，如果多出来1个，则混入能被1打败的队伍中。
- 剩下的能被1打败的队伍，可能还有混进来的那个队，内部打。
- 剩下来的队伍晋级下一轮。
本题的关键在于：
- 能看出始终保持原始条件则1能夺冠。
- 先将两种队伍配对，以确保不能被1打败的队伍始终被间接打败。
- 让不能被1打败的队伍内斗，以最安全的方式确保其数量少于总数一半。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2000;
const int INF = 0x3f3f3f3f;
int n;
char c;
vector<int>win[maxn], die[maxn], ali, ene, tmp;
bool vis[maxn], gg[maxn];
int a[maxn][maxn];
int main() {
while (cin >> n) {
memset(a, 0, sizeof(a));
memset(gg, 0, sizeof(gg));
for (int i = 1; i <= n; i++) {
win[i].clear();
die[i].clear();
}
ali.clear();
ene.clear();
for (int i = 1; i <= n; i++) {
getchar();
for (int j = 1; j <= n; j++) {
scanf("%c", &c);
if (c == '1') {
win[i].push_back(j);
die[j].push_back(i);
a[i][j] = 1;
}
}
}
for (int i : win[1])ali.push_back(i);
for (int i : die[1])ene.push_back(i);
for (int tt = 0; tt < log2(n); tt++) {
memset(vis, 0, sizeof(vis));
tmp.clear();
for (auto it = ene.begin(); it != ene.end(); ) {
int j = 0, p = *it;
for (; j < die[p].size();j++) {
int m = die[p][j];
if ((!vis[m]) && a[1][m] && (!gg[m])) {
printf("%d %d\n", m, p);
vis[m] = 1;
it = ene.erase(it);
break;
}
}
if (j == die[p].size())it++;
}
for (auto it = ali.begin(); it != ali.end(); it++) {
if (!vis[*it]) {
printf("%d %d\n", 1, *it);
gg[*it] = 1;
ali.erase(it);
break;
}
}
bool rest = 0;
if ((ene.size() & 1)) rest = 1;
if (ene.size() > 1) {
int len = ene.size();
for (auto it = ene.begin(); (it + 1) < ene.end();) {
printf("%d %d\n", *it, *(it + 1));
if (a[*it][*(it + 1)]) {
if (it + 2 == ene.end()) {
ene.erase(it + 1);
break;
}
else
it = ene.erase(it + 1);
}
else {
if (it + 2 == ene.end()) {
ene.erase(it);
break;
}
else
it = (ene.erase(it) + 1);
}
}
}
for (int i : ali)if (!vis[i] && !gg[i])tmp.push_back(i);
if (tmp.size() > 1) {
int len = tmp.size();
for (auto it = tmp.begin(); (it + 1) < tmp.end();) {
printf("%d %d\n", *it, *(it + 1));
if (a[*it][*(it + 1)]) {
gg[*(it + 1)] = 1;
if (it + 2 == tmp.end()) {
tmp.erase(it + 1);
break;
}
else
it = tmp.erase(it + 1);
}
else {
gg[*it] = 1;
if (it + 2 == tmp.end()) {
tmp.erase(it);
break;
}
else
it = (tmp.erase(it) + 1);
}
}
}
if (rest) {
printf("%d %d\n", *tmp.rbegin(), *ene.rbegin());
gg[*tmp.rbegin()] = 1;
tmp.erase(--tmp.end());
}
for (int i : ali) {
if (vis[i] && !gg[i])tmp.push_back(i);
}
ali = tmp;
}
}
return 0;
}
|
