【4/1/26 更新第12题】摸鱼人节（April Fish Day）一周年，推荐一些有趣但不难的编程练习题（不是 LeetCode）

最近逛泥潭感觉令人焦虑的帖子越来越多，于是我打算开个轻松愉快的话题来庆祝摸鱼人节（April Fish Day）。刚好距离我上次在泥潭讲题过去了一年，不如借此机会来推荐一些比较有趣（i.e., not LeetCode）的编程练习题吧，难度希望是学完 CS2 的同学能在 20 分钟左右搞掂。每道题我都会给出解题思路和参考代码，no intimidation

如果潭友们有好的题解愿意分享，也欢迎在楼下回复，众人拾柴火焰高嘛

本楼内容为水老师独家回馈泥潭所作，请勿转出美卡论坛，谢谢！

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{red}\,水老师小课堂\,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

既然是摸鱼人节，首先有请 @打豆豆 老师镇楼

@打豆豆

2026真的不上泥潭了！

2023 年4 月 7 日加入

准备工作：Kattis

如果你打算提交代码进行评测的话，需要在 Kattis 上注册一个账号。这是个完全免费的平台，不需要提供信用卡，也没有广告（i.e., 没有什么羊毛可薅 ）。

与 LeetCode 不同的是，Kattis 上的所有题目都是通过标准输入/输出进行交互的。也就是说，你需要提供完整的程序从 stdin 读取输入数据，并将答案输出至 stdout，而不是像 LeetCode 那样只要实现一个函数就行。如果你是第一次使用 Kattis 的话，建议先试一下这道热身题，熟悉一下平台环境。
Frosting on the Cake

今天我要推荐的是 2017 年 ICPC Southwestern Europe Regional Contest 中的一道题目——Frosting on the Cake（不要慌，区域赛的题目往往都很简单）。题目描述如下：

image1310×1650 261 KB

image1310×720 12.8 KB

Kattis 链接在此，感兴趣的潭友们不妨一试：

open.kattis.com

Frosting on the Cake – Kattis, 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
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
俗话说得好：只要你想摸鱼，每天都是 April Fish Day。周五的夜晚，何不来做个题呢？那一盏盏小绿灯 ，都在为你鼓掌呢！没什么能比这带来更多的多巴胺了
[image]
今天的题目选自 2021 年 ICPC North America Qualifier，题目叫做 Stamp Combinations …
Pizza Party!
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
又到周末了！为了庆祝隔壁摸鱼三号楼开业，咱们来开个 Pizza Party 吧
今天的题目还是选自 2021 年 ICPC North America Qualifier，题目就叫 Pizza Party!
[image]
[image]
Kattis 链接：Pizza Party! – Kattis, Kattis
解题思路
参考…
Stacking Up
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
潭友们周五好！如果早上好是 Good morning，晚上好是 Good evening，那么周五好便是 Good Friday 了
据说在某些地区 Good Friday 要吃 pancake，那么今天就来一道和 pancake 有关的题目（依然选自 2021 年 ICPC North America Qualifier）——Stacking Up …
MrCodeFormatGrader
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
国际劳动节快乐！劳动节就应该让机器劳动，人类休息。那么今天的题目就是要让机器劳动啦——MrCodeFormatGrader（又是来自 2021 年 ICPC North America Qualifier，因为我懒 ）
[image]
[image]
Kattis 链接：MrCodeFormatGrader – Kattis, Kattis
解题思路
参考…
Alien Integers
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
今天是 5/5/25，而且 2025 也是个完全平方数。那么——平方根日快乐！
为了庆祝这个每个世纪只有九次的节日，今天来一道跟数字相关的题目吧——Alien Integers（还是来自 2021 年 ICPC North America Qualifier ）
[image]
Kattis 链接：Alien Integers – Kattis, Kattis
解题思…
Free Weights
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
在开始今天的题目之前，让我们先来庆祝一下水老师连续三次抢到摸鱼楼二楼
居然又抢到二楼了 欢迎跟我一起来做题呀～
大家好呀！今晚真热闹～
除了摸鱼四号楼开张之外，今天泥潭的头等大事应该是茶色撸卡杀全家了吧。没关系，卡撸不成不要紧，还可以撸别的嘛，比如说撸铁和撸题都是很好的选择，甚至可以边撸铁边撸题，例如这道来自 2016 年 ICPC …
Prehistoric Programs
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
这周是很多学校的 finals week，那么咱们也来个 finals 的题目吧，我是说，第 45 届 ICPC World Finals，题目叫做 Prehistoric Programs
[image]
[image]
Kattis 链接：Prehistoric Programs – Kattis, Kattis
解题思路
参考代码
SLA Tomography
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
Memorial Day 快乐！今天其实也是 2025 年 ICPC North America Championship 的日子，那我们不妨一起来做一下刚刚结束的这场比赛的签到题——SLA Tomography
[image]
[image]
[image]
Kattis 链接：SLA Tomography – Kattis, Kattis
解题思路
参考代码
Walking on Sunshine
【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
潭友们新学年快乐！过了一个暑假，大家有没有晒黑呢？
在上周四刚刚结束的第 49 届 ICPC World Finals 中就有一道关于防晒的问题——Walking on Sunshine
[image]
[image]
Kattis 链接：Walking on Sunshine – Kattis, Kattis
解题思路
参考代码
也可能直接烂尾 ↩︎

【引用自 aqua】:
摸鱼人节（April Fish Day）
woc

这个好像是水姐原创的? 厉害

also 我题目读了几句已经睡了, 赶紧退出thread

看别的帖子我没焦虑，让我做题我已经开始焦虑了

【引用自 aqua】:
就不难发现
众所周知，焦虑了

疯了，都疯了

摸鱼……做题？

题看不懂
【引用自 aqua】:
令人焦虑
我是愚人

我过节

水老师我不想努力了

怕不是今天最大的一个joke

【引用自 aqua】:
CS2
对不起但是我真的以为CS2是 CS2

我就想知道是不是培训小水的时候顺便培训坛友

小水几岁了开始做题了

早上睡醒想摸个鱼结果更焦虑了

深感这份工作就是我最后一份工作了

【引用自 divinebaboon】:
also 我题目读了几句已经睡了, 赶紧退出thread
+10086

题目倒不难，对3同余的A/B可以合并，扫一遍之后就变成3*3的组合

还是acm的题做起来有意思，lc都太直给了

【引用自 aqua】:
在上班，不刷泥潭。
在这个帖子下很难不引用 @打豆豆 的签名

终于看到一个来做题的了！

做题家本能发动了属于是

敲碗等水姐更新

上着班摸着鱼被人踹了一脚

我错了水姐，我再也不传播焦虑了

能别让我再刷泥潭的时候还做题吗

看完题了，有一种ACM的脑经急转弯的美，让我想起来以前打数学竞赛的美丽时光

lc的题目确实直给，但是lc全是这种acm形式的题目，面试的时候很容易就出现要是没见过一个字都写不出来的尴尬境遇，只能说lc还是更有规律一点（

我也来提供一个问题

implement一个blackjack游戏的optimal bot

还好钻老师根本不会编程

不好意思啊……过节了主打一个轻松愉快嘛，咱们做题是为了陶冶情操不是为了面试

脑筋急转弯爱看，希望还有续集

开面试辅导班吗？第一个报名

哈哈哈哈，仅供娱乐，请勿当真

水姐是OIer/ACMer？

晚上了，这东西应该挺助眠的。

BSVG就是不一般啊

【引用自 divinebaboon】:
我题目读了几句已经睡了
俺也一样！

想了半天才反应过来是五笔……你走开

水姐除了长的不像别的都太像我第一个女朋友了。希望水姐不是福州人。

那我可以确定不是

你是北大的？

支持，今天我就把这个做了

【引用自 uscreditcardguide】:
欢迎来到美卡论坛&本论坛版规
禁止人肉坛友、谈论坛友的个人信息

水妈竟然是姚班的，我的慕强症又犯了捏

姚班有水老师，是姚班的荣幸

竟然是真实头像

有没有人测试一下是我的问题吗还是这题c++的test case有问题

没问题呀……你是不是用了 int

没有新题吗？ 我以为是一天一题。。。这个楼也摸鱼吗

坏了 8年以后又被同样的问题卡住了

【引用自 未知】:
【摸鱼第二季完结】四月处于放弃边缘，如何进入工作状态。 搬砖
感谢二位关注！要不今天再来道新题吧
俗话说得好：只要你想摸鱼，每天都是 April Fish Day。周五的夜晚，何不来做个题呢？那一盏盏小绿灯 ，都在为你鼓掌呢！没什么能比这带来更多的多巴胺了

image1210×170 11.4 KB

今天的题目选自 2021 年 ICPC North America Qualifier，题目叫做 Stamp Combinations

image1040×950 220 KB

image1040×270 5.63 KB

image1040×420 30.8 KB

Kattis 链接：Stamp Combinations – Kattis, Kattis

解题思路

这又是一道看起来很容易，但暴力做法会超时的题目。但其实只要稍加提示，方法应该不难想到。

提示

这道题的关键在于邮票不能乱撕，而是只能从两端连续撕取。你想到了什么？

方法一

对数据结构比较敏感的潭友们应该这时候能想到 prefix sum 了。没错，这道题的描述就是典型的为了一盘醋包了一碟饺子。如果我们抛开饺子只看醋的话，其实一句话就能讲清楚：

给定一组整数，请问是否存在一段 prefix sum 和一段 suffix sum 相加等于 q ？

讲到这儿基本上应该懂的都懂了。

如果你还不懂，请听我继续分解……

预处理计算 prefix sum 或 suffix sum 只需要 O(m) 的时间。但问题是，如何找到一段 prefix sum 和一段 suffix sum 相加等于 q 呢？如果两两组合全都试验一遍的话，O(m²) 又超时了。但其实

image1920×1080 85.9 KB

假设我们已经通过预处理计算并保存下来了所有的 prefix sum，那么对每一段 suffix sum s，我们只需要判断 (q – s) 是不是某个已经计算好的 prefix sum 就行了。有人可能会问，在众多 prefix sum 当中找到我们想要的 (q – s) 难道不需要 O(m) 的时间么？当然不用啦 因为 prefix sum 一定是单调递增的，所以这里可以做 binary search，只要 O(logm) 的时间就够了。或者也可以一上来就把所有的 prefix sum 存在一个 hash set 里，这样每次只要从 hash set 当中查找 (q – s) 就好了。如果认为在 hash set 当中查找一个值的时间复杂度是 O(1) 的话，这个方法总的时间复杂度就是 O(mn) 的，在 10⁷ 的数据范围内毫无压力。

方法二

其实这道题还有另一种思路，也许更简单……如果从两端撕取邮票不容易思考的话，我们可以反其道而行之，想想中间还剩多少邮票——这部分一定是连续的。

换句话说，假如全部邮票总共有 T 张的话，只要我们找到一段 subarray sum 等于 (T – q) 就大功告成了。

讲到这儿又应该是懂的都懂了，因为如何在数组中找到某个特定的 subarray sum 算是经典方法了。

如果你还不懂，请听我继续分解……

这个方法就是 sliding window……我们把一个窗口从左往右滑动，一边滑一边计算窗口内的邮票数。具体怎么滑呢？

初始时，窗口的起点和终点都在数组的最左侧，窗口内的邮票数 s = 0。
如果当前窗口内的邮票数小于 (T – q)，我们就扩大窗口，也就是把窗口的终点右移一位，并把新进入窗口的值加到 s。
如果当前窗口内的邮票数大于 (T – q)，我们就缩小窗口，也就是把窗口的起点右移一位，并把刚刚离开窗口的值从 s 中减掉。
重复这个过程，直到当前窗口内的邮票数刚好等于 (T – q)，那么大功告成；或者窗口扩大到超过了数组最右侧，这时我们就知道此题无解了。

这个方法的时间复杂度也是 O(mn) 的。

避坑指南

两种方法都不难实现，但边界情况还需小心，比如 q = 0 或是超过了邮票总数的情况。

参考代码

方法一
m, n = map(int, input().split())
a = [int(x) for x in input().split()]

prefix_sums = {0}
total = 0
for i in a:
total += i
prefix_sums.add(total)

a.reverse()
for _ in range(n):
q = int(input())
if q > total:
print("No")
elif q in prefix_sums:
print("Yes")
else:
s = 0
for i in a:
s += i
if s > q:
print("No")
break
if q - s in prefix_sums:
print("Yes")
break

方法二
m, n = map(int, input().split())
a = [int(x) for x in input().split()]

length = len(a)
total = sum(a)

for _ in range(n):
q = int(input())
target = total - q
if target < 0:
print("No")
continue
start = end = s = 0
while True:
if s == target:
print("Yes")
break
if s < target:
if end == length:
print("No")
break
s += a[end]
end += 1
else:
s -= a[start]
start += 1

【引用自 aqua】:
周五的夜晚
【引用自 aqua】:
何不
为爱
【引用自 aqua】:
鼓掌呢
zs

一眼前缀和

请叫我爆零大王

image2298×1193 138 KB

我还担心这些题太简单你们看不上眼

我可是在弱省noip拿过一次三等奖的泥潭认证著名智障

难受 开始想了半天还是不会

@先别急 再想想～

解题思路里有多层提示你可以点开看，不会直接爆答案

如果去掉n*m <= 1e7（开始没看到）

好像我确实不太会

已经给我逼急到想怎么利用a_i <= 100去背包了

去掉限制就没法做了……数据范围是有意义的

大半夜做题会睡不着觉的

大半夜手慢无捶胸顿足更睡不着觉

那东西我不需要

睡觉

真的给我逼急到想歪脑筋了

前缀和 后缀和 然后FFT 1e8再乘log 想不超时也难

怎么说呢，WA瞪眼调试了快一个小时才看出什么问题来

我是SB

image2305×777 41.3 KB

亲，这边已经为您准备好了
【引用自 aqua】:
避坑指南

我想到了，但是条件写错了

本智障高中的时候都不知道
【引用自 ATF】:
oi
这回事

不知道好，高中是谈甜甜的恋爱的年纪，我机房扣脚做题太失败了

羡慕高中就进机房

【引用自 anhpp】:
羡慕高中就进机房
羡慕高中就进机房

+1

怎么高中还有电脑的

只听说过数理化竞赛但那也是省城大高中搞的

oi没听说过

谢谢水老师！

两题都不错， 请继续！

谢谢水老师！

两题都不错， 请继续！

看到楼上几位的发言不禁想起高中电竞（我们叫信竞这个名字）大佬之间的互吹

神犇，%%%%%%%

对味了，还有各种膜的表情包

被水姐点赞了，受宠若惊

【引用自 CatGPT】:
看到楼上几位的发言不禁想起高中电竞（我们叫信竞这个名字）大佬之间的互吹
看到楼上的发言不禁想起高中自己没有学习过信竞的悲哀了

其实大部分人都在机房打dota

？不是东方吗

完了，代沟了

手残党实在玩不来

可以听音乐啊

别提了，都过了二十年了东方永夜抄第一关的 BGM 我还是一闭眼就能哼出来……不知道死了多少遍

那这个视频更适合你了，直接把解法用rap的形式表演给你看

小时候玩雷电还以为这种游戏有点儿可玩性。。。

上大学了看同学打东方 我认清了 这种游戏绝对没意思！

然後還是有些人在追求ノーミス ノーボム フルスペカ

【引用自 samgg】:
ノーミス ノーボム フルスペカ
image576×256 18.6 KB

日语的完全不理解

说到理解 我就想起来 不如我们还是来讨论平和吧

image400×139 38.1 KB

【引用自 aqua】:
如果认为在 hash set 当中查找一个值的时间复杂度是 O(1) 的话，这个方法总的时间复杂度就是 O(mn) 的，在 10⁷ 的数据范围内毫无压力。
也可以在pre和post上用两数之和 稳定O(m) 不过这个就跟下面的双指针本质相同了

又到周末了！为了庆祝隔壁摸鱼三号楼开业，咱们来开个 Pizza Party 吧
【引用自 未知】:
【摸鱼第三季完结】卷起还是躺下，大家都要自洽。 搬砖
居然又抢到二楼了 欢迎跟我一起来做题呀～
今天的题目还是选自 2021 年 ICPC North America Qualifier，题目就叫 Pizza Party!

image1040×1280 173 KB

image1040×730 24 KB

Kattis 链接：Pizza Party! – Kattis, Kattis

解题思路

这道题其实就是需要根据一系列已知条件进行逻辑推理。我们可以把输入的条件分为三类——必选食材、合取条件和析取条件，并把每个条件的前提和结论都保存下来。

数据结构小贴士

必选食材可以保存为一个列表。
每个条件的前提和结论可以保存为一个二元组。
为了避免重复，我们可以用集合来保存前提当中的各种食材。这样在后续逻辑推理过程中，一旦某种食材被选取，我们便可以将其从集合中删除。

读完全部输入数据之后便可以进行逻辑推理了，推理的过程就是不断检查各个条件的前提是否已经满足，一旦满足就将其结论加入必选食材。具体操作方法如下：

外层循环逐个分析必选食材列表中的每种食材……

内层循环检查每个条件……

如果当前食材不在这个条件的前提当中，那么这个条件雨女无瓜，直接跳过。
否则，我们将当前食材从这个条件的前提集合中删除。然后

对于合取条件，如果此时前提集合刚好被删光了，我们便可以将其结论添加到必选食材列表的末尾。
对于析取条件，我们可以直接将其结论添加到必选食材列表的末尾。

最后，输出必选食材列表中不同食材的总数即可。

参考代码
absolute_toppings = []
and_conditionals = []
or_conditionals = []

c = int(input())
for _ in range(c):
s = input()
if s.startswith("if "):
antecedents, consequent = s[3:].split(" then ")
if " and " in s:
and_conditionals.append((set(antecedents.split(" and ")), consequent))
else:
or_conditionals.append((set(antecedents.split(" or ")), consequent))
else:
absolute_toppings.append(s)

for topping in absolute_toppings:
for antecedents, consequent in and_conditionals:
if topping in antecedents:
antecedents.remove(topping)
if not antecedents:
absolute_toppings.append(consequent)
for antecedents, consequent in or_conditionals:
if topping in antecedents:
antecedents.remove(topping)
absolute_toppings.append(consequent)

print(len(set(absolute_toppings)))

不懂编程，捧个人场吧

感觉这题是最简单的。。。不需要什么奇技淫巧/数学直觉

写写看哦，代码可能没有想象中那么简单～

这么长的题目，看都不想看

完蛋了，本科计程设的大作业还是去答疑坊给我重写的，现在啥都看不懂了

哎 看了一眼好烦啊 非得把题绕一圈 字符串先处理一下 他们预选赛出这题的时候不会觉得有人喜欢吧。。。

【引用自 anhpp】:
字符串先处理一下
所以要用 Python

不行 我是有坚持的

Since you are paying by the topping, the conference organizers wish to find the minimal set of satisfying toppings for each table’s pizza.

怎么一股 graph theory 的味道

不是味道 虽然也没啥theory 就是纯graph吧

太卷了！ 周末还要刷题 @aqua

我是很忍不住用AI直接做题的。python好就好在各路LLM训练集里python代码最多，让AI写代码用python更容易写对。

这字符串parse看着就恶心

image440×208 18.2 KB

“打人不打脸，骂人不骂短！”

我才意识到上周讨论解题是在摸鱼楼不是在这里，怪不得这儿这么冷清……

好想把帖子都挪过来

不懂编程

只会上班的路过

我把题发我哥们他3分钟就秒了 卷不过

image581×199 26.4 KB

can can need

写一半研究OTA飞机票去了 现在继续

image1217×146 9.55 KB
c = int(input())

ands = []
ors = []
ans = set()

for i in range(c):
line = input()
w = line.split()

if w[0] == "if":
t = set()

for i in range(1, len(w) - 1, 2):
t.add(w[i])

if "and" in line:
ands.append((set(t), w[-1]))
else:
ors.append((set(t), w[-1]))

continue

ans.add(line)

prev = -1

while prev != len(ans):
prev = len(ans)

for req, res in ors:
if res in ans:
continue

ok = False

for r in req:
if r in ans:
ok = True
break

if ok:
ans.add(res)

for req, res in ands:
if res in ans:
continue

ok = True

for r in req:
if r not in ans:
ok = False
break

if ok:
ans.add(res)

print(len(ans))

既然 parse 恶心就不parse了

py很简洁

image1892×205 4.81 KB

java可真烦人啊 而且还没快 我看看你们怎么写的

一点做题的欲望都没有

感觉这辈子别想跳槽了

我当年是通过这门公开课发现kattis的：GitHub - SuprDewd/T-414-AFLV: T-414-ÁFLV: A Competitive Programming Course

这是我能想到最sb最暴力的做法了，居然都能AC

，看来是签到题
n = input()
n = int(n)
已选食材 = set()
与条件: list[tuple[tuple[str], str]] = []
或条件: list[tuple[tuple[str], str]] = []
就条件: list[tuple[str, str]] = []
for i in range(n):
食材 = input()
if "then" not in 食材:
已选食材.add(食材)
else:
食材列表 = 食材.split()
if "and" in 食材列表:
过滤后的食材列表 = [食 for 食 in 食材列表 if 食 not in ("and", "if", "then")]
与条件.append((tuple(过滤后的食材列表[:-1]), 过滤后的食材列表[-1]))
elif "or" in 食材列表:
过滤后的食材列表 = [食 for 食 in 食材列表 if 食 not in ("or", "if", "then")]
或条件.append((tuple(过滤后的食材列表[:-1]), 过滤后的食材列表[-1]))
else:
就条件.append((食材列表[1], 食材列表[-1]))
本轮已更新 = True
while 本轮已更新:
本轮已更新 = False
余下的食材条件列表 = []
for 如果有, 就包括 in 就条件:
if 如果有 in 已选食材:
已选食材.add(就包括)
本轮已更新 = True
else:
余下的食材条件列表.append((如果有, 就包括))
就条件 = 余下的食材条件列表
余下的食材条件列表 = []
for 如果有, 就包括 in 或条件:
if any(map(lambda x: x in 已选食材, 如果有)):
已选食材.add(就包括)
本轮已更新 = True
else:
余下的食材条件列表.append((如果有, 就包括))
或条件 = 余下的食材条件列表
余下的食材条件列表 = []
for 如果有, 就包括 in 与条件:
if all(map(lambda x: x in 已选食材, 如果有)):
已选食材.add(就包括)
本轮已更新 = True
else:
余下的食材条件列表.append((如果有, 就包括))
与条件 = 余下的食材条件列表
print(len(已选食材))

【引用自 未知】:
【5/16/25 更新第八题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
[image]
c = int(input())
ands = []
ors = []
ans = set()
line = input()
w = line.split()
t = set()
for i in range(1, len(w) - 1…
看了一下和我这个差不多

人家是中文

我还以为是 pseudo code 原来是中文编程

很符合 @ATF 的编程风格
【引用自 未知】:
NG找工投简历记录贴 搬砖
好久没见过反转链表了，不过曾经教过本科生数据结构，跟他们讲递归的一大要点是要让他们记住一开始在写递归的时候要假设自己的递归函数已经可以正常使用了，而这之后的正确性证明完全由当前步骤和边界条件决定。这点和归纳推理的步骤十分相似。
那么讲解递归解决反转链表就从这里开始：
假如当前处在边界条件，即链表只有一个元素，那么无需任何操作直接返回即可。
加入当前处在非边界条件，即链表有多个元素，
a. …

建议加入小学数学

x+y+z=1

x^2+y^2+z^2=1

求x^3+y^3+z^3的最小值

这真的是小学数学吗 记不得方法了

总结

不过假定一定对称性 x=y 应该能得到一个1/3*(2,2,-1) 结果是5/9看起来挺优 :doge

【引用自 咕的鹦鹉宁】:
求x^3+y^3+z^3的最小值
gradient descent给你搞一个出来

image541×800 72.2 KB

小学数学来了

还好这个是真的小学数学

你的答案隐藏一下

被看到了都没人做题了

我能想到的就是画个线分割成三角形 三角形和长方形然后用三角形的特性来求出长方形短的边长然后再把面积加起来

完了

你不如现在小学生

我只有小学文化 这么多年退化了肯定连小学生都不如了

为什么不是人类补完计划呢 补出一个完整的三角形

那也可以

【引用自 咕的鹦鹉宁】:
建议加入小学数学
你说这个我可就不困了

洛谷

P3951 [NOIP 2017 提高组] 小凯的疑惑

NOIP2017 提高组 D1T1

题目不错 大概猜想一下就是算一下Ax+By= ±1的结果 然后就知道A和B最多有几个了

这题智商高可以用朴素的exgcd推导，或者从小学课外读物找到答案；我这种智商低的就爆零

这题看了答案显得自己好蠢 虽然没错 但是蠢的要死。。。

我想的是 找到

x1 * a - y1 * b = 1

y2 * b - x2 * a = 1

显然当a至少有 x1个 或者b有y2个时 可以很朴素的继续减一。。。

但是我肯定是sb，两个相减 (x1 + x2) * a = (y1 + y2) * b

y1 + y2 不就等于a吗

所求的(x1 - 1) * a + ( y2 - 1) * b - 1 不就等于

(y1 * b + 1 - a) + y2 * b - b - 1 = (y1 + y2) * b - a - b = ab - a - b吗。。。

tql膜

考点在于45%直角三角形，两边相等。作个辅助线就可以啦

不错

你已经达到小学同等学力

【引用自 咕的鹦鹉宁】:
小学同等学力
image1421×911 146 KB

小升幼，启动！

得重回娘胎修行了

潭友们周五好！如果早上好是 Good morning，晚上好是 Good evening，那么周五好便是 Good Friday 了

据说在某些地区 Good Friday 要吃 pancake，那么今天就来一道和 pancake 有关的题目（依然选自 2021 年 ICPC North America Qualifier）——Stacking Up

image1220×1670 211 KB

image1220×810 49 KB

Kattis 链接：Stacking Up – Kattis, Kattis

解题思路

这是一道构造题，所以方法可能不唯一。如果你的方法和我不同，欢迎回复分享～

首先从最简单的情况入手——如果 stack 只有一个数字，很容易想到递归构造的方法：

先想再看

假设 s(x) 是构造出数字 x 的一系列 Stackulator 3000 指令，显然 s(1) = “1” 满足条件。对于大于 1 的数字，我们可以按照如下方式递归构造：

如果 x 是偶数，那么 s(x) = s(x/2) + “d+”
如果 x 是奇数，那么 s(x) = s((x-1)/2) + “d+1+”

一个数字解决了，多个数字怎么办？

这里唯一棘手的问题是每次加法运算都会导致 stack 下方的所有数字减一。所以我们为了构造 stack 中某个数字 x，需要统计出构造它上方的所有数字总共要进行多少次加法运算（假设为 k 次），然后故意构造出 x+k，这样就能抵消掉加法运算的影响了。

为了构造出整个 stack，我们反过来从上到下构造每个数字会比较容易一些，按照上面的方法一边构造一边统计用了多少次加法运算，最后把构造每个数字的指令从下到上连续输出即可。

由于递归构造 s(x) 的指令长度不会超过 4⋅log₂x，总的指令长度不会超过 4,000⋅log₂10⁶ = 80,000，满足题目要求。

参考代码
from functools import cache

@cache
def s(x):
if x == 1:
return "1", 0
instructions, count = s(x // 2)
if x % 2 == 0:
return instructions + "d+", count + 1
return instructions + "d+1+", count + 2

if __name__ == "__main__":
n = int(input())
xs = [int(x) for x in input().split()]
program = []
total = 0
for x in reversed(xs):
instructions, count = s(x + total)
program.append(instructions)
total += count
print("".join(reversed(program)))

看起来只要构造一个valid输入而没有其他限制

如果假设100000不是一个太严格的限制的话

想要输出n就只需要 1[d+]*(n/2) [1+] 就可以构造任意数字

然后想要输出 m n 则需要先 生成 (m + n/2) 再生成 n

但是问题是这么构造出来的序列有多长，感觉需要具体算一遍

可以做视频讲解吗 到时候可以都内

是这个思路，不过有个细节你想差了一点点

我草 这不我参加那届吗

我偷懒只从同一场比赛选题被发现了

确实，脑子里想着二进制结果写了个n/2

还是直接递归定义方便一点

fn x: ‘1’ if x == 1 else fn(x/2) + ‘d+’ if x % 2 == 0 else fn(x-1) + ‘1+’

相当于用了 log(n) 次+拿到最高位的1，加上除最高位的1之和一共2logn次

数据范围最大log(10^6) ~ 20 * 2 = 40 次加号，80个字符，写1000个数字绰绰有余

这题不对我胃口 就硬来

缺少这一道题
【引用自 ATF】:
你说这个我可就不困了
P3951 [NOIP 2017 提高组] 小凯的疑惑 - 洛谷
看完答案之后 那种Aha的感觉

你怎么还是白金会员

第二个贴子写不出来啊

昨天磨磨蹭蹭写到五六点 今天确实没精神头了

或者再熬 45 天……

啊哈哈哈 其实我很想写我回国的流水账的 控制不住的分享欲

但是每次打开google photos 图片太多了 又直接回床上趴着了

【引用自 anhpp】:
看完答案之后 那种Aha的感觉
在赛场上遇到这道题是D1T1 直接怀疑人生想要跳楼

image1309×152 10.1 KB

大概知道水姐是谁了

我超，看看盒

其实我没看懂你的答案，但是我的思路是这样

因为a, b互质，所以对于任意整数c，存在x * a + y * b = c （x, y可能为负）

观察到这个关系的通解是(x + k * b) * a + (y - k * a) * b = c （k为任意整数，可能为负）

那么c不能被凑出来if and only if (x + k * b) 和 (y - k * a) 无法同时非负

那么考虑0 <= (x + k * b) < b 并且 (y - k * a) < 0 的边界情况， 最大化c就是最大化(x + k * b)和(y - k * a)，前者最大可以取b - 1，后者最大可以取-1，所以答案是(b-1)*a+(-1)*b

en.wikipedia.org

Coin problem

In mathematics, the coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. T Th...

男上加男。

我趴在地上想了想，感觉这题是最脑筋急转弯的 是直接输出mn-n-m吗

我说这怎么那么眼熟，看到这题仿佛都闻到了竞赛训练教室的味道，原来小时候看华老的《数论导引》看见过

image2449×223 28.7 KB

是的，大概就是
#include "bits/stdc++.h"
int main(void) {
long a,b;
std::cin>>a>>b;
std::cout<< a * b - a - b;
return 0;
}

我超，看看盒

【引用自 aqua】:
不要慌，区域赛的题目往往都很简单
指NEERC和CERC吗？

反正我只选签到题就好了

我超，看看盒

有人做数学题么

已知函数

（1）当a=8，求f(x)的单调区间；

（2）对任意正数a，证明：1<f(x)<2．

这题太经典了我日

陶神仙经典作

有人做物理题么
【引用自 summitguy】:
看来AI对解初中物理题还是可以的
在一个高度为H的水瓶里装满水放在桌子上，从上到下共打5个孔，哪个孔喷射的水最远。最远的是多少，（不考虑其他外部环境，比如侧风等）

陶老师现在还出题吗

我记得以前出去培训听他讲课，他电脑里都是那种巨丑无比的自创组合题

不出了，年纪大了，现在最多审审题。而且江西也成全国卷了，空有一堆难题也发挥不出来了

cmo可能玄，各种区域比赛（东南赛、女奥啥的）还是能出的吧

那我猜·还是能的，毕竟是出题界的拉马努金

国际劳动节快乐！劳动节就应该让机器劳动，人类休息。那么今天的题目就是要让机器劳动啦——MrCodeFormatGrader（又是来自 2021 年 ICPC North America Qualifier，因为我懒 ）

image1040×1460 86.8 KB

image1040×260 10.4 KB

Kattis 链接：MrCodeFormatGrader – Kattis, Kattis

解题思路

这道题真的很 straightforward，只要细心就好了……

记录下来输入数据中每组连续行号的起止点（单一行号相当于起点 == 终点）
把这些起止点按照题目要求的方式输出
把它们的补集也按照题目要求的方式输出

参考代码
def fmt(pairs):
return " and".join(
", ".join(
map(lambda pair: str(pair[0]) if pair[0] == pair[1] else f"{pair[0]}-{pair[1]}", pairs)
).rsplit(",", 1)
)

c, n = map(int, input().split())
errors = []
start = end = 0
for cur in map(int, input().split()):
if cur - end != 1:
if start != 0 or end != 0:
errors.append((max(start, 1), end))
start = cur
end = cur
errors.append((max(start, 1), end))
print("Errors:", fmt(errors))

corrects = []
start = 1
for error in errors:
if start < error[0]:
corrects.append((start, error[0] - 1))
start = error[1] + 1
if start <= c:
corrects.append((start, c))
print("Correct:", fmt(corrects))

这属于签到题么，感觉完全不需要算法

没错
【引用自 aqua】:
这道题真的很 straightforward
但
【引用自 aqua】:
只要细心就好了
还真不是那么容易一遍 bug-free

前有Pxrnhxb 教高数，现有美卡 教编程

帮你 @Pornhub

应该没有数据太多需要stream之类的情况吧…那就好像还好

但是要一次写对真不容易，像我肯定会把最后那个and漏掉

数据量不是问题，就是个签到题，拼手速

北美赛区，曾经就算练习这个赛区都会被当成浪费时间

【引用自 Vincent1】:
有Pxrnhxb 教高数
谢邀

其实ph是个很包容的平台 鼓励大家来发撸卡的视频

对呀，本来我起这楼是为了帮转码的同学推荐一些 LeetCode 之外的题目，结果发现来做题的都是竞赛选手

标题加上【理工科生勿入】

那就彻底没人了

加上男性勿入

不如直接关帖了

上周的呢

趁着没人发现
【引用自 aqua】:
【摸鱼第三季完结】卷起还是躺下，大家都要自洽。
悄悄烂尾

做得出来，但不知道是不是我用得太多列表推导式，去到最后一个测试用例出现超时
def group_num(data):
starts = [x for x in data if x-1 not in data and x+1 in data]
ends = [x for x in data if x-1 in data and x+1 not in data and x not in starts]
singles = [(x, x) for x in data if x-1 not in data and x+1 not in data]

return list(zip(starts, ends)) + singles

def int_to_str(data):
result = []
length = len(data)

for index, item in enumerate(data):
s = str(item[0]) if item[0] == item[1] else f"{item[0]}-{item[1]}"

if index < length - 2:
s += ','
elif index == length - 2:
s += ' and'

result.append(s)

return " ".join(result)

C = int(input().split(' ')[0])
errors = [int(x) for x in input().split(' ')]
correct = [x for x in range(1, C+1) if x not in errors]
print('Errors: ' + int_to_str(sorted(group_num(errors))))
print('Correct: ' + int_to_str(sorted(group_num(correct))))

【引用自 tobyma】:
if x not in errors
这里太慢了，应该用 set 而不是 list。改成这样就好了：
errors = set(int(x) for x in input().split(' '))
correct = set(x for x in range(1, C+1) if x not in errors)

对哦，反正里面的东西也不会有重复

受教了

我是有尊严的 这题我不写

【引用自 anhpp】:
尊严
想到当年和俩ioi金牌组队，这种题就是我写，给人创造输出条件

用点好玩的语言写

不算处理输入 haskell真的两分钟写好了

hof yyds

【引用自 RandomTrash】:
想到当年和俩ioi金牌组队
谁来开个盒

看到这楼我忽然想到自己好久没写c++，导致近N年的feature都不会。
【引用自 aqua】:
开个盒
。别开了别开了都被开完了放过我

还可以把每种语言试一遍

image3204×1272 439 KB

js竟然用的spidermonkey

怎么没有q

敢说哪年吗

我刚闲着试了下，发现ghc的groupBy行为是比较group里第一个element，我之前用的是一个库里的groupBy（比较adjacent）

如果不粘这种groupBy的definition的话，一下子也想不到啥优雅地办法写 用foldr写了一个，如果correct error都跑一遍的话最后一个case会TLE，最后还是挺乱的

下面这个是ac的

import Data.List (groupBy, intercalate, (\\))

ranges :: [Int] -> [(Int,Int)]
ranges = foldr aux []
where
aux x [] = [(x,x)]
aux x acc@((s,e):rest)
| x + 1 == s = (x,e):rest
| otherwise = (x,x):acc

correctRanges :: Int -> [(Int,Int)] -> [(Int,Int)]
correctRanges n errs = aux 1 errs
where
aux start []
| start <= n = [(start,n)]
| otherwise = []
aux start ((s,e):rs)
| start < s = (start,s-1) : aux (e+1) rs
| otherwise = aux (e+1) rs

fmt :: (Int,Int) -> String
fmt (x,y)
| x == y = show x
| otherwise = show x ++ "-" ++ show y

formatRanges :: [(Int,Int)] -> String
formatRanges rs = case map fmt rs of
[x] -> x
xs -> let initItems = init xs
lastItem = last xs
in intercalate ", " initItems ++ " and " ++ lastItem

main :: IO ()
main = do
[n, _] <- map read . words <$> getLine :: IO [Int]
errs <- map read . words <$> getLine :: IO [Int]

let errRanges = ranges errs
corrRanges = correctRanges n errRanges

putStrLn $ "Errors: " ++ formatRanges errRanges
putStrLn $ "Correct: " ++ formatRanges corrRanges

辣鸡ghc

need this

泥潭的majority都是IOI起跳么……

太可怕了

hrt一小时问我三道题+sys design

【引用自 ApplePay】:
这题hrt问过
啊 扑克牌机器人也能写的出来的吗 这也太夸张了

一次面试难道是一下午 不是一小时？

CERC 其实还行，你不提谁记得 NEERC 是区域赛啊 跟开火车差不多难度了都

sys design有点过分了 如果是ng的话

【引用自 ApplePay】:
如果是ng的话
intern，那会还大一刚开学

完全不敢。

我是一整天zs

羡慕哭了 人家花一整天时间来面你 也是花了大价钱的

其实我很好奇，像，，，，他们面试一个candidate的成本是多少？

【引用自 otonoco】:
成本是多少
engineering hour 面你的等级越高他们花得越多 面一轮他们就耗费一小时左右 好几轮 + debrief 如果真的要找到一个很满意的candidate其实不少钱

很难量化吧

太难统计简历多少份

多少个人能第一轮电话面试

多少个人走到了完整的虚拟onsite

这里其实是把面试官时薪折现来算的吧

但是像@打豆豆

本来也没在干活

多安排几个面试去干

也算物尽其用（

其实面试也是perf的一部分 我记得E4还是什么级别开始就要每年面多少个人了

是的 但是你如果面试了别人 又可以多划水半天了

原来如此

怪不得我的那些面试官都贼开心

一脸中奖了的表情

除了某些司马脸

【引用自 otonoco】:
怪不得我的那些面试官都贼开心
需要表演，否则会被投诉。

啊？原来还能投诉

那那些司马脸面试官早就该被我投诉到丢工作了

【引用自 otonoco】:
司马脸面试官
也许他们工作压力已经很大，或者不在升职track上。我是喜欢面试的；但很多人不喜欢，他们只是为了升职无短板

总之，面试也是一种表演形式，双方都是。

水老师是我的偶像

拖把哥好久不见

以后多跟水老师学做题

今天是 5/5/25，而且 2025 也是个完全平方数。那么——平方根日快乐！

为了庆祝这个每个世纪只有九次的节日，今天来一道跟数字相关的题目吧——Alien Integers（还是来自 2021 年 ICPC North America Qualifier ）

image1040×1340 235 KB

Kattis 链接：Alien Integers – Kattis, Kattis

解题思路

这道题没有任何算法上的难度，想清楚如何构造数字就好了。

参考代码
n = int(input())
digits = [int(digit) for digit in str(n)]
length = len(digits)
alien_digits = sorted(digit for digit in range(10) if digit not in digits)

if not alien_digits:
print("Impossible")
exit()

smaller_digits = [str(digit) for digit in alien_digits if 0 < digit < digits[0]]
bigger_digits = [str(digit) for digit in alien_digits if digit > digits[0]]

smallest_digit = str(alien_digits[0])
biggest_digit = str(alien_digits[-1])

prev_alien = smaller_digits[-1] + biggest_digit * (length - 1) if smaller_digits else biggest_digit * (length - 1)
next_alien = bigger_digits[0] + smallest_digit * (length - 1) if bigger_digits else smallest_digit * (length + 1)

if not prev_alien or int(prev_alien) == 0:
prev_alien = "0"

if int(next_alien) == 0:
next_alien = str(alien_digits[1]) + next_alien[1:] if len(alien_digits) > 1 else ""

if not next_alien or n - int(prev_alien) < int(next_alien) - n:
print(prev_alien)
elif n - int(prev_alien) > int(next_alien) - n:
print(next_alien)
else:
print(prev_alien, next_alien)

这题目里也没平方根啊 不自洽啊

牵强附会一下

红温了，一直 WA 14/55

想想如果输入是111，你会不会输出099。感觉这题没有第二种错法了

这题如果改一改 最多k个数字匹配呢

哦 好像也没啥区别 前几位可以一致试一试

如果进位才会有点儿烦

并不会

刚刚 WA 14/55 是因为输入 9 的时候莫名其妙输出了 1

我现在 WA 36/55 了，估计还有哪里写丑了

就对偶情况考虑下，999输出1111或者111输出99这种，就完事了。

其他还能怎么错，我是想不出来

过了，还是输入 9 的时候没处理好

【引用自 anhpp】:
如果进位
其实可以出一个在任意k进制下都是alien，但这题一出，我自己不会做

不对，这样这题都出错了

以前上课的时候用的作业题库。。。真亲切

这么强？？？

家人们做做我的
【引用自 未知】:
【水】钟慢效应是不是决定了人类永远也无法离开现在的宇宙？ 学术
给你个提示，可以考虑这个公式
\int_{\mathcal{M}} e^{i S[\phi]} \mathcal{D}[\phi] = \sum_{n=0}^\infty \left(\frac{\Lambda^n}{n!} \sqrt{\det\left(G_{\mu\nu} + \frac{8\pi G}{c^4} T_{\mu\nu}\right)} \right) \exp \le…

题呢？？？？@aqua 题呢？？？ @aqua 题呢？？？？？@aqua

题呢？？？？@aqua 题呢？？？ @aqua 题呢？？？？？@aqua 你在这样我真的要生气了

【引用自 未知】:
给你个提示，可以考虑这个公式 \int_{\mathcal{M}} e^{i S[\phi]} \mathcal{D}[\phi] = \sum_{n=0}^\infty \left(\frac{\Lambda^n}{n!} \sqrt{\det\left(G_{\mu\nu} + \frac{8\pi G}{c^4} T_{\mu\nu}\right)} \right) \exp \le…
【引用自 jnnksn】:
家人们做做我的

在开始今天的题目之前，让我们先来庆祝一下水老师连续三次抢到摸鱼楼二楼
【引用自 aqua】:
【摸鱼第二季完结】四月处于放弃边缘，如何进入工作状态。
大家好，我是水老师
【引用自 aqua】:
【摸鱼第三季完结】卷起还是躺下，大家都要自洽。
居然又抢到二楼了 欢迎跟我一起来做题呀～
【引用自 aqua】:
【摸鱼第四季完结】卷起还是躺下，大家都要自洽。
大家好呀！今晚真热闹～
除了摸鱼四号楼开张之外，今天泥潭的头等大事应该是茶色撸卡杀全家了吧。没关系，卡撸不成不要紧，还可以撸别的嘛，比如说撸铁和撸题都是很好的选择，甚至可以边撸铁边撸题，例如这道来自 2016 年 ICPC Northwestern Europe Regional Contest 的 Free Weights

image1040×1450 324 KB

image1040×150 5.21 KB

Kattis 链接：Free Weights – Kattis, Kattis

解题思路

这道题如果直接去找 the heaviest dumbbell that must be moved 的方法不好想（或者不好证明）的话，不妨换个角度考虑——如果已知某个重量 W，并且告诉你重量不超过 W 的哑铃可以随便移动，让你来判断能否完成任务。这样问题是不是就容易多了？

假设给定了 𝘞，该如何判断能否完成任务呢？

只需要把所有重量不超过 W 的哑铃统统拿走，看看剩下的哑铃是不是已经配好了对，就可以了。

可问题是我们要找的就是这个 𝘞 啊，这可怎么办呢？

既然哑铃的重量都是整数，我们只需要对哑铃重量的数据范围做个二分查找，就可以找到满足条件的最小 W 值了。时间复杂度 O(n log max(wᵢ)) ≤ 10⁶×log₂10⁹ ≈ 3×10⁷ 完全是可以接受的。

题外话

当然，这道题是有 O(n) 的构造方法的，不过与其花时间去思考它的正确性，不如尽快完成签到……感兴趣的潭友们可以自行思考一下。

参考代码
def read_ints():
return [int(x) for x in input().split()]

def binary_search(w):
lower = -1
upper = max(w)
while upper - lower > 1:
mid = (lower + upper) // 2
remains = [x for x in w if x > mid]
if remains[::2] == remains[1::2]:
upper = mid
else:
lower = mid
return upper

if __name__ == "__main__":
n = int(input())
ws = (read_ints(), read_ints())
print(max(map(binary_search, ws)))

水老师我不服 约战第五季

题都看不懂，终于看懂了只能想出来brutal force还是错的。例外水老师的解体思路给的好清楚啊

水姐终于来了一道我看得上的赛区

因为
【引用自 未知】:
【摸鱼第四季完结】卷起还是躺下，大家都要自洽。 搬砖
NAQ’21 的签到题用光了，得去别处找了
不能再偷懒了

讲真，现在AI coding agent这么厉害，不知道过几年面试不会变成考谁能 feed 正确的prompt 来引导AI完成coding task

我觉得这些签到题 AI 都能秒杀……

【引用自 pat】:
现在AI coding agent这么厉害
你可以试试把这题喂ai。不太可能成功btw 我错了

还真没试过，一般都是拿AI来写些repetitive code

不是说 o3 已经达到 cf grandmaster 的水平了么……

image441×783 20.2 KB

gemini 2.5pro 还没生成结果；但我在看thinking就知道我错了

不太意外，ai 业务代码的屎山都能搞得大差不差

well。我觉得这个评论not exactly

构造解我想不出来。可以提示下么？人变蠢了没办法

另外我来出道题吧，应该蛮简单的，忽然想到这个构造题：

给定正整数N。输出1…N的一个排列（permutation），满足任意两个数字的均值都落在这两个数字的位置区间之外。

例子：

N=3时，[3, 2, 1]不符合条件，因为2作为1和3的均值是落在1和3之间的。[2, 3, 1]符合条件，因为任意两个元素的均值都在区间之外。

N=6时，[1, 5, 3, 2, 6, 4] 是一个好的解，容易验证15对元素的均值不在这两个数字之间。例如，1和3的均值是2，但是1和3中间只有5，没有2。

这题有个比较优美的递归分治构造。

对每一行从左到右扫描，每次看相邻两个哑铃，如果重量相同则继续看后面两个，如果重量不同的话拿走轻的那个（并记录下最大重量），然后把留下来的那个和下一个继续比，依此类推……

所以出结果了么？

出了啊，就是标准解法啊

人变蠢的证据就是，一开始就想了下这，然后好像觉得是错的……

我在想它是真的会，还是它的训练集已经包含了 nwerc 的题解……

它装模做样想了一下的确是想出来的。思考过程很合理。

但后来再问它有没有其他好方法，它就说“题解是这么说的”

image2890×206 12 KB

1Y 了

剧透思路

水老师这种左开右开的二分好像不太常见

但是我想复杂了，用了个 ST 表来查两个哑铃中间的最值
【引用自 aqua】:
对每一行从左到右扫描，每次看相邻两个哑铃，如果重量相同则继续看后面两个，如果重量不同的话拿走轻的那个（并记录下最大重量），然后把留下来的那个和下一个继续比，依此类推……
绝了，想了一下这就是将 ST 省略后的构造法

哭晕了 想了半天线性还是没想明白

被逼无奈写了个二分

【引用自 未知】:
【9/8/25 更新第十题】推荐一些有趣但不难的编程练习题（不是 LeetCode） 搬砖
对每一行从左到右扫描，每次看相邻两个哑铃，如果重量相同则继续看后面两个，如果重量不同的话拿走轻的那个（并记录下最大重量），然后把留下来的那个和下一个继续比，依此类推……

歪个楼…这让我想起当年在THU凹数据结构和算法，没日没夜的搞作业，把我老妈的生日都忘了 被家里说了一顿….. 从此感觉自己还是别专业写码了

image1616×159 8.93 KB

题不错，但是平台看不到错误的输入？除了前几个test。那岂不是要花很多时间琢磨。

是这样的哦

【引用自 aqua】:
remains[::2] == remains[1::2]
你们python玩得真花

不过还需要手写二分吗
*ranges::partition_point(views::iota(0,1e9),[](int x){
for(int i=0;i<2;++i){
auto t=a[i]|views::take(n)|views::filter([&](int y){return y>x;});
for(auto it=t.begin();it!=t.end();++it){
int j=*it++;
if(it==t.end()||*it!=j)return 1;
}
}
return 0;
});

这花里胡哨的，竞赛的味出来了

有几个feature我没见过。虽然能猜出来。这是c++20？

不如用 Kotlin，玩得更花

yes
【引用自 RandomTrash】:
另外我来出道题吧
可以通过polygon上传codeforces让大家交一下，然后就可以 潭友啦

【引用自 abc123】:
codeforces
燕国地图有点短啊你这

这周是很多学校的 finals week，那么咱们也来个 finals 的题目吧，我是说，第 45 届 ICPC World Finals，题目叫做 Prehistoric Programs

image1220×1480 194 KB

image1220×490 11.4 KB

Kattis 链接：Prehistoric Programs – Kattis, Kattis

解题思路
【引用自 aqua】:
这是一道构造题，所以方法可能不唯一。如果你的方法和我不同，欢迎回复分享～
括号匹配算是很经典的问题了。一个括号序列合法的充要条件是：

左括号总数 = 右括号总数
当从左到右扫描这个序列的时候，截至任意时刻的左括号总数 ≥ 右括号总数

于是乎，当我们在构造这道题答案的时候，就是要保证任意时刻（左括号总数 − 右括号总数）的“盈余”必须非负，且最终“盈余”为 0。

具体怎样构造呢？

大方向应该不难想到贪心，也就是尽可能地让左括号在左边，右括号在右边。换句话说，如果我们考虑每块砖的总盈余，那么应该先选取总盈余为正的砖，再选取总盈余为负的砖。例如 ())())() 的总盈余为 -2，而 ((() 的总盈余为 +2，所以我们应该先选取 ((() 再选取 ())())()。

但只考虑每块砖的总盈余还不够，还需要考虑从左到右扫描过程中的最低盈余。例如 ))( 尽管总盈余为 -1，但其最低盈余为 -2，所以只有当我们当前盈余不少于 2 的时候才可以选这块砖，否则就不能选这块砖。

综合以上考虑，我们可以这样操作：

预处理输入数据，计算出每块砖的最低盈余和总盈余。
对于所有总盈余 > 0 的砖，按照最低盈余从大到小的顺序依次选取。
对于所有总盈余 ≤ 0 的砖，按照（最低盈余 − 总盈余） 从小到大的顺序依次选取。
最后检验一下如此选取的序列是否满足要求。如果满足则输出序列，否则打印无解。

参考代码
from functools import reduce
from itertools import accumulate

n = int(input())
a = []
for i in range(1, n + 1):
bal = list(accumulate(input(), lambda acc, c: acc + 1 if c == "(" else acc - 1, initial=0))
a.append((min(bal), bal[-1], i))

ans = (sorted(filter(lambda x: x[1] > 0, a), key=lambda x: x[0], reverse=True) +
sorted(filter(lambda x: x[1] <= 0, a), key=lambda x: x[0] - x[1]))
if reduce(lambda old, x: (min(old[0], old[1] + x[0]), old[1] + x[1]), ans, (0, 0)) == (0, 0):
for x in ans:
print(x[2])
else:
print("impossible")

【引用自 aqua】:
方法可能不唯一
真的吗zs

免责声明

一个小问题

“总”和“最低”都大于0的那些，就不需要排序了吧，直接都放最前面就可以了，然后总>0且最低<0的那些才需要排序。

是可以的，那些人畜无害

所以说
【引用自 aqua】:
方法可能不唯一

一周没题了，水姐

【引用自 未知】:
【摸鱼第五季完结】大家接着奏乐接着舞 搬砖
烂尾了

Memorial Day 快乐！今天其实也是 2025 年 ICPC North America Championship 的日子，那我们不妨一起来做一下刚刚结束的这场比赛的签到题——SLA Tomography

image1260×1200 110 KB

image1260×1510 178 KB

image1260×522 16.8 KB

Kattis 链接：SLA Tomography – Kattis, Kattis

解题思路

这道题就是个阅读理解题，别看题目很长，方法其实非常简单，代码也非常短。

举个例子，假设输入数据是 2 1 4，如何构造最窄的物件呢？

从上往下看，如果只考虑第一层 2 个单位的液态树脂，那么满足条件的最窄物件有多宽？

很显然，满足条件的最窄物件为 #..#，其宽度为 4。

第二层 1 小于第一层 2，是否需要拓宽物件？

既然这一层残留的液态树脂不超过上一层，我们只需要把上一层多余的 . 变为 # 即可，不需要拓宽物件。

于是满足前两层要求的物件为
#..#
#.##

宽度依然为 4。

第三层 4 大于第二层 1，是否需要拓宽物件？

这一层残留的液态树脂超过了上一层，我们必须要拓宽物件了。拓宽多少呢？既然还差 4 − 1 = 3 个单位的液态树脂，我们就在上一层物件的基础上再追加 ...# 即可。

于是满足前三层要求的物件为
#..#
#.##
#.##...#

总宽度变为 4 + (4 − 1) + 1 = 8。

对于任意输入，照此方法构造物件并记录下宽度即可。

参考代码
n = int(input())
prev = 0
width = 1
for _ in range(n):
x = int(input())
if x > prev:
width += x - prev + 1
prev = x
print(width)

image1866×181 4.8 KB

完了 只会签到题了

笑死 我甚至还加了一个判断 结果为0的时候不加1

At least one row will have at least one leftover cell of liquid resin.

不是 你不会觉得我们leetcoder会读完题的吧

【引用自 anhpp】:
读完题
题是不会读完，但是input不读完真的不怕吗

不是周五更新么，怎么还加班啊

号外

腹黑反证法

输入输出的例子没给impossible->不可能impossible

有点意思

每次做贪心题都觉得自己是 SB

昨天的 ICPC Live 直播间把这道题截图扔进 ChatGPT，o4-mini 思考了2分34秒后生成的代码一发 AC 了，速度超过了在场所有选手

o4-mini 毕竟也有 cf 2700 分，再加上读入和输出的 token per second 都比人类更快

如果没记错的话，最开始是 @Ryan2021 提出了一个猜想，然后我说不要开盒，然后掌门就删帖了。后来再有人
【引用自 aqua】:
【摸鱼第四季完结】卷起还是躺下，大家都要自洽。
以讹传讹
我也懒得理了，反正你们开心就好

然而最近这帖子又在隔壁被 quote 了，然后就有人私信问我是不是某某某，我觉得我还是来回应一下吧……我从来没说过我是姚班的，都是大家在这儿乱猜。本来我觉得无所谓，但最近泥潭日渐加重的开盒风气让我觉得如果我再不回应的话，也许会影响到被误猜中枪的姐妹们的正常生活……

泥潭本来就是个虚拟社区，何必非要对应到现实中的人物呢？

我不对 我有罪 我不好 我检讨

哎 实在是水姐姐人气太高了

掌门客气了

（我不是 我没有 我没私信 我没盒人最多盒个小号）

抽空做了一下这些题，最近泥潭的热帖都没赶上热乎的。折叠防剧透。

Frosting on the Cake

我只压缩了一维，也就比水姐多 O(n) 次乘法而已 但是C++爆了一次int。

Stamp Combinations

没有用双指针我直接一个暴力二分。但是忘了特判0的情况，WA了一次。

Pizza Party!

字符串处理比题目本身还烦，忘了处理k=1的情况，WA了一次。

Stacking Up

终于1A了一次。随便二分搞一下。

MrCodeFormatGrader

显然我们有一个 O(C) 的做法和一个 O(N) 的做法，写了个 O(N) 的，1A。

Alien Integers

这个构造真烦呀，考虑位数，一共四种情况需要考虑，WA了一次。

Free Weights

一眼题，二分答案，1A。

Prehistoric Programs

WA了好几次 。判断括号序列是否匹配一个常规的处理就是考虑1和-1的映射，再看一眼规模那基本上就是排序贪心无疑。一开始急功近利着急睡觉随便猜了一个做法果然WA了。睡觉起来造了几个样例发现还需要考虑前缀和中出现的最小值。令 x 为序列的和， y 为前缀和出现过的最小值，那么我们有这几种情况：

x ≥ 0, y ≥ 0，随便排。
x ≥ 0, y < 0，显然按 y 从大到小排序是最优的。

注意到这两种情况可以合并，所以都按 y 从大到小取就完事了。
x < 0, y ≥ 0，不会出现这种情况。
x < 0, y < 0，一开始想的是按 (y, x) 从大到小排，一直WA。又造了几个例子发现对于)(和))，我们其实应该首选)(，因为)(又引入了开放的左括号一定需要别的串才能匹配上。而且对于更长的序列例如))))((((也要排在))的前面，所以这时候单纯比较 y 或者 x 是不能得到正确的排序的。观察发现按 y-x 的从小到大排序可以达成这个目标，因为这个值越小意味着越需要被排在中间，改后直接AC。证明不知道咋证明，我一个直接摆烂。

纯属一开始就看到了整体框架但是细节没扣对就开始写造成的无谓WA。

SLA Tomography

WA了一次才认真想了一下，过了。

@aqua 论坛发帖format的帖子找不到了，公式打不出来咋办哦。。 改了一下。

把尖括号的 details 换成方括号的 details
[details="总结"]
此文本将被隐藏
[/details]

才看到水姐声明 我也滑轨

又又又烂尾了吗

最近摸鱼楼太热闹了，我都忘了这儿了

第十题都快一个月了，难产了嘛水老师

【引用自 aqua】:
视心情不定期更新[1]
也可能直接烂尾 ↩︎

不定期=定期不

好玩好玩 水老师再来几个益智的

我试了一下，感觉时间卡得挺紧的

即使是用 C/C++，我用 cin/cout 的时候都过不了

总结
#include <bits/stdc++.h>

using namespace std;

char s[12345], arr[12345];
int k;
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%s%d", &s, &k);
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (k > 0 && s[i] != '0') {
arr[i] = '9';
k -= 1;
}
else {
arr[i] = '0';
}
}
for (int i = n - 2; i >= 0 && k > 0; i--) {
if (arr[i] == '0' && arr[i + 1] == '9') {
arr[i] = '9';
k -= 1;
}
}
if (k > 0) {
puts("-1");
}
else {
arr[n] = '\0';
puts(arr);
}
}
return 0;
}

算法如果对，就不要去想TLE，意义不大，又不打竞赛了。

【引用自 KagaSumire】:
即使是用 C/C++，我用 cin/cout 的时候都过不了
其实有可能是因为这题spj他的spj输入不见得有多优化。

【引用自 哈耶克】:
就是因为TLE，不知道算法对不对
看了一下，应该对
【引用自 哈耶克】:
奇技淫巧time：读入、输出优化 - OI Wiki
我当时就试过解除关联了

那我既然评论肯定看过你code了 差不多就完事了

做题应该源于生活、高于生活，今天我来出一道与本论坛主题（MS）切身相关的题。
Easy version:

小明开了一个有高额dd bonus的粉色银行账户，需要将其他N个银行的账户与粉色账户绑定。每个银行会进行trial deposit，转入两笔钱 0< 0.xx <= 0.yy < 1 ，之后既有可能只转出一笔 0.xx+0.yy ，也有可能分别转出两笔 0.xx 和 0.yy 。

由于粉色银行的activity界面有bug，不显示每笔交易的附言，只显示金额，小明十分混淆。你的任务是untangle这些交易，将两笔对应的转入进行配对；已知交易记录内容存在唯一正确的配对。

输入：N，M，随后M行为转入或转出交易，转出表示为负数。2<N<100。范例：

5 16

+0.13

+0.35

+0.43

+0.43

+0.48

+0.50

+0.60

+0.55

+0.78

+0.78

-0.55

-0.78

-0.78

-0.91

-0.91

-1.10

输出：共N行，每行两个数字 0.xx <= 0.yy ，表示配对后的一对trial deposit，按偏序从大到小排列。范例：

0.13 0.78

0.35 0.43

0.43 0.48

0.50 0.60

0.55 0.78

Hard version:

这个粉色银行有很大的bug，每一笔ACH动账会被sweep到一个cash sweep账户，在activity界面会显示成一正一负两笔交易，并且有一定概率只显示其中一侧（每笔进账或出账至少显示一次）。给定所有activity记录，正确的配对并恢复每对micro deposit。

（人脑推理还是能solve出来的，programmatic的解决可能需要SMT solver。）

下次面试就出这道题

Yeah 我就是解完了觉得好像很适合拿来面试 才整理了一下发论坛

correct me if I am wrong

我觉得这题超级难啊，甚至很难有不是遍历所有可能的方法–主要是“有唯一解”这个条件有点太难用了。

举个例子，50个正数，30个负数，其中20对正负恰好相等的。那么由条件推出，分开扣回的10笔，二合一扣回的40笔（20家银行）。问题来了，那20组正负相等的里面恰好有10组其实不是同一笔的扣回，那么怎么确定是哪10组？总不能逐一检查（20取10）这么多种可能吧？

（而且应该能构造出例子，使得取别的10组的时候会有多解（从而不满足条件），这个也很难处理吧。）划掉，这一段我想错了，如果某个别的10组也有解，就直接导致多解不满足条件。

有唯一解才是关键信息，保证了负数transaction的个数一定是正数/2+1，然后就很简单了

你没理解，正数两笔x和y，对应的负数既可能是一笔x+y，还可能是两笔x和y。你看出题人的例子里面，就有一家银行的0.55和0.78是分别扣回，所以在输出里省略了。

你可能没有正确理解例子的输出，这个例子故意搞出了一些数字重复，增加了难度。题干“只存在唯一解”确实蕴含了一些可以推理出来的其他限定条件。

这题easy mode站在图匹配视角用网络流还是不难的，但网络流好像有点大炮打蚊子。而且输入规模被唯一解限定死了，论复杂度比超时也没意思，除非改成小数点后六位…

潭友们新学年快乐！过了一个暑假，大家有没有晒黑呢？
【引用自 aqua】:
水老师迟到的加勒比海东线邮轮游记（Carnival: USVI – PR – TC）
俗话说得好，美白第一步是防晒
在上周四刚刚结束的第 49 届 ICPC World Finals 中就有一道关于防晒的问题——Walking on Sunshine

image1220×1760 333 KB

image1220×1500 95 KB

Kattis 链接：Walking on Sunshine – Kattis, Kattis

解题思路

这道题恐怕是近年来总决赛最简单的签到题。题目描述乍一看像是个二维（甚至是计算几何）的问题，但实际上阳光永远只会从正南方向照射过来，而且横着走并不会晒到太阳，可以随便走。所以我们可以完全忽略横坐标，只要考虑这些区间在 y 轴方向的投影就足够了……

于是问题就变成了在数轴上给定若干区间，求两点之间未被任何区间覆盖的部分总长是多少。方法很简单，只需要将所有区间排个序，然后从小到大扫描一遍即可。

参考代码
def read_ints():
return [int(x) for x in input().split()]

n, xc, yc, xa, ya = read_ints()
shades = [read_ints() for _ in range(n)]

cost = 0
topmost = ya
for x1, y1, x2, y2 in sorted(shades, key=lambda x: x[1]):
cost += max(min(y1, yc) - topmost, 0)
topmost = max(topmost, y2)
cost += max(yc - topmost, 0)
print(cost)

有生之年系列

【引用自 aqua】:
【摸鱼第十季完结】第十季可以摸鱼吗？
泥潭今日信息密度再创新低
本来想响应水姐号召分享某游乐场的一点心得体会干货，结果发现原贴被删了？！看来最初带大家进门的坛友想上车关门，我还是尊重他的决定吧…

今天再出一道源于生活高于生活的论坛主题编程题。

小明开了N个账户，每个账户有各自的野路子，体现为从另外 k_N 个账户转入此账户时可以凭空产生 i\_{n,m}\\% 的收益。每个账户也会给不同的利息，按每天结束时的余额给 rate_N\\% 加入第二天的余额。最后，钱从每个账户转出时也会有对应的收费，可能是按固定比例每次转账收 O\_{n,m} 刀，也可能是按比例收 o\_{n,m}\\% ；作为简化，可以假定所有转账都是当天隔夜完成、第二天T+1结算开始时的新余额。本题的难点是每个账户有不同的AML限制：转入的资金必须存放 T_n 天才能尝试取走，否则会被封号冻结资金（ T_n 天内可以转出更早之前已解锁的余额，或者利息收益）。
Harder version:

小明正计划在第一天存入了一笔数额不定的启动资金进入1号账户（第一日1号账户的余额为$x），给定未来账单$Z，他需要在第Y日将所有资金归集回1号账户，保证余额大于等于$Z。求他需要存入的最小值$x。

如果没有思路，可以先想简单版本，再解决对偶问题。
Easy version:

小明在第一天向1号账户存入了一笔启动资金，在1号账户的余额为$X，然后进行最优操作；他需要在第Y日将所有资金归集回1号账户，求他可以获得的最大结束余额$Z。

提示：本题看似DP，还是网络流更快。

（我还没空编测试数据…现实世界常见的情况是锁定期T=3, T=7, T=65，利率是0或者2%或者4%apr除以360，转入收益是1%, 1.5%, 2%, 3%，转出收费是0, 1.5%, 1.8%, 3%, $0.1, $0.25, $1.99等等）

小哥哥好牛逼啊

lz怎么tj了？

lzmyxjj

今天遇到了一个有趣的问题，找到O(nlog(n))解法的时候眼前一亮，遂记录下来，略作改编，以飨坛友。

坛友小明手持多张信用卡，每张卡上都绑定了很多限时offer活动。每个offer规定了有效日期区间、达标消费金额和可获得的积分奖励。比如他的A卡有一个开卡奖励offer，在1月1日到3月31日之间刷卡20000元可以获得30点分数。A卡也有一个升级offer，在1月30日到5月30日之间刷卡15000元可以获得10点分数。同时，卡A又有一个spending offer，在3月2日到3月31日之间刷卡每满5000元可以获得1点分数，且这个offer可以重复使用3次。作为专业MS玩家，他早就发现了同一张卡上不同积分活动都可以叠加，也就是只要消费达到了各个活动各自的要求，他就能获得所有被完成任务的活动的积分总和。他的另一张卡B就比较无趣，只是每个季度有活动，刷满1500元可以获得7.5分。卡C是首年花满1000给1积分。卡D是首年花满500给2积分。

由于突发情况，小明变成了"云居民"，再也没法进行日常organic消费，只剩一笔无法拆分的金额为X的大额消费需要完成，现在他需要精心策划：选择哪张卡、在哪一天刷卡，才能获得最大的积分收益？

请你帮助小明，对于给定的若干消费金额X，分别计算最优的刷卡策略（卡号+日期），使得获得的积分最大化。若有多个日期收益相同，输出最早的日期；若多张卡收益相同，输出字典序最小的卡号。

输入格式

第一行一个整数 Q ，表示查询次数。

接下来 Q 行，每行一个整数 X ，表示待查询的消费金额。

接下来一行两个整数 C, M ，分别表示信用卡数量和offer总数。

接下来 M 行，每行描述一个offer：

card_id : 卡号标识（字符串）
start_day, end_day : offer有效日期区间（每个日期用整数表示）
threshold : 触发该offer所需的最低消费金额
reward : 触发后获得的积分（可能为浮点数）

样例输入
4
1000
5000
15000
20000
4 10
A 1 90 20000 30
A 30 150 15000 10
A 61 90 5000 1
A 61 90 10000 1
A 61 90 15000 1
B 1 90 1500 7.5
B 91 180 1500 7.5
B 181 270 1500 7.5
B 271 360 1500 7.5
C 1 365 1000 1
D 1 365 500 2

注：部分offer为"阶梯型"，即每满足一定消费额度即可重复获得积分（有次数上限）。例如满5000可重复3次的阶梯型offer会在输入中表示为刷满5000、刷满10000、刷满15000三行。

数据规模

Time limit: 1s, Mem limit: 256MB

Easy难度: 0<start_day<end_day<365, C<100, M<100, Q<10

Medium难度: 0<start_day<end_day<1,000,000,000, C<1,000, M<1,000,000,000, Q<1,000,000
输出格式

共 Q 行，每行输出一个卡号、一个日期和一个积分，表示对应消费金额X能最大化积分回报的消费日期，以及对应的积分。

若有多个刷卡方案积分相同，优先输出卡号字典序小 的；若卡号相同，输出日期最早的。
样例输出
D 1 2
B 1 7.5
A 61 13
A 61 43

样例解释

X=1000 ：只有D卡（500返2）和C卡（1000返1）可触发，D卡收益2 > C卡收益1，选D卡第1天刷。
X=5000 ：A卡触发一档阶梯offer可得1分（需在第60-91天），B卡触发季度offer可得7.5分（第1天即可），C卡1分，D卡2分。最大收益为B卡的7.5分，最早触发日期为第1天。
X=15000 ：A卡在第61天至第90天之间，可同时触发升级offer（15000返10）和3个阶梯offer（满5000、10000、15000各返1），总计13分。其他卡最高收益均不超过13分。满足该最大收益的最早日期是第61天。
X=20000 ：A卡在第61天到第90天区间内，可同时触发：开卡offer(20000返30)+升级offer(15000返10)+阶梯offer×3(5000返1×3) = 43分，为全局最优。满足条件的最早日期是第61天

M 1e9没打错？？？

为了庆祝 iOS 26.4 正式推出弱智 emoji 🫪[1]，今天来做一道上周刚刚结束的 2026 年 ICPC North America Championship 的弱智签到题——Evil Judges，大家试试能不能三分钟之内做出来

image1260×1600 317 KB

image1260×320 11.9 KB

Kattis 链接：Evil Judges – Kattis, Kattis

解题思路

为了简化讨论少打几个字，我们姑且称 AC 或 AK 子序列为“弱智对”[2]。

如果所有的 A 都在最右边，那么弱智对的数量为零。

否则，我们每次找到一组 AC 或 AK 交换一下，都恰好会减少一个弱智对。

所以这道题其实就是累计一下每个 C 或者 K 之前有几个 A，再减去交换的次数就好了（注意减到零就别再减了）。

参考代码
s = input()
m = int(input())

a_count = 0
inversions = 0
for c in s:
if c == 'A':
a_count += 1
else:
inversions += a_count

print(max(inversions - m, 0))

not to be confused with ↩︎

not to be confused with 逆序对 ↩︎

庆祝水妈时隔半年+归来

还有别的吗，这个太水了

7456 我本来还在想 这要怎么数

拍一下脑袋才反应过来 这不就是加减法吗

真的给猴哥学校跪了，first solve 三分钟，我连题都没读完呢……

【引用自 aqua】:
三分钟
太慢了，搁lc周赛人家四题都做完了

本來想看看自己有多弱智，但是想到 JavaScript 處理 input 好麻煩就懶了

这种题不用 Python 就是在跟自己作对，C++ 还要担心 int 会不会溢出

【引用自 aqua】:
担心 int 会不会溢出
JavaScript 有 BigInt

JS 寫題實在痛苦，很多標準 data structures 都沒有，搞得 LeetCode 還得給你引進第三方庫

python也没有标准
【引用自 aqua】:
【摸鱼第十四季完结】你也要变成和我一样的大人了呢
TreeSet/TreeMap
也得用
【引用自 aqua】:
【摸鱼第十四季完结】你也要变成和我一样的大人了呢
山寨包

说实话我被 安利了几次之后现在真心觉得
【引用自 aqua】:
Kotlin
不错

看题型想到组合计数，想了三分钟然后发现只是加减法

IMG_5045533×601 59.5 KB
【引用自 aqua】:
int
老话说得好，不开long long见祖宗

等待 sortedcontainers 加入標準包的那一天：Add binary search tree to collections - Ideas - Discussions on Python.org

JavaScript 可是連 queue/heap 都沒有

【引用自 aqua】:
大家试试能不能三分钟之内做出来
三十分钟都做不出来，我太笨了
【引用自 aqua】:
Kotlin
旅行者也用，虽然是主人的任务罢了

【引用自 aqua】:
大家试试能不能三分钟之内做出来
用时 10 分钟

还爆了一波 int

罚时 20 分钟

nac.icpc.global

G-Gemstonedowsing.pdf

959.62 KB

四小时内做出来击败100%美国大学生

有趣但不难

注意审题！

摸鱼人节（April Fish Day）快乐！不知不觉这个帖子已经一周年了。一年十二题，四舍五入也算是月更了吧 #footnote-7938349-1 今天的题目是 2026 年 https://nac.icpc.global/ 的另一道签到题。这是一道跟薅羊毛有关的题——I Don’t Miss Pennies /uploads/short-url/9t9nB8brKJI2k3cgFmCJldFFXgN.png?dl=1 /uploads/short-url/2Y1F95sBubBkSfWXgvhGf34n69f.png?dl=1 Kattis 链接：https://open.kattis.com/problems/idontmisspennies 解题思路 首先我想说的是，题目中薅羊毛的方法简直是弱爆了，https://www.uscreditcardguide.com/citi-rewards-plus/ 才是 yyds（ 言归正传，其实这道题的结果跟每件商品的具体价格无关，只跟价格除以五的余数有关。 如果余数是 0、1、2，那么单独购买就好了，羊毛薅到 如果余数是 3 或 4，那我们得想办法组合一下。最好的办法是每次把一个 3 和一个 4 凑成一对，可以薅到 2¢。这样凑完之后…… 如果还剩下多余的 3，那么每两个 3 凑在一起可以薅到 1¢。 如果还剩下多余的 4，那么每三个 4 凑在一起可以薅到 2¢。 如果还有多余的零头，就只能忍痛被反薅了 参考代码 import collections input() c = collections.Counter(p % 5 for p in map(int, input().split(" "))) pairs = min(c[3], c[4]) c[3] -= pairs c[4] -= pairs print(c[1] + c[2] * 2 + pairs * 2 + c[3] // 2 - (c[3] % 2) * 2 + (c[4] // 3) * 2 - c[4] % 3) [WARN] off-by-one error #footnote-ref-7938349-1

連簽到題都寫不出來

随便贪了一下，过了。懒得证明了去捞卤牛肉了 n = int(input()) s = input() mods = [0]*5 for item in s.split(' '): mods[int(item)%5] += 1 b, c, e, d = mods[1:] res = b+2*c-d-2*e+min(d, e)*5 d, e = d-min(d, e), e-min(d, e) res += (d//3)*5+(e//2)*5 print(res) 写完才发现和水妈的贪法是一样的。果然同样的论坛养出同样的挂壁。

WA 一次，寫得好醜 import collections n = int(input()) prices = [int(_) for _ in input().split()] piles = collections.defaultdict(int) for p in prices: piles[(p % 5] += 1 # 3 + 4 -> 7 pair = min(piles[3], piles[4]) piles[3] -= pair piles[4] -= pair piles[2] += pair # 3 + 3 -> 6 piles[1] += piles[3] // 2 piles[3] %= 2 # 4 + 4 + 4 -> 12 piles[2] += piles[4] // 3 piles[4] %= 3 res = piles[1] + piles[2] * 2 - piles[3] * 2 - piles[4] print(res)

看不懂Python desuwa 总结 #include <bits/stdc++.h> int n, x, res; int main() { int a[5] = {0}; res = 0; std::cin >> n; while (n--) { std::cin >> x; a[x % 5]++; } if (a[3] > a[4]) { a[2] += a[4]; a[3] -= a[4]; a[4] = 0; int r = a[3] / 2; a[1] += r; a[3] -= 2 * r; } else if (a[3] == a[4]) { a[2] += a[3]; a[3] = 0; a[4] = 0; } else { a[2] += a[3]; a[4] -= a[3]; a[3] = 0; int r = a[4] / 3; a[2] += r; a[4] -= 3 * r; } for (int i = 1; i <= 2; i++) { res += a[i] * i; } for (int i = 3; i <= 4; i++) { res -= a[i] * (5 - i); } std::cout << res << std::endl; } 这种题比较适合数学好的人做，不用纠结半天证明贪心是对的

忘记了一个判断，硬吃一个WA，爆了

aqua: 一年十二题 NAC 13题，刚好水一年

非交换几何: 有趣但不难 注意审题！

/u/nik0major 是能去nac的大手子，这些题都是有趣又不难

别造谣

给竞赛爷奶