P12892 [蓝桥杯 2025 国 Java B] 弹跳鞋

· · 题解

可笑吗?我访问提交记录的时候有多慌张。他会 AC 吗,隐私用户只有我能看的模样。从夜深人静,一直调过到天亮。你反正不会再担心,我隐隐作疼的心脏。

显然题目是要你找到一个 i 使得 S=\{1,2,\ldots,i\},问是否存在一个子集的和为 b 满足 \frac{i(i+1)}{2}-2b=n

结论:第一个 \frac{i(i+1)}{2} 大于等于 n\frac{i(i+1)}{2}\equiv n\pmod{2}i 为答案。可以发现 b=\frac{\frac{i(i+1)}{2}-n}{2},只要证明 b 可以被凑出来的即可,因为 b\le \frac{i(i+1)}{2},所以这是成立的。