UVA11222题解：序列处理与集合运算的边界条件实战

1. 从一道没人做出来的题说起第一次看到 UVA11222 这个题号的时候我正处在刷题最密集的那段时间。题目名字叫 Only I did it!直译过来就是只有我做出来了。光看名字你可能以为是什么高深的算法题实际上它是一道非常典型的序列处理题核心逻辑简单到可以用一句话概括找出每个人独有的、别人都没做出来的题目编号。但就是这么一道看起来人畜无害的题我在上面栽了不止一次。原因不是算法难而是边界条件多、输出格式刁钻、去重逻辑容易想当然。后来我在带新人练习的时候发现这道题几乎成了检验序列处理基本功的试金石——能一次 AC 的人往往对集合运算、排序、去重这些操作有清晰的认识反复 WA 的人问题基本都出在细节上。所以这篇文章我想把这道题彻底拆开讲透。不只是给你一份能过的代码而是把为什么这样设计、每一步在防什么坑、序列处理这类题的通用套路都讲清楚。如果你正在刷 UVA 的题目或者想系统提升自己对序列和集合操作的理解这篇内容应该能帮到你。哪怕你从没接触过 UVA只要你会写循环、会用数组就能跟上。先说清楚这道题到底在干什么。题目会给你若干个参赛者每个人做对了一些题目题目用正整数编号表示。你要找出每个参赛者独有的题目——也就是这道题只有他一个人做对了其他人都没做出来。然后按规则输出。听起来很简单对吧但独有这个词的定义、多个人并列时的处理、输出格式的细节才是真正拉开差距的地方。2. 题目规则逐条拆解别被简单两个字骗了2.1 输入结构到底长什么样这道题的输入格式是典型的 UVA 风格第一行给出测试用例的数量接下来每个测试用例先给出参赛人数然后每个人一行每行开头是他做对的题目数量后面跟着具体的题目编号。我用一个具体的例子来说明。假设有 3 个参赛者参赛者 1 做对了 3 道题编号 1、2、3参赛者 2 做对了 2 道题编号 2、3参赛者 3 做对了 1 道题编号 3那么谁有独有的题目参赛者 1 的题目 1 只有他做出来了所以参赛者 1 有一道独有题。参赛者 2 的题目 2 和 3 都被别人做出来了没有独有题。参赛者 3 的题目 3 也被别人做出来了同样没有独有题。这里第一个容易踩的坑就出现了题目编号可能重复出现在同一个人的列表里吗按照题目的常规设定同一个人的题目列表里不应该有重复但实际数据中偶尔会出现。如果你不去重统计这道题被几个人做出来的时候就会算错。我的建议是读入每个人的题目列表后先做一次去重用集合或者排序后去重都行这一步花不了多少时间但能省掉后面一堆麻烦。2.2 独有的精确含义独有这个词必须精确理解。一道题被称为某个参赛者独有需要同时满足两个条件这个参赛者做对了这道题除了他之外没有任何其他参赛者做对这道题注意是没有任何其他参赛者而不是做对这道题的人数最少。这两者差别很大。举个例子如果一道题被参赛者 A 和 B 同时做对那它既不是 A 的独有题也不是 B 的独有题哪怕做对它的人只有两个。只有当一道题恰好被一个人做对时它才成为那个人的独有题。这个定义直接决定了算法思路我们需要统计每道题被哪些人做对了。最自然的做法是用一个映射结构键是题目编号值是一个列表记录做对这道题的所有参赛者编号。遍历完所有人的数据后凡是列表长度为 1 的题目就是某个人的独有题。2.3 输出格式的魔鬼细节UVA 的题目有个特点算法本身不难但输出格式能卡掉一半人。这道题也不例外。输出要求大致是这样的先输出一行Case #X:其中 X 是测试用例编号从 1 开始然后对于每个有独有题的参赛者输出一行包含参赛者编号、独有题数量、以及所有独有题编号按升序排列参赛者之间按独有题数量从多到少排序数量相同时按参赛者编号从小到大排序如果某个人没有独有题他不出现在输出里这里有几个细节必须注意。第一题目编号要升序输出不能按读入顺序。第二参赛者排序是先按独有题数量降序再按编号升序这个双关键字排序很容易写错。第三如果所有人都有独有题那所有人都要输出如果只有部分人有只输出有独有题的那些人。我见过不少人在这里翻车要么是忘了排序要么是排序关键字搞反了要么是题目编号没升序。这些都不是算法问题纯粹是审题和细节处理的问题。3. 核心算法设计从暴力到优雅3.1 最直观的思路与它的代价拿到这道题最直接的想法可能是对于每个人遍历他的每一道题然后检查这道题是否出现在其他所有人的列表里。如果没出现就是独有题。这个思路逻辑上完全正确但复杂度不理想。假设有 N 个人每个人平均有 M 道题那么对每个人的每道题都要扫描其他 N-1 个人的列表总复杂度大约是 O(N²M)。在数据量小的时候没问题但如果题目数量大就会比较吃力。更重要的是这个思路写起来容易出错。每次检查都要遍历别人的列表边界条件多代码冗长。我早期就是这么写的结果因为一个下标越界调了半天。3.2 用题目视角重新组织数据换个角度想问题效率会高很多。与其从人出发去检查每道题不如从题目出发统计每道题被谁做对了。具体做法是维护一个映射键是题目编号值是一个集合或列表存放做对这道题的所有参赛者编号。遍历每个人的题目列表把当前参赛者编号加入对应题目的记录中。全部遍历完之后再遍历这个映射凡是记录里只有一个参赛者的题目就是那个参赛者的独有题。这个思路的复杂度是 O(总题目数)因为每道题只需要处理一次。而且代码结构清晰不容易出错。这就是典型的用空间换时间、用数据结构简化逻辑的做法。我用 Python 写一下核心部分你可以感受一下from collections import defaultdict # problem_owners[题目编号] 做对这道题的人组成的集合 problem_owners defaultdict(set) for person_id, problems in enumerate(all_problems, start1): for p in set(problems): # 先去重 problem_owners[p].add(person_id) # 统计每个人的独有题 unique defaultdict(list) for p, owners in problem_owners.items(): if len(owners) 1: owner next(iter(owners)) unique[owner].append(p)这段代码里set(problems)那一步就是去重防止同一个人的重复题目影响统计。defaultdict(set)保证了每道题的记录自动初始化。最后遍历problem_owners长度为 1 的记录对应的就是独有题。3.3 为什么用集合而不是列表有人可能会问记录做对某道题的人用列表不行吗当然行但用集合有两个好处。第一自动去重万一同一个人被重复加入集合会帮你处理掉。第二判断是否只有一个人只需要看长度不需要额外去重。不过要注意集合是无序的如果你需要按顺序输出做对某道题的人就得额外排序。但在这道题里我们只关心是不是只有一个人所以集合完全够用。如果你用的是 C可以用mapint, setint或者mapint, vectorint配合去重。Java 的话用HashMapInteger, SetInteger。思路是一样的选你熟悉的语言就行。4. 排序与输出最容易丢分的地方4.1 双关键字排序的正确写法前面提到参赛者要按独有题数量降序、编号升序排列。这个双关键字排序是很多人出错的地方。我用 Python 举例说明正确的写法# 假设 unique 是 {参赛者编号: [独有题列表]} result [] for person_id, problems in unique.items(): result.append((person_id, sorted(problems))) # 排序先按独有题数量降序再按编号升序 result.sort(keylambda x: (-len(x[1]), x[0]))关键在key函数里-len(x[1])实现了数量降序因为 Python 默认升序取负就变成降序x[0]实现了编号升序。这个技巧很常用记住就行。如果你用 C可以写一个自定义比较函数sort(result.begin(), result.end(), [](const auto a, const auto b) { if (a.problems.size() ! b.problems.size()) return a.problems.size() b.problems.size(); // 数量降序 return a.id b.id; // 编号升序 });这里要注意比较函数必须满足严格弱序否则在某些编译器上会出问题。上面这个写法是安全的。4.2 输出格式的逐字符检查输出部分我建议你逐字符对照题目要求不要凭感觉写。常见的坑包括Case #1:后面有没有空格冒号是英文还是中文参赛者编号和独有题数量之间用什么分隔题目编号之间用什么分隔最后一个编号后面有没有多余空格每个测试用例之间要不要空行这些细节题目描述里都会写清楚但很多人扫一眼就过了。我的习惯是把题目里的输出样例复制下来和自己的输出做逐字符对比用diff工具或者肉眼都行。UVA 的评测是严格匹配的多一个空格就是 WA。提示UVA 题目的输出格式要求通常非常严格建议在本地写好之后用题目给的样例数据跑一遍把输出和标准答案做精确对比确认每一个空格和换行都一致。4.3 一个容易忽略的边界所有人都没有独有题如果所有题目都被至少两个人做对那么没有人有独有题。这时候输出应该只有Case #X:这一行后面什么都不跟。很多人会忘记处理这种情况导致输出格式错误。还有一种情况是只有一个人参赛。这时候他做的所有题都是独有题因为其他参赛者不存在。这个边界也要考虑进去。虽然实际测试数据里可能不常见但严谨的代码应该能正确处理。5. 我在调试这道题时踩过的坑5.1 去重没做导致统计错误前面反复强调去重是因为我真的在这上面栽过。当时我读入数据后直接统计没有对每个人的题目列表去重。结果有一组数据里某个人的列表中有重复编号导致这道题被统计了两次系统认为有两个人做对了实际上只有一个人。这个 bug 很隐蔽因为大部分测试数据没有重复只有特定数据才会触发。后来我养成了一个习惯凡是涉及统计出现次数的题目读入数据后第一件事就是去重。这个习惯帮我避免了很多类似的错误。5.2 排序关键字写反双关键字排序我写反过一次把数量降序写成了数量升序。结果输出顺序完全不对但每行内容都是对的所以看起来像是格式问题实际上排序逻辑错了。这种错误很难通过看输出发现因为内容本身没错只是顺序不对。我的建议是写完排序后手动构造一组有并列情况的测试数据验证排序结果是否符合预期。比如让两个人有相同数量的独有题看他们的输出顺序是不是按编号升序。5.3 题目编号没升序输出题目要求独有题编号升序输出我一开始按读入顺序输出结果 WA。这个错误的原因是我用列表记录独有题但没有排序。修复方法很简单输出前对列表排个序就行。但如果不仔细看题目要求很容易忽略这一点。5.4 多测试用例之间的状态清理这道题有多个测试用例每个用例之间要清理全局状态。我见过有人把problem_owners定义在循环外面导致上一个用例的数据污染下一个用例。这种错误在单用例测试时不会暴露只有多用例才会出问题。正确的做法是每个测试用例开始时重新初始化所有数据结构。在 Python 里把defaultdict定义在循环内部就行。在 C 里注意清空map和vector。6. 序列处理类题目的通用套路6.1 先想清楚统计维度序列处理题的核心往往是统计。统计什么按什么维度统计这道题统计的是每道题被谁做对维度是题目。换一道题可能是统计每个数字出现的次数维度是数字。想清楚统计维度数据结构就自然出来了。我的经验是先画一个表格行和列分别代表什么单元格里存什么。这个表格想清楚了代码就是把表格翻译成数据结构。这道题的表格就是行是题目编号列是参赛者单元格是是否做对。我们要找的是每行只有一个是的那些行。6.2 集合运算的三种基本操作序列处理离不开集合运算。最基本的有三种并集、交集、差集。这道题用到的其实是计数——统计每个元素出现在多少个集合里。但很多类似题目会直接考并集、交集、差集。比如找出两个人共同做对的题目就是交集找出两个人所有做过的题目就是并集找出第一个人做对但第二个人没做对的题目就是差集。Python 的set类型直接支持这些操作C 的set_intersection、set_union、set_difference也能用。熟练掌握这些操作能省很多事。6.3 排序是序列处理的半壁江山序列处理题里排序出现的频率极高。有的是直接要求排序输出有的是排序后便于后续处理。这道题两者都有独有题要排序输出参赛者要按规则排序。我建议你熟练掌握至少一种语言的排序写法包括单关键字和多关键字。Python 的sort(keylambda ...)和 C 的sort配合自定义比较函数是最常用的两种。多关键字排序的核心技巧就是把排序键组合成一个元组Python 里直接写keylambda x: (key1, key2)C 里在比较函数里逐级判断。6.4 边界条件的检查清单每次写完序列处理题我都会过一遍这个清单空输入怎么处理只有一个元素怎么处理所有元素都相同怎么处理有重复元素怎么处理最大数据量下会不会超时或超内存输出格式是否和题目要求完全一致这道题对应的边界就是没有人有独有题、只有一个人参赛、题目编号有重复、多个测试用例。把这些都想一遍基本就不会有遗漏了。7. 完整代码实现与逐行注释下面我给出一个完整的 Python 实现你可以直接拿去用也可以对照着自己的代码检查。import sys from collections import defaultdict def solve(): data sys.stdin.read().strip().split() if not data: return idx 0 t int(data[idx]); idx 1 output_lines [] for case_num in range(1, t 1): n int(data[idx]); idx 1 # problem_owners[题目编号] 做对这道题的参赛者集合 problem_owners defaultdict(set) for person in range(1, n 1): m int(data[idx]); idx 1 problems [] for _ in range(m): problems.append(int(data[idx])); idx 1 # 去重后加入统计 for p in set(problems): problem_owners[p].add(person) # 统计每个人的独有题 unique defaultdict(list) for p, owners in problem_owners.items(): if len(owners) 1: owner next(iter(owners)) unique[owner].append(p) # 构造输出 output_lines.append(fCase #{case_num}:) if unique: result [] for person_id, problems in unique.items(): result.append((person_id, sorted(problems))) # 独有题数量降序编号升序 result.sort(keylambda x: (-len(x[1]), x[0])) for person_id, problems in result: line f{person_id} {len(problems)} for p in problems: line f {p} output_lines.append(line) print(\n.join(output_lines)) if __name__ __main__: solve()这段代码有几个值得说明的地方。第一我用sys.stdin.read().split()一次性读入所有数据然后按索引取用。这种写法在处理 UVA 题目时很常见因为输入格式可能有多余空格或换行用split()可以自动处理。第二set(problems)那一步做了去重。第三排序用了-len(x[1])实现降序。第四输出用列表收集后统一打印避免频繁 IO。如果你用 C结构类似只是数据结构换成mapint, setint排序用自定义比较函数。核心逻辑完全一样。8. 从这道题延伸出去的学习建议这道题虽然简单但它涉及的技能点很全面输入解析、集合去重、映射统计、多关键字排序、格式化输出。这些技能在更复杂的题目里会反复出现。我的建议是不要满足于过了就行而是把这道题当成一个模板把里面的每个操作都练到熟练。比如你可以试着用不同的数据结构实现同一道题用数组代替映射、用位运算代替集合、用计数排序代替普通排序。每种实现都有它的适用场景多练几种遇到新题时就能快速选择最合适的方案。另外UVA 的题目普遍注重细节和边界这是很好的训练。很多人刷题只追求数量忽略了质量。我的做法是每道题做完后写一段简短的总结记录这道题的核心思路、踩过的坑、学到的技巧。积累下来就是一份属于自己的经验库。下次遇到类似的题翻一翻总结往往能少走很多弯路。最后分享一个小技巧如果你在本地测试通过但提交 WA先检查输出格式再检查边界条件最后才怀疑算法。根据我的经验UVA 题目里因为输出格式和边界条件导致的 WA比算法错误多得多。把这两项检查做到位通过率会明显提升。