首页 > 代码库 > HDU 5873 Football Games 【模拟】 (2016 ACM/ICPC Asia Regional Dalian Online)
HDU 5873 Football Games 【模拟】 (2016 ACM/ICPC Asia Regional Dalian Online)
Football Games
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 802 Accepted Submission(s): 309Problem DescriptionA 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.
InputMultiple 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
OutputFor 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 Input23 0 5 12 1 1
Sample OutputFT
Source2016 ACM/ICPC Asia Regional Dalian Online
Recommendwange2014 | We have carefully selected several similar problems for you: 5877 5875 5872 5871 5870
Statistic | Submit | Discuss | Note
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5873
题目大意:
多组数据(<=10),每组数据有M(M<=100)个小组,每个小组有N(N<=20000)支球队,每个小组内有一轮单循环赛(一个队与其他所有队只比一次),赢得2分,平各得1分,输得0分。
现在给N个球队的最终得分,问是否合法。
题目思路:
【模拟】
因为一场比赛会使得得分之和+2,所以sum!=n*(n-1)的必然不合法。
接着考虑假设没有平局,得分最高的队最多得2*(N-1)分,第二高2*(N-2),将球队分数从小到打排序,从后往前做,记S为剩余可分配的分数。
S+=a[i]-2*(i-1)表示当前得分扣除最高得分还多余或缺少多少分(如果之前有平局会剩余分数加到后面由负变平的队伍),当S<0时说明前面剩余可分配的分数不够了,就不合法。
其他情况都是合法的。
1 // 2 //by coolxxx 3 //#include<bits/stdc++.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string> 7 #include<iomanip> 8 #include<map> 9 #include<stack>10 #include<queue>11 #include<set>12 #include<bitset>13 #include<memory.h>14 #include<time.h>15 #include<stdio.h>16 #include<stdlib.h>17 #include<string.h>18 //#include<stdbool.h>19 #include<math.h>20 #define min(a,b) ((a)<(b)?(a):(b))21 #define max(a,b) ((a)>(b)?(a):(b))22 #define abs(a) ((a)>0?(a):(-(a)))23 #define lowbit(a) (a&(-a))24 #define sqr(a) ((a)*(a))25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))26 #define mem(a,b) memset(a,b,sizeof(a))27 #define eps (1e-10)28 #define J 1000029 #define mod 100000000730 #define MAX 0x7f7f7f7f31 #define PI 3.1415926535897932332 #pragma comment(linker,"/STACK:1024000000,1024000000")33 #define N 2000434 using namespace std;35 typedef long long LL;36 double anss;37 LL aans;38 int cas,cass;39 int n,m,lll,ans;40 int a[N];41 LL sum;42 bool cmp(int aa,int bb)43 {44 return aa<bb;45 }46 bool judge()47 {48 int i;49 LL s=0;50 if(sum!=1LL*n*(n-1))return 1;51 sort(a,a+n,cmp);52 for(i=n-1;i>=0;i--)53 {54 s+=i*2-a[i];55 if(s<0)return 1;56 }57 return 0;58 }59 int main()60 {61 #ifndef ONLINE_JUDGE62 // freopen("1.txt","r",stdin);63 // freopen("2.txt","w",stdout);64 #endif65 int i,j,k;66 int x,y,z;67 // init();68 // for(scanf("%d",&cass);cass;cass--)69 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++)70 // while(~scanf("%s",s))71 // while(~scanf("%d",&n))72 while(~scanf("%d",&cas))73 {74 while(cas--)75 {76 sum=cass=0;77 scanf("%d",&n);78 for(i=0;i<n;i++)79 {80 scanf("%d",&a[i]);81 sum+=a[i];82 }83 if(judge())puts("F");84 else puts("T");85 }86 }87 return 0;88 }89 /*90 //91 92 //93 */
HDU 5873 Football Games 【模拟】 (2016 ACM/ICPC Asia Regional Dalian Online)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。