梦之队 (Wonder Team,Tehran 2007,LA 4094)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 using namespace std;
10 #define MAXN 10002
11 int main()
12 {
13     int n;
14     while(scanf("%d",&n),n!=0)
15     {
16         if(n<=3)printf("1
");
17         else if(n==4)printf("2
");
18         else printf("%d
",n);
19     }
20 
21 
22     return 0;
23 }

View Code

对于1<=n<=3 明显是1

对于n=4 可以发现答案是2

对于n>=5 我用下列矩阵表示一个构造，证明WonderTeam可以是最后：对于每个队伍的胜场，平局，败场分别用2,1,0表示，（最后一行是WonderTeam）

矩阵有n行，表示n个队伍；2*n-2列，表示某场比赛的胜负

由于进球数目和输球数目是任意的，所以我们可以假设每场比赛的失球数目和进球数目，则明显每个队伍都要有负场才行。

21111110 我们对这个矩阵进行微调，得到 22111110

21111110 22111110

21111110 22111100

22000000 22200000

这是一个最后一名的构造

对于n>5的情况，构造法相同:1-n-1行每行开头是2，末尾是0(因为要有失球数)，中间是1，最后一行开头是两个2，其余都是0，然后根据情况进行调整（从上到下将1变成2之类），使得最后一行的2最多，且分数最少即可

给出6的排列

2211111110

2111111110

2220000000

所以最终的代码只要判断一下即可。。。

以上摘自http://hi.baidu.com/isaacpei/item/1d8907c39392bc105150583c

逗比了很久~~