2022年卡塔尔世界杯是第一次在年底举行的世界杯，当然中国男足早早出局，为了让更多球队有机会参这项举世瞩目的盛会，传言2026年世界杯每个小组将有5支球队参加，进行单循环比赛, 每个小组总场数共打10场，每场比赛胜者得3分，负者得0分，如果踢平两队各得1分。求小组赛结束后，最终得分由高到低排列，去重之后会有多少种可能的情况，并对输入的得分组合判断其是否是一种可能的得分结果。比如一种可能得分是6 5 5 5 4，这时候不考虑是哪一支队伍排第一，只看最终得分的可能组合。
[编程题]世界杯积分问题
- 热度指数：547 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行，1个是int类型的值，判断这个值是不是小组赛排名后的得分去重后所有可能的组合的数目？
第二行，输入5个是降序排列的int类型的数，判断这组值是不是可能的【小组赛排名后的得分】组合情况之一？
输出描述:
输出一行：对于两个判断，分别输出yes，或者no，用空格隔开，比如no yes
示例1
输入
328 6 5 5 5 4
输出
no yes
备注:
1、10场小组赛结束后，5支球队积分降序排列，这个时候已经不用考虑不同的球队了2、比赛的结果不完全相同，但是最终积分会出现相同可能，这个时候要去重
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
// games: 10
// 0 : 1 vs 2 , 1 : 1 vs 3 , 2 : 1 vs 4 , 3 : 1 vs 5
// 4 : 2 vs 3 , 5 : 2 vs 4 , 6 : 2 vs 5
// 7 : 3 vs 4 , 8 : 3 vs 5
// 9 : 4 vs 5
vector<int> getTeamNumsFromGameIndex(int gameIndex) {
switch (gameIndex) {
case 0:
return {1, 2};
case 1:
return {1, 3};
case 2:
return {1, 4};
case 3:
return {1, 5};
case 4:
return {2, 3};
case 5:
return {2, 4};
case 6:
return {2, 5};
case 7:
return {3, 4};
case 8:
return {3, 5};
case 9:
return {4, 5};
default:
return {};
}
return {};
}
set<vector<int>> ans;
void dfs(vector<int> tmpScore, int gameIndex) {
if (gameIndex == 10) {
sort(tmpScore.begin(), tmpScore.end(), [](int x1, int x2) {
return x1 >= x2;
});
ans.insert(tmpScore);
return;
}
auto twoTeams = getTeamNumsFromGameIndex(gameIndex);
auto TeamA = twoTeams[0];
auto TeamB = twoTeams[1];
// TeamA win
tmpScore[TeamA - 1] += 3;
dfs(tmpScore,gameIndex + 1);
tmpScore[TeamA - 1] -= 3;
// TeamA lose
tmpScore[TeamB - 1] += 3;
dfs(tmpScore,gameIndex + 1);
tmpScore[TeamB - 1] -= 3;
// Team Tie
tmpScore[TeamA - 1] += 1;
tmpScore[TeamB - 1] += 1;
dfs(tmpScore,gameIndex + 1);
tmpScore[TeamA - 1] -= 1;
tmpScore[TeamB - 1] -= 1;
}
int main() {
int n;
cin >> n;
vector<int> scores(5, 0);
for (int i = 0; i < 5; i++) {
cin >> scores[i];
}
vector<int> tmpScore(5,0);
dfs(tmpScore,0);
if(n == (int)ans.size()){
std::cout <<"yes" << " ";
}else{
std::cout <<"no" << " ";
}
if(ans.find(scores) != ans.end()){
std::cout << "yes";
}else{
std::cout << "no";
}
return 0;
}
// 64 位输出请用 printf("%lld")
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
// games: 10
// 0 : 1 vs 2 , 1 : 1 vs 3 , 2 : 1 vs 4 , 3 : 1 vs 5
// 4 : 2 vs 3 , 5 : 2 vs 4 , 6 : 2 vs 5
// 7 : 3 vs 4 , 8 : 3 vs 5
// 9 : 4 vs 5
vector<int> getTeamNumsFromGameIndex(int gameIndex) {
switch (gameIndex) {
case 0:
return {1, 2};
case 1:
return {1, 3};
case 2:
return {1, 4};
case 3:
return {1, 5};
case 4:
return {2, 3};
case 5:
return {2, 4};
case 6:
return {2, 5};
case 7:
return {3, 4};
case 8:
return {3, 5};
case 9:
return {4, 5};
default:
return {};
}
return {};
}
set<vector<int>> ans;
void dfs(vector<int> tmpScore, int gameIndex) {
if (gameIndex == 10) {
sort(tmpScore.begin(), tmpScore.end(), [](int x1, int x2) {
return x1 >= x2;
});
ans.insert(tmpScore);
return;
}
auto twoTeams = getTeamNumsFromGameIndex(gameIndex);
auto TeamA = twoTeams[0];
auto TeamB = twoTeams[1];
// TeamA win
tmpScore[TeamA - 1] += 3;
dfs(tmpScore,gameIndex + 1);
tmpScore[TeamA - 1] -= 3;
// TeamA lose
tmpScore[TeamB - 1] += 3;
dfs(tmpScore,gameIndex + 1);
tmpScore[TeamB - 1] -= 3;
// Team Tie
tmpScore[TeamA - 1] += 1;
tmpScore[TeamB - 1] += 1;
dfs(tmpScore,gameIndex + 1);
tmpScore[TeamA - 1] -= 1;
tmpScore[TeamB - 1] -= 1;
}
int main() {
int n;
cin >> n;
vector<int> scores(5, 0);
for (int i = 0; i < 5; i++) {
cin >> scores[i];
}
vector<int> tmpScore(5,0);
dfs(tmpScore,0);
if(n == (int)ans.size()){
std::cout <<"yes" << " ";
}else{
std::cout <<"no" << " ";
}
if(ans.find(scores) != ans.end()){
std::cout << "yes";
}else{
std::cout << "no";
}
return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2024-08-02 00:00:42
回复(0)
楼上的DFS加了些注释：
DEBUG = False
ans = set()
def dfs(i, j, score, cur_result):
# 0: i胜利, 1: j胜利, 2:平局
if cur_result == 0:
score[i] += 3
elif cur_result == 1:
score[j] += 3
else:
score[i] += 1
score[j] += 1
if i == 4 and j == 5: # 当所有比赛都完成时
ans.add(tuple(sorted(score[1:], reverse=True)))
return
nxt_i = i
nxt_j = j + 1
if nxt_j > 5: # 如果下一队的编号超过了队伍总数，则增加当前队的编号
nxt_i += 1
nxt_j = nxt_i + 1
# 继续递归
for result in range(3):
dfs(nxt_i, nxt_j, list(score), result)
# 从第1队开始，进行递归调用
for result in range(3):
dfs(1, 2, [0] * 6, result)
full_cnt = len(ans)
if DEBUG:
print(full_cnt)
quest_cnt = int(input())
quest_comb = tuple(sorted(map(int, input().split()), reverse=True))
print(f"{'yes' if full_cnt == quest_cnt else 'no'} {'yes' if quest_comb in ans else 'no'}")
发表于 2024-09-16 14:24:52
回复(0)
回溯法，遍历，一共 3^10 种可能，使用 unorder_set<string> 进行去重
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
vector<vector<int>> rowcol = {{0,1},{0,2},{0,3},{0,4},
{1,2},{1,3},{1,4},
{2,3},{2,4},
{3,4}};
vector<vector<int>> gain = {{0,3}, {1,1}, {3,0}};
vector<vector<int>> scorematrix(5, vector<int>(5, 0));
vector<int> finalscore(5, 0);
unordered_set<string> scoreset;
string vec2str(vector<int> & vec) {
string str;
for(int i : vec) {
str.push_back((char)(i + '0'));
}
return str;
}
void backtrace(int idx) {
if(idx == 10) {
for(int i=0; i<5; i++) {
finalscore[i] = accumulate(scorematrix[i].begin(), scorematrix[i].end(), 0);
}
sort(finalscore.begin(), finalscore.end(), greater<>());
string scorestr = vec2str(finalscore);
scoreset.insert(scorestr);
}
if(idx >= 10) return;
int row = rowcol[idx][0];
int col = rowcol[idx][1];
for(auto & score : gain) {
scorematrix[row][col] = score[0];
scorematrix[col][row] = score[1];
backtrace(idx+1);
scorematrix[row][col] = 0;
scorematrix[col][row] = 0;
}
return;
}
int main() {
backtrace(0);
int totalnum = scoreset.size();
// cout << totalnum << endl; // 355
int inputnum; cin >> inputnum;
totalnum == inputnum ? cout << "yes " : cout << "no ";
vector<int> inputscore(5, 0);
for(int i=0; i<5; i++) cin >> inputscore[i];
string inputstr = vec2str(inputscore);
scoreset.find(inputstr) != scoreset.end() ? cout << "yes" : cout << "no";
return 0;
}
// 64 位输出请用 printf("%lld")
编辑于 2024-09-04 16:36:11
回复(0)
from copy import deepcopy
scores = []
#枚举10轮比赛，0vs1, 0vs2, 0vs3, 0vs4, 1vs2, 1vs3, 1vs4, 2vs3, ...3vs4
def enum(epoch, score):
if epoch == 10:
scores.append(score)
return
for i in [1, 0, 3]:
score.append(i)
enum(epoch+1, deepcopy(score))
score = score[:-1]
enum(0, [])
#对于每中可能得10场比赛分别计算每个队伍获得的分数，并排序
scores = [
sorted([
sum(score[:4]),
sum([score[i] if score[i] == 1 else 3 - score[i] for i in [0]] + score[4:7]),
sum([score[i] if score[i] == 1 else 3 - score[i] for i in [1, 4]] + score[7:9]),
sum([score[i] if score[i] == 1 else 3 - score[i] for i in [2, 5, 7]] + score[9:10]),
sum([score[i] if score[i] == 1 else 3 - score[i] for i in [3, 6, 8, 9]]),
], reverse=True)
for score in scores
]
#转为字符，去重
scores = [list(map(str, score)) for score in scores]
scores = set([" ".join(score) for score in scores])
total = len(scores)
if __name__ == "__main__":
N = input()
score = input()
print("yes" if int(N) == total else "no", "yes" if score in scores else "no")
发表于 2024-08-13 21:52:53
回复(0)
//直接dfs10场比赛即可
#include <algorithm>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int TEAM_N = 5;
int race[20];
set<vector<int>> p;
void rank_race() {
int race_cnt = 1;
vector<int> team_rank(5, 0);
for(int i = 0; i < TEAM_N; i++) {
for(int j = 0; j < i; j++) {
if(race[race_cnt] == 1) {
team_rank[i] += 3;
}
else if(race[race_cnt] == 0) {
team_rank[i] += 1;
team_rank[j] += 1;
}
else {
team_rank[j] += 3;
}
race_cnt++;
}
}
sort(team_rank.rbegin(), team_rank.rend());
// for(int i = 1; i <= TEAM_N; i++) {
// cout<<team_rank[i];
// }
p.insert(team_rank);
}
void dfs(int cur) {
if(cur == 11) {
rank_race();
return;
}
race[cur] = 1;
dfs(cur + 1);
race[cur] = 0;
dfs(cur + 1);
race[cur] = -1;
dfs(cur + 1);
}
int main() {
dfs(1);
int ans = p.size();
int ans_mb;
cin>>ans_mb;
if(ans_mb != ans) cout<<"no";
else cout<<"yes";
cout<<" ";
vector<int> p_t;
for(int i = 1; i <= TEAM_N; i++) {
int a;
cin>>a;
p_t.push_back(a);
}
if(p.find(p_t) != p.end()) cout<<"yes";
else cout<<"no";
return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2025-03-02 00:31:08
回复(0)
#include <functional>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<PII> coms {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};
set<vector<int>> s;
vector<int> temp (5, 0);
void dfs(int i) {
if (i == 10) {
vector<int> backup = temp;
sort(backup.begin(), backup.end(), greater<> ());
s.insert(backup);
return ;
}
auto& [a, b] = coms[i];
// a win
temp[a - 1] += 3;
dfs(i + 1);
// b win
temp[a - 1] -= 3;
temp[b - 1] += 3;
dfs(i + 1);
// a-b
temp[a - 1] += 1;
temp[b - 1] -= 2;
dfs(i + 1);
temp[a - 1] -= 1;
temp[b - 1] -= 1;
}
int main() {
dfs(0);
int query = 0;
cin >> query;
if (query == s.size()) cout << "yes ";
else cout << "no ";
vector<int> query_arr (5, 0);
for (int i = 0; i < 5; i ++) {
cin >> query_arr[i];
}
if (s.count(query_arr)) cout << "yes ";
else cout << "no ";
return 0;
}
发表于 2024-11-09 17:20:23
回复(0)
dfs启动！
def solve():
ans = set()
def dfs(i, j, score, cur_result):
# 0: i胜利, 1: j胜利, 2:平局
if cur_result == 0:
score[i] += 3
elif cur_result == 1:
score[j] += 3
else:
score[i] += 1
score[j] += 1
if i == 4 and j == 5:
ans.add(tuple(sorted(score[1:], reverse=True)))
return
nxt_i = i
nxt_j = j + 1
if nxt_j > 5:
nxt_i += 1
nxt_j = nxt_i + 1
for result in range(3):
dfs(nxt_i, nxt_j, list(score), result)
for result in range(3):
dfs(1, 2, [0, 0, 0, 0, 0, 0], result)
full_cnt = len(ans)
quest_cnt = int(input())
quest_comb = tuple(sorted(map(int, input().split()), reverse=True))
print(f"{'yes' if full_cnt == quest_cnt else 'no'} {'yes' if quest_comb in ans else 'no'}")
solve()
编辑于 2024-08-30 11:20:40
回复(0)
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
constintNUM_TEAMS = 5;
constintNUM_GAMES = 10;
voidgenerateScores(vector<int>& scores, intgame,
vector<pair<int, int>>& matches, set<vector<int>>& scoreSets) {
if(game == NUM_GAMES) {
vector<int> sortedScores = scores;
sort(sortedScores.begin(), sortedScores.end(), greater<int>());
scoreSets.insert(sortedScores);
return;
}
// 获取当前比赛的队伍
intteam1 = matches[game].first;
intteam2 = matches[game].second;
// team1 胜，team2 负
scores[team1] += 3;
generateScores(scores, game + 1, matches, scoreSets);
scores[team1] -= 3;
// team2 胜，team1 负
scores[team2] += 3;
generateScores(scores, game + 1, matches, scoreSets);
scores[team2] -= 3;
// 平局
scores[team1] += 1;
scores[team2] += 1;
generateScores(scores, game + 1, matches, scoreSets);
scores[team1] -= 1;
scores[team2] -= 1;
}
intmain() {
intn;
vector<int> arr(5);
cin >> n;
for(inti = 0; i < 5; i++)
cin >> arr[i];
// 比赛安排 (10 场比赛，按序列出队伍)
vector<pair<int, int>> matches = {
{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
};
set<vector<int>> scoreSets;
vector<int> scores(NUM_TEAMS, 0);
generateScores(scores, 0, matches, scoreSets);
if(n == scoreSets.size()) cout << "yes ";
elsecout << "no ";
if(scoreSets.find(arr) != scoreSets.end()) cout << "yes"<< endl;
elsecout << "no"<< endl;
return0;
}
发表于 2024-07-12 14:00:21
回复(0)
问题信息
难度：
9条回答
40收藏
330浏览
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
