World Cup (dfs预处理)

World Cup (dfs预处理)

Here is World Cup again, the top 32 teams come together to fight for the World Champion. The teams are assigned into 8 groups, with 4 teams in each group. Every two teams in the same group will play a game (so there are totally 6 games in each group), and the winner of this game gets 3 points, loser gets 0 point. If it is a tie game, both teams get 1 point. After all games finished, we get the scoreboard, but we forget the result of each game, can you help us to figure the result of each game? We only care about the win/lose/tie result of each game, but we don’t care the goals in each game. Input The input starts with one line containing exactly one integer T, which is the number of test cases. Each test case contains four space-separated integers A, B, C, D, in a line, which indicate the points each team gets after all 6 games. Output For each test case, output one line containing ‘Case #x: y’, where x is the test case number (starting from 1) and y is ‘Yes’ if you can point out the result of each game, or ‘No’ if there are multiple game results satisfy the scoreboard, or ‘Wrong Scoreboard’ if there is no game result matches the scoreboard. Limits: • 1 ≤ T ≤ 100. • 0 ≤ A, B, C, D ≤ 100. Notes: In sample case #1, the only scenaro will be: the first team wins all the three games it plays, the second team loses to the first team and wins the other two, the third team only wins the game with the fourth, and the fourth team lose all the games. In sample case #2, the fourth team loses all the games, and the first three teams get into a winningcycle, but there may be two different winning-cycles: first team wins second team, second team wins third team, third team wins first team OR first team wins third team, third team wins second team, second team wins first team. We can’t figure which winning-cycle is the actual game result. In sample case #3, the first team get 10 points, but no team could get more than 9 points by play three games, so it is a wrong scoreboard. Sample Input 3 9 6 3 0 6 6 6 0 10 6 3 0 Sample Output Case #1: Yes Case #2: No Case #3: Wrong Scoreboard

题目大概:

有四支队伍进行比赛，然后这些队伍两只队伍之间进行一场比赛，赢了得3分，输了0分，平局各得1分。

现在给你各个队伍的分数，问对局方案是否存在，对局方案是否唯一。

不存在输出  Wrong Scoreboard   唯一输出  Yes   不唯一输出   No

思路：

用dfs处理出所有的比赛方案数。然后O(1)查询。

代码：

#include using namespace std;#define ll long longconst int maxn=1e5+10;const int INF=0x3f3f3f3f;const long long mod=1e18;const double pi=acos(-1);int sum;int dx[6]={1,1,1,2,2,3};int dy[6]={2,3,4,3,4,4};int dp[15][15][15][15];void dfs(int a[5],int b[5],int tem){ int flag=0; for(int i=1; i<=4; i++)if(b[i]!=3)flag=1; if(!flag){dp[a[1]][a[2]][a[3]][a[4]]++;return;} int i=dx[tem];int j=dy[tem]; if(b[i]<3&&b[j]<3) { a[i]+=3;b[i]++;b[j]++; dfs(a,b,tem+1); a[i]-=3;b[i]--;b[j]--; } if(b[i]<3&&b[j]<3) { a[j]+=3;b[i]++;b[j]++; dfs(a,b,tem+1); a[j]-=3;b[i]--;b[j]--; } if(b[i]<3&&b[j]<3) { a[j]+=1;a[i]+=1;b[i]++;b[j]++; dfs(a,b,tem+1); a[j]-=1;a[i]-=1;b[i]--;b[j]--; }}int a[5];int b[5];int main(){ dfs(a,b,0); int t; int ans=1; scanf("%d",&t); while(t--) { sum=0; for(int i=1; i<=4; i++)scanf("%d",&a[i]); if(dp[a[1]][a[2]][a[3]][a[4]]==0)printf("Case #%d: Wrong Scoreboard\n",ans++); else if(dp[a[1]][a[2]][a[3]][a[4]]==1)printf("Case #%d: Yes\n",ans++); else if(dp[a[1]][a[2]][a[3]][a[4]]>=2)printf("Case #%d: No\n",ans++); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。