此文章可以使用目录功能哟↑(点击上方[+])
HDU 5873 Football Games
Accept: 0 Submit: 0
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
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
3 0 5 1
2 1 1
Sample Output
T
Problem Idea
解题思路:
【题意】
M个分组,每个分组有n支球队
n支球队两两进行一轮比赛
赢的球队得2分,平局的球队得1分,输的球队得0分
现给你n支球队的最终得分
问这n支球队的最终得分是否一定是错的,是则输出"F";否则输出"T"
【类型】
签到题
【分析】
因为n支球队两两之间都会进行一轮比赛
所以每支球队都会参与n-1场比赛,即球队i会和另外的n-1支球队都比一场
假设n-1场比赛都获得胜利,那得分最高为2(n-1)
故凡是得分超过2(n-1)的球队得分都是错的
另外,由于一轮比赛,不管输赢还是平局,比赛双方球队获得的总分必定是2分
而两两之间进行一轮比赛,意味着比赛总共有n(n-1)/2场
所以最终所有球队的得分之和必定为n(n-1)
也就是说如果所有球队的最终得分之和不为n(n-1),那这个分数也是假的
循环判断一遍就可以了
【时间复杂度&&优化】
O(mn)
题目链接→HDU 5873 Football Games
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 20005;
const int M = 20005;
const int inf = 1000000007;
const int mod = 7;
int s[N];
int main()
{int m,n,i,sum;bool flag;while(~scanf("%d",&m)){while(m--){sum=0;flag=true;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&s[i]);sum+=s[i];if(s[i]>2*n-2)flag=false;}if(sum!=n*(n-1))flag=false;if(flag)puts("T");elseputs("F");}}return 0;
}