第8周：第五次上机课（详细讲义）

课堂版 · 详细讲义 · py 作业 6 · OJ 题集

一、二维列表

04 · 矩阵换行求边缘和

原题 · 知识点： 二维列表、下标、交换、逻辑或。

处理步骤

1. 读入行数 m、列数 n，逐行建立矩阵，每一行都是独立列表。
2. 将输入行号 x、y 减 1，交换对应的两个行列表。
3. 遍历每个位置 (i,j)；如果 i 是首尾行，或 j 是首尾列，则累加一次。
4. 输出交换后的边缘和。

手工推演与方法对照

样例中第 1、2 行交换后，三行分别是 [3,7,1]、[3,4,1]、[2,0,1]。边缘按行累计为 11 + 4 + 3 = 18。

也可以先加首尾行，再加中间行的左右两端。但这种方法要单独处理只有一行或一列的情况。逐格判断边缘条件更统一，时间复杂度为 O(mn)。

自查： 只有一行 [2,3,4] 得 9；只有一列 [2,3,4] 也得 9；只有一个格子值为 7 时得 7。交换同一行不改变结果。先求和再交换会漏掉换行对边缘的影响。

05 · 图像模糊处理

原题 · 知识点： 二维列表、独立副本、邻域访问、舍入。

处理步骤

1. 读入原图，为输出图逐行复制列表。
2. 行下标只遍历 1 到 n-2，列下标只遍历 1 到 m-2。
3. 从原图取中心及上下左右五个整数，求和除以 5，舍入后写入输出图。
4. 输出整张新图，边缘保持原值。

为什么不能原地更新

OJ 样例第 2 行第 2 列的原值是 100，新值是 (100+0+50+50+200)/5=80。

接着算第 2 行第 3 列，必须仍用原来的左邻居 100：(200+100+100+100+0)/5=100。如果读到了刚写进去的 80，就会误算成 96。

每个值只由原图决定，因此更新方向不应影响结果。若从左到右和从右到左算出不同答案，就应检查是否覆盖了输入。

复制和舍入

result = image 不复制；result = image[:] 只复制外层。对整数矩阵，[row[:] for row in image] 能让每行独立。

五个整数的和除以 5，小数部分只可能是 .0、.2、.4、.6、.8，不会出现恰好 .5 的情形，因此此题可以用 round(total / 5)，无需纠结恰好一半的舍入规则。total // 5 则会错误地把 .6、.8 向下截断。

自查： 全部像素相同，处理后不变；没有内部点时原样输出；一个中心点的新值只看五个位置。时间复杂度 O(nm)，新图占用 O(nm) 空间。

二、排序与区间

07 · 小鹿的工作和休息时间

原题 · 知识点： 区间排序、扫描合并、最大值与并列处理。

处理步骤

1. 用二元组保存委托人的空闲区间，按起点升序排列。
2. 用当前段 [start,end] 接住第一段。后续区间起点 a <= end 时，合并并令 end = max(end,b)；否则当前段已经结束，记录它并开启新段。
3. 扫描结束后别漏记最后一段。在所有合并段中选长度最大的，长度相同选起点最早的。
4. 先输出选中的工作段 [s,e]。若 l < s，输出休息段 [l,s]；若 e < r，输出 [e,r]。

为什么先合并再比较

同一段连续覆盖的时间里可以衔接委托；遇到真正的空隙，就不能继续同一段工作。端点相接没有休息间隙，因此也要合并。

样例 1 中 [1,5]、[5,6]、[6,9]、[8,10]、[9,10] 连成 [1,10]，剩下 [10,15] 休息。

样例 2 合并为 [1,4]、[6,10]，比较的是长度 3 和 4，选后者。无需枚举见面顺序，也不是挑选最多个互不重叠的区间。

边界与易错点

• [1,8] 后接 [2,3]：右端点仍为 8，不能被覆盖成 3。
• [1,3]、[3,5]：合成 [1,5]，条件使用 <=。
• [1,4]、[6,9]：长度同为 3，保留较早的 [1,4]。按起点顺序扫描时，只在长度严格增大时替换最优段。
• 工作覆盖整个清醒区间时，没有正长度休息段，不输出 l l 或 r r。

题面没有详细说明无委托或委托完全落在清醒时间外的输出约定，不据此编造答案。理解题意时应把工作限制在清醒时间内；若做通用实现，可先将区间与 [l,r] 取交集，再处理有效区间。

排序占 O(n log n)，合并扫描占 O(n)。

三、字典统计

09 · 单词出现频率统计

原题 · 知识点： EOF 输入、字典计数、多关键字排序。

处理步骤

逐行读取到 EOF，以单词为键，将出现次数加 1；统计完成后对 (单词, 次数) 排序，按“次数降序、词典序升序”输出。

排序键怎么写

key=lambda item: (-item[1], item[0])

元组从左往右比较。次数越大，负数越小，就越靠前；次数相同时再比较单词。不能把单词放在第一个关键字，也不能对两个关键字统一倒序。

about、send、about、me 汇总为 about:2、send:1、me:1，结果为 2 about、1 me、1 send。

自查： 输入只有一种词时只输出一行；所有词都只出现一次时按词典序排列。首行也是单词，不能按数量读取。设总词数为 N、不同单词数为 K，统计约 O(N)，排序 O(K log K)；避免对每个词重复扫描整份输入。

10 · 网站网页访问统计

原题 · 知识点： 函数、字符串拆分、字典累加、最大值。

处理步骤

1. 写时间转换函数，用 split(':') 拆分，转成整数并返回 h*3600+m*60+s。
2. 读记录条数，再逐条拆出网页名、开始时间、结束时间。
3. 本次时长为结束秒数减开始秒数，累加到网页对应的值。
4. 全部记录完成后，选择累计值最大的网页并输出名字。

用样例区分“单次最长”和“累计最长”

网页	时长（秒）
index.html	6 + 183 = 189
study.html	185
teachers.html	122

单次最长的是 study.html，累计最长却是 index.html，应输出后者。字典更新要在旧值上加本次时长，直接赋值会丢掉之前的访问。

自查： 同一网页多条记录、跨分钟或跨小时、起止相同的零秒记录。题目不考虑跨午夜，不能无条件加 24 小时。题面没有规定累计时长并列时的规则，不把自行选择的规则当成题目要求。只求最大值无需排序，整体时间约为 O(N)。

11 · 单词打分（提高版）

原题 · 知识点： 字典分组、聚合信息、平均值、保留关联记录。

处理步骤

1. 读取人数 n，再读取 n*10 条记录。
2. 每个单词保存总分、评分次数、评分人 id 列表；处理一条记录，就加分、加次数、追加 id。
3. 汇总完成后比较平均分 总分 / 次数，选择最小的词。只遍历实际收到评分的词。
4. 第一行输出单词；第二行按记录顺序用空格分隔评分人 id。

为什么不直接保存不断更新的平均值

评分为 2、8、8 时，真实平均分是 (2+8+8)/3=6。先求前两次平均得到 5，再求 (5+8)/2=6.5，相当于错误地给最后一个人更大的权重。

保存总分和次数最直观。比较前不要把平均分取整或保留一位小数，以免把不同的平均分变成相同值。也可用交叉相乘比较两词平均分：比较 sum_a * count_b 与 sum_b * count_a。

输出与数据组织

可以用一个字典，把每个词映射到包含三类信息的记录；也可以使用三个字典，分别保存总分、次数和 id 列表。关键是三个结构都使用相同的单词作键。

OJ 样例最简单的词为 gate，评分人是 2 5。题面保证最简单的单词唯一，但没有另行要求 id 排序；按输入顺序保留，不擅自增加排序规则。

自查： 只出现一次的词也要参与比较；最低总分不一定有最低平均分；输出的是评分人 id，不是评分分数，也不是评分条数。记录总数为 10n，一次汇总再遍历不同单词即可。