世界杯积分问题

2025-08-11 16:50:549103

首页题库面试求职学习竞赛搜索面经/职位/试题/公司搜索我要招人去企业版登录 / 注册首页 > 试题广场 > 世界杯积分问题 [编程题]世界...

首页

题库

面试

求职

学习

竞赛

搜索面经/职位/试题/公司

搜索

我要招人

去企业版

首页

试题广场

世界杯积分问题

[编程题]世界杯积分问题

热度指数：596

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

算法知识视频讲解

2022年卡塔尔世界杯是第一次在年底举行的世界杯，当然中国男足早早出局，为了让更多球队有机会参这项举世瞩目的盛会，传言2026年世界杯每个小组将有5支球队参加，进行单循环比赛, 每个小组总场数共打10场，每场比赛胜者得3分，负者得0分，如果踢平两队各得1分。求小组赛结束后，最终得分由高到低排列，去重之后会有多少种可能的情况，并对输入的得分组合判断其是否是一种可能的得分结果。比如一种可能得分是6 5 5 5 4，这时候不考虑是哪一支队伍排第一，只看最终得分的可能组合。

输入描述:

第一行，1个是int类型的值，判断这个值是不是小组赛排名后的得分去重后所有可能的组合的数目？第二行，输入5个是降序排列的int类型的数，判断这组值是不是可能的【小组赛排名后的得分】组合情况之一？

输出描述:

输出一行：对于两个判断，分别输出yes，或者no，用空格隔开，比如no yes

示例1

输入

328

6 5 5 5 4

输出

no yes

备注:

1、10场小组赛结束后，5支球队积分降序排列，这个时候已经不用考虑不同的球队了2、比赛的结果不完全相同，但是最终积分会出现相同可能，这个时候要去重

马上挑战

算法知识视频讲解

提交运行

算法知识视频讲解

添加笔记

求解答(0)

邀请回答

纠错

提交结果有问题?

9个回答

0篇题解

添加回答

撒大大撒

#include #include #include #include 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 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> ans; void dfs(vector 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 scores(5, 0); for (int i = 0; i < 5; i++) { cin >> scores[i]; } vector 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

月有残

楼上的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

文羊羽

回溯法，遍历，一共 3^10 种可能，使用 unorder_set 进行去重 #include

#include

using namespace std;

vector> rowcol = {{0,1},{0,2},{0,3},{0,4},

{1,2},{1,3},{1,4},

{2,3},{2,4},

{3,4}};

vector> gain = {{0,3}, {1,1}, {3,0}};

vector> scorematrix(5, vector(5, 0));

vector finalscore(5, 0);

unordered_set scoreset;

string vec2str(vector & 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 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

加麻加辣的小白很想找对象

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

人工一号

//直接dfs10场比赛即可

#include

using namespace std;

const int TEAM_N = 5;

int race[20];

set> p;

void rank_race() {

int race_cnt = 1;

vector 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<

// }

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 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

玛卡巴卡尔w33

#include

using namespace std;

typedef pair PII;

vector coms {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};

set> s;

vector temp (5, 0);

void dfs(int i) {

if (i == 10) {

vector 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 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

啊雷洛

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

吃呀吃没吃

#include #include #include #include using namespace std; constintNUM_TEAMS = 5; constintNUM_GAMES = 10; voidgenerateScores(vector& scores, intgame, vector>& matches, set>& scoreSets) { if(game == NUM_GAMES) { vector sortedScores = scores; sort(sortedScores.begin(), sortedScores.end(), greater()); 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 arr(5); cin >> n; for(inti = 0; i < 5; i++) cin >> arr[i]; // 比赛安排 (10 场比赛，按序列出队伍) vector> matches = { {0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} }; set> scoreSets; vector 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

会编程的亚瑟快支棱起来

求助大佬

发表于 2024-04-20 11:17:21

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：

9条回答

42收藏

424浏览