UVA1609-Foul Play（构造+递归）

Problem UVA1609-Foul Play

Accept: 101 Submit: 514
Time Limit: 3000 mSec

Problem Description

Input

For each test case, the input is as follows:

• One line containing the number of teams n, where n is a power of two and 2 ≤ n ≤ 1024. Teams are numbered from 1 to n, where team 1 is your favourite team.

• n lines, each containing a string of n binary digits. The k-th digit on the j-th line is ‘1’ if team j would certainly win from team k, otherwise it is ‘0’. A team cannot play against itself, therefore the j-th digit on the j-th line is ‘0’. If j ̸= k, the k-th digit on the j-th line is diﬀerent from the j-th digit on the k-th line.

Output

For each test case, print n−1 lines of output, specifying a tournament schedule that ensures victory for team 1. The ﬁrst n/2 lines describe the ﬁrst round of the tournament. The next n/4 lines describe the second round, if any, etc. The last line describes the ﬁnal match. Each line contains two integers x and y, indicating that team x plays a match against team y. If there are multiple tournament schedules where team 1 wins, any one of those tournament schedules will be accepted as a correct answer.

Sample Input

4
0110
0011
0000
1010
8
00111010
10101111
00010010
01000101
00110010
10101011
00010000
10101010

Sample Output

1 3
2 4
1 2
1 5
3 7
4 8
2 6
1 3
4 2
1 4

题解：这个题的构造比较难，我是想不到，构造出来之后的递归就相对比较简单了。构造的方式分为四个阶段：

1、把满足条件的队伍A和B配对，其中1打不过A，1能打过B，并且B能打过A.

2、把1和剩下的它能打过的队伍配对.

3、把1打不过的队伍相互配对.

4、把剩下的队伍配对.

能够证明按照这样的策略打过一轮之后，剩下的队伍还满足初始条件，因此可以递归求解。（构造太巧妙orz）

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 1050;
 6 
 7 int n;
 8 char gra[maxn][maxn];
 9 bool vis[maxn], have_failed[maxn];
10 
11 void dfs(int m) {
12     if (m == 1) return;
13 
14     memset(vis, false, sizeof(vis));
15     
16     for (int i = 2; i <= n; i++) {
17         if (have_failed[i] || vis[i]) continue;
18         if (gra[1][i] == '0') {
19             for (int j = 2; j <= n; j++) {
20                 if (have_failed[j] || vis[j]) continue;
21                 if (gra[1][j] == '1' && gra[j][i] == '1') {
22                     vis[j] = vis[i] = true;
23                     have_failed[i] = true;
24                     printf("%d %d
", i, j);
25                     break;
26                 }
27             }
28         }
29     }
30     
31     for (int i = 2; i <= n; i++) {
32         if (have_failed[i] || vis[i]) continue;
33         if (gra[1][i] == '1') {
34             vis[i] = true;
35             have_failed[i] = true;
36             printf("%d %d
", 1, i);
37             break;
38         }
39     }
40     
41     int flag = 0, pre = 0;
42     for (int i = 2; i <= n; i++) {
43         if (have_failed[i] || vis[i]) continue;
44         if (gra[1][i] == '0') {
45             if (!flag) {
46                 flag = 1;
47                 pre = i;
48             }
49             else {
50                 flag = 0;
51                 vis[i] = vis[pre] = true;
52                 printf("%d %d
", pre, i);
53                 if (gra[pre][i] == '0') have_failed[pre] = true;
54                 else have_failed[i] = true;
55             }
56         }
57     }
58     
59     flag = 0;
60     for (int i = 2; i <= n; i++) {
61         if (have_failed[i] || vis[i]) continue;
62         if (!flag) {
63             flag = 1;
64             pre = i;
65         }
66         else {
67             flag = 0;
68             vis[i] = vis[pre] = true;
69             printf("%d %d
", pre, i);
70             if (gra[pre][i] == '0') have_failed[pre] = true;
71             else have_failed[i] = true;
72         }
73     }
74 
75     dfs(m >> 1);
76 }
77 
78 int main()
79 {
80     //freopen("input.txt", "r", stdin);
81     //freopen("output.txt", "w", stdout);
82     while (~scanf("%d", &n)) {
83         memset(have_failed, false, sizeof(have_failed));
84         for (int i = 1; i <= n; i++) {
85             scanf("%s", gra[i] + 1);
86         }
87 
88         dfs(n);
89     }
90     return 0;
91 }