The 2016 ACM-ICPC Asia China-Final Contest L – World Cup
- 2020 年 4 月 9 日
- 筆記
World Cup
pdf题面: World Cup Description: 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. 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 Note 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 winning-cycle, 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.
Problem solving: 这道题的意思就是有四个队，每两个队之间都要进行一场比赛，获胜的队加三分，平局的话两个队都加一分。现在给你一个最后的分数的情况，问你可以不可以判断出比赛中胜负的情况。 如果可以就输出Yes，如果多种胜负情况都会出现这种结果，就输出No，如果不会有任何一种情况导致这种结果的出现就输出Wrong Scoreboard。
这里用一个结构体来表示四个队两两个队之间的关系。
总共六场比赛，每次比赛三种结果，用dfs枚举一下，算出所有情况，因为只有四个结果，并且每个结果都是小于等于9的数字，所以我们可以直接加成字符串存起来，然后用map进行标记。按照上面说的就是如果map的string的值为0就输出Wrong，值为1的话输出Yes，否则输出No。
其实这个dfs的过程还是很有意思的。注意回溯的过程。
Code:
#include <bits/stdc++.h> using namespace std; int score[4], T, jie[4]; struct node { int a, b; } pk[6] = { 0, 1, 0, 2, 0, 3, 1, 2, 1, 3, 2, 3 }; map<string, int> ma; void DFS(int n) { if (n == 6) { string mid; for (int i = 0; i < 4; i++) mid += score[i]; ma[mid]++; return; } for (int i = 0; i < 3; i++) { int x = score[pk[n].a], y = score[pk[n].b]; if (i == 0) score[pk[n].a] += 3; else if (i == 1) score[pk[n].b] += 3; else score[pk[n].a] += 1, score[pk[n].b] += 1; DFS(n + 1); score[pk[n].a] = x; score[pk[n].b] = y; } } int main() { DFS(0); cin >> T; for (int k = 1; k <= T; k++) { string mid; for (int i = 0; i < 4; i++) { cin >> jie[i]; mid += jie[i]; } printf("Case #%d: ", k); if (ma[mid] == 0) puts("Wrong Scoreboard"); else if (ma[mid] == 1) puts("Yes"); else puts("No"); } return 0; }
