hdu 5873 Football Games 模拟、兰道定理Landau's Theorem

忘是亡心i 2022-09-25 14:19 7阅读 0赞

hdu 5873 Football Games 题目链接：[http://acm.split.hdu.edu.cn/showproblem.php?pid=5873][http_acm.split.hdu.edu.cn_showproblem.php_pid_5873]

题目描述：

# Football Games #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 841 Accepted Submission(s): 323**

Problem Description

A mysterious country will hold a football world championships---Abnormal Cup, attracting football teams and fans from all around the world. This country is so mysterious that none of the information of the games will be open to the public till the end of all the matches. And finally only the score of each team will be announced.  
  
At the first phase of the championships, teams are divided into  M groups using the single round robin rule where one and only one game will be played between each pair of teams within each group. The winner of a game scores 2 points, the loser scores 0, when the game is tied both score 1 point. The schedule of these games are unknown, only the scores of each team in each group are available.  
  
When those games finished, some insider revealed that there were some false scores in some groups. This has aroused great concern among the pubic, so the the Association of Credit Management (ACM) asks you to judge which groups' scores must be false.

Input

Multiple test cases, process till end of the input.  
  
For each case, the first line contains a positive integers  M, which is the number of groups.  
The  i\-th of the next  M lines begins with a positive integer  Bi representing the number of teams in the  i\-th group, followed by  Bi nonnegative integers representing the score of each team in this group.  
  
  
**number of test cases <= 10  
M<= 100  
B\[i\]<= 20000  
score of each team <= 20000**

Output

For each test case, output  M lines. Output \`\`F" (without quotes) if the scores in the i-th group must be false, output \`\`T" (without quotes) otherwise. See samples for detail.

Sample Input

2
    3 0 5 1
    2 1 1

Sample Output

F
    T

Source

[2016 ACM/ICPC Asia Regional Dalian Online][2016 ACM_ICPC Asia Regional Dalian Online]

题目大意：

每组球队中有若干个队伍，每两个队伍之间比赛，产生2分，胜得2分，负得0分，平手得1分，分别判断每组队伍得分是否正确，若得分正确，则输出T，否则输出F。

题目分析：

首先n个队伍两两之间比赛，能产生的分值一共有2\*(n\*(n-1)/2)种，所以，所有队伍的得分所得和一定为n\*(n-1)；其次每个队伍都会和其他的n-1个队伍进行比赛，所以，单个队伍的最大得分就是2\*(n-1)；再次，如果存在一个得分为0的队伍，那么就不可能存在得分任何一个得分为1的队伍，或者不可能存在两个或两个以上得分为0的队伍；最后，所有队伍要么赢了许多场，要么输了许多场，要么平了许多场，所以，在每个队伍的得分对2进行求模之后，所得到的结果为1的队伍的个数一定是偶数个。

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int B[20010];
    int sum;
    int main()
    {
        int M;
        int n;
        int geshu0,geshu1;
        while(scanf("%d",&M)!=EOF)
        {
            for(int t=0; t<M; t++)
            {
                sum=0;
                geshu0=geshu1=0;
                memset(B,0,sizeof(B));
                scanf("%d",&n);
                for(int i=1; i<=n; i++)
                {
                    scanf("%d",&B[i]);
                    if(B[i]==0)
                    {
                        geshu0++;
                    }
                    else if(B[i]==1)
                    {
                        geshu1++;
                    }
                    sum+=B[i];
                }
                if((sum!=(n*(n-1))) || (geshu0==1&&geshu1!=0) || geshu0>=2)
                {
                    printf("F\n");
                }
                else
                {
                    int flag=0;
                    for(int i=1; i<=n; i++)
                    {
                        if(B[i]>(2*(n-1)))
                        {
                            printf("F\n");
                            flag=1;
                            break;
                        }
                    }
                    if(flag==0)
                    {
                        int num=0;
                        for(int i=1; i<=n; i++)
                        {
                            num+=B[i]%2;
                        }
                        if(num%2==0)
                        {
                            printf("T\n");
                        }
                        else
                        {
                            printf("F\n");
                        }
                    }
                }
            }
        }
        return 0;
    }

官方题解：

如果没有平手选项, 赢得加一分的话, 可以用[Landau's Theorem][Landau_s Theorem]判定, 这题稍微修改下这个定理就好了. 令`s_1,s_2,...,s_ns1,s2,...,sn`是他们的得分序列, 从小到大拍个序, 使得`s_1 \le s_2 \le ... \le s_ns1≤s2≤...≤sn`, 那么这个序列合法, 当且仅当:

1.  `s_1+s_2+...+s_i \ge i(i-1)s1+s2+...+si≥i(i−1)`, 对于所有`1 \le i \le n - 11≤i≤n−1`
2.  `s_1+s_2+...+s_n=n(n-1)s1+s2+...+sn=n(n−1)`.

[http_acm.split.hdu.edu.cn_showproblem.php_pid_5873]: http://acm.split.hdu.edu.cn/showproblem.php?pid=5873
[2016 ACM_ICPC Asia Regional Dalian Online]: http://acm.split.hdu.edu.cn/search.php?field=problem&key=2016+ACM%2FICPC+Asia+Regional+Dalian+Online&source=1&searchmode=source
[Landau_s Theorem]: https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29