28127: 北大夺冠

hash table, http://cs101.openjudge.cn/practice/28127/

在刚刚结束的第46届国际大学生程序设计竞赛（简称ICPC），来自全球100多个国家的200多支大学队伍同场竞技。北京大学的三位选手（王展鹏、蒋凌宇、罗煜翔）获得了全球总决赛冠军，这也是北京大学历史最好成绩。

ICPC是全世界最高水平的算法竞赛，各个国家、各个大学最优秀的选手都会参加，比赛采用组队形式，3名选手，共用1台电脑，在5小时内解决10道左右非常困难的算法问题。相比真实比赛的排名规则，本题做了一些简化，请你写个程序计算最终排名。

共有 m 个提交记录，每个提交记录包含队伍名称、提交题目的编号和是否正确（即通过评测）。排序规则为：

做对题目多的队伍排名靠前；
做对题目数相同时，总提交次数较少的队伍排名靠前；
做对题目数和总提交次数都相同时，按队伍名称的字典序排名；

按上述规则输出前 12 名的队伍信息，几点说明和提示：

如果队伍总数不足 12 名，则输出所有队伍；
如果队伍在某题 AC 后重复提交此题，这时的提交仍然记入总提交数，但重复 AC 同一题不会增加“做对题目数目”；

输入

第一行一个整数 M (1 ≤ M ≤ 1000) 表示提交记录数目。接下去 M 行，每行一个提交记录，由逗号分隔的三部分组成，第一部分为队伍名称，仅有大小写字母和空格组成；第二部分为题目编号，必为大写字母A-Z之一；第三部分为评测结果，yes 表示通过，no 表示未通过。

输出

共 12 行（队伍总数不足 12 个时，输出全部队伍即可），按排名顺序依次输出每支队伍，包括名次（1开始）、队伍名称、做对题目数（重复AC同一题只计一次）、总提交次数，共四部分信息，信息之间用一个空格隔开。

样例输入

样例输入1
9
Peking University,A,no
Massachusetts Institute of Technology,A,yes
National Research University Higher School of Economics,A,no
University of Oxford,A,yes
Peking University,B,yes
Peking University,A,yes
University of Oxford,C,no
University of Oxford,C,no
National Research University Higher School of Economics,C,yes

样例输入2
31
University of Waterloo,C,yes
University of Waterloo,C,yes
University of Waterloo,C,yes
University of Waterloo,C,yes
University of Waterloo,C,yes
University of Waterloo,D,yes
University of Waterloo,D,no
University of Waterloo,D,yes
University of Waterloo,X,no
University of Waterloo,G,no
University of Waterloo,P,no
Peking University,A,no
Peking University,B,no
Peking University,Y,yes
Peking University,Z,no
Peking University,Y,no
Peking University,Y,yes
Peking University,Y,yes
Peking University,Z,yes
Peking University,A,yes
University of Warsaw,T,no
University of Warsaw,T,yes
University of Warsaw,F,no
University of Warsaw,F,no
University of Warsaw,F,no
University of Warsaw,F,no
University of Warsaw,F,no
University of Warsaw,F,yes
University of Warsaw,Q,no
University of Warsaw,F,no
University of Warsaw,B,no

样例输入3
14
TeamA,A,no
TeamB,B,yes
TeamC,C,no
TeamD,D,yes
TeamE,E,no
TeamF,F,yes
TeamG,G,no
TeamH,H,yes
TeamI,I,no
TeamJ,J,yes
TeamK,K,no
TeamL,L,yes
TeamM,M,no
TeamN,N,yes

样例输出

样例输出1
1 Peking University 2 3
2 Massachusetts Institute of Technology 1 1
3 National Research University Higher School of Economics 1 2
4 University of Oxford 1 3

样例输出2
1 Peking University 3 9
2 University of Warsaw 2 11
3 University of Waterloo 2 11

样例输出3
1 TeamB 1 1
2 TeamD 1 1
3 TeamF 1 1
4 TeamH 1 1
5 TeamJ 1 1
6 TeamL 1 1
7 TeamN 1 1
8 TeamA 0 1
9 TeamC 0 1
10 TeamE 0 1
11 TeamG 0 1
12 TeamI 0 1

来源：张老师和杜老师编程课

思路：用多个字典存储数据，方便实现同名的添加和修改，排序输出之前再合并到同一个列表里面，这样又变的有利于排序。

python

# 李云凌 24工学院
from collections import defaultdict

m = int(input())
leaderboard = defaultdict(list)
tries = defaultdict(int)
for _ in range(m):
    team, question, result = input().split(',')
    tries[team] += 1
    if result == 'yes':
        if question not in leaderboard[team]:
            leaderboard[team].append(question)
    else:
        if team not in leaderboard:
            leaderboard[team] = []

ans = []
for key, value in leaderboard.items():
    ans.append((100-len(value), tries[key], key))
ans.sort()
for rank, (correct, tri, team) in enumerate(ans[:12], start=1):
    print(rank, team, 100-correct, tri)

使用 defaultdict 存储每支队伍的提交信息，并根据排序规则进行排名。

python

import sys
from collections import defaultdict

def process_icpc_results(m, submissions):
    teams = defaultdict(lambda: {'solved': set(), 'attempts': defaultdict(int), 'total_attempts': 0})
    
    for record in submissions:
        team_name, problem, result = record.split(',')
        team_name = team_name.strip()
        problem = problem.strip()
        result = result.strip()
        
        teams[team_name]['attempts'][problem] += 1
        teams[team_name]['total_attempts'] += 1
        
        if result == 'yes':
            teams[team_name]['solved'].add(problem)
    
    ranking = sorted(
        teams.items(),
        key=lambda item: (-len(item[1]['solved']), item[1]['total_attempts'], item[0])
    )
    
    for rank, (team_name, data) in enumerate(ranking[:12], start=1):
        print(rank, team_name, len(data['solved']), data['total_attempts'])

if __name__ == "__main__":
    m = int(sys.stdin.readline().strip())
    submissions = [sys.stdin.readline().strip() for _ in range(m)]
    process_icpc_results(m, submissions)

Q: 这是什么意思： teams = defaultdict(lambda: {'solved': set(), 'attempts': defaultdict(int), 'total_attempts': 0})

这行代码使用了 collections.defaultdict 来初始化 teams 这个字典，它的作用是存储每个队伍的提交信息。让我们逐步解析它的结构：
python
teams = defaultdict(lambda: {'solved': set(), 'attempts': defaultdict(int), 'total_attempts': 0})
defaultdict(lambda: {...})
defaultdict 是 Python 标准库 collections 模块中的一种特殊字典，它允许在访问不存在的键时自动创建一个默认值。
这里 lambda: {...} 指定了每个新键的默认值是一个包含多个字段的字典。
该字典包含的字段：
'solved': set()
这是一个 set（集合），用来存储该队伍成功通过评测（AC，即 "Accepted"）的题目。
由于集合的特性，重复 AC 同一题不会增加题目计数，符合比赛规则。
'attempts': defaultdict(int)
这是另一个 defaultdict(int)，用来记录该队伍每道题的提交次数。
例如，teams["Peking University"]["attempts"]["A"] 表示北大队伍对题目 A 的提交次数。
'total_attempts': 0
这是一个整数，表示该队伍的总提交次数（无论是否 AC）。
示例：
假设有一条提交记录：
python
"Peking University,A,yes"
执行 teams["Peking University"]["attempts"]["A"] += 1 时：
由于 "Peking University" 还不在 teams 里，defaultdict 会自动创建：
python
teams["Peking University"] = {'solved': set(), 'attempts': defaultdict(int), 'total_attempts': 0}
然后 "A" 题的提交次数增加：
python
teams["Peking University"]["attempts"]["A"] += 1
"A" 题通过评测（yes），则加入 solved 集合：
python
teams["Peking University"]["solved"].add("A")
总提交次数 total_attempts 增加：
python
teams["Peking University"]["total_attempts"] += 1
这样，每个队伍的提交记录都会被自动初始化并正确存储！

28127: 北大夺冠 ​

28127: 北大夺冠