最近逛泥潭感觉令人焦虑的帖子越来越多，于是我打算开个轻松愉快的话题来庆祝摸鱼人节（April Fish Day）。刚好距离我上次在泥潭讲题过去了一年，不如借此机会来推荐一些比较有趣（i.e., not LeetCode）的编程练习题吧，难度希望是学完 CS2 的同学能在 20 分钟左右搞掂。每道题我都会给出解题思路和参考代码，no intimidation 
如果潭友们有好的题解愿意分享，也欢迎在楼下回复，众人拾柴火焰高嘛 
本楼内容为水老师独家回馈泥潭所作，请勿转出美卡论坛，谢谢！
既然是摸鱼人节，首先有请 @打豆豆 老师镇楼 
准备工作：Kattis
如果你打算提交代码进行评测的话，需要在 Kattis 上注册一个账号。这是个完全免费的平台，不需要提供信用卡，也没有广告（i.e., 没有什么羊毛可薅 ）。
与 LeetCode 不同的是，Kattis 上的所有题目都是通过标准输入/输出进行交互的。也就是说，你需要提供完整的程序从 stdin 读取输入数据，并将答案输出至 stdout，而不是像 LeetCode 那样只要实现一个函数就行。如果你是第一次使用 Kattis 的话，建议先试一下这道热身题，熟悉一下平台环境。
Frosting on the Cake
今天我要推荐的是 2017 年 ICPC Southwestern Europe Regional Contest 中的一道题目——Frosting on the Cake（不要慌，区域赛的题目往往都很简单）。题目描述如下：
Kattis 链接在此，感兴趣的潭友们不妨一试：
解题思路
这道题最简单粗暴的方法必然是把 n² 个格子的面积全都计算一遍再都加起来。不过很不幸，O(n²) 的时间复杂度必然超时了。但只要稍微观察一下就不难发现，如果我们调整一下每行或每列颜色的排列顺序，其实并不影响每种颜色的总面积。所以我们完全可以把所有 A₁, A₄, A₇…这些列挪到蛋糕的最左侧，把 A₂, A₅, A₈…这些列挪到蛋糕中间，再把 A₃, A₆, A₉…这些列挪到蛋糕的最右侧，这样 n 小列就合并成 3 大列了。同理，我们也可以把所有 B₁, B₄, B₇…这些行挪到蛋糕的最上面，把 B₂, B₅, B₈…这些列挪到蛋糕中间，再把 B₃, B₆, B₉…这些列挪到蛋糕的最下面，这样 n 小行就合并成 3 大行了。于是我们得到了九个大矩形：
| 白 | 橙 | 粉 |
| 橙 | 粉 | 白 |
| 粉 | 白 | 橙 |
也就是说，我们只需要把长和宽两个方向每段的长度按照 mod 3 的余数分类求和，就可以得到这三大行、三大列的长度，然后算九次乘法计算出九个大矩形的面积就行了。每种颜色的总面积就是三个大矩形面积的和。总的时间复杂度只要 O(n)。
参考代码
既然是轻松愉快导向，代码就用 Python 写咯。尽管原题的下标是 1-based，我为了偷懒就用 0-based 下标来计算了，只要别把颜色搞混就好
def read_ints():
return [int(x) for x in input().split()]
def partition(x):
return [sum(x[i::3]) for i in range(3)]
if __name__ == "__main__":
n = int(input())
a = partition(read_ints())
b = partition(read_ints())
print(
a[1] * b[0] + a[0] * b[1] + a[2] * b[2],
a[2] * b[0] + a[1] * b[1] + a[0] * b[2],
a[0] * b[0] + a[2] * b[1] + a[1] * b[2],
)
今天先到这儿，以后视心情不定期更新[1]……祝大家摸鱼愉快！
Stamp Combinations
Pizza Party!
Stacking Up
MrCodeFormatGrader
Alien Integers
Free Weights
Prehistoric Programs
SLA Tomography
Walking on Sunshine
也可能直接烂尾 ↩︎
