其实有可能是因为这题spj他的spj输入不见得有多优化。
2 个赞
看了一下，应该对
我当时就试过解除关联了
那我既然评论肯定看过你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。）
3 个赞
下次面试就出这道题
1 个赞
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站在图匹配视角用网络流还是不难的，但网络流好像有点大炮打蚊子。而且输入规模被唯一解限定死了，论复杂度比超时也没意思，除非改成小数点后六位…
潭友们新学年快乐！过了一个暑假，大家有没有晒黑呢？
在上周四刚刚结束的第 49 届 ICPC World Finals 中就有一道关于防晒的问题——Walking on Sunshine 
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)
4 个赞
有生之年系列
本来想响应水姐号召分享某游乐场的一点心得体会干货，结果发现原贴被删了？！看来最初带大家进门的坛友想上车关门，我还是尊重他的决定吧…
今天再出一道源于生活高于生活的论坛主题编程题。
小明开了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等等）
2 个赞
小哥哥好牛逼啊
lz怎么tj了？
今天遇到了一个有趣的问题，找到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天
1 个赞
M 1e9没打错？？？
为了庆祝 iOS 26.4 正式推出弱智 emoji [1]，今天来做一道上周刚刚结束的 2026 年 ICPC North America Championship 的弱智签到题——Evil Judges，大家试试能不能三分钟之内做出来 
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))
4 个赞
庆祝水妈时隔半年+归来
还有别的吗，这个太水了
1 个赞