夏令营7.15总结

今天又模考了。

时间线

$8:30\sim8:40$自习，题目坏了

$8:40-9:03$做T1，AC

$9:04\sim9:30$做T2，69tps

$9:30\sim10:00$想T3-T4

$10:00\sim10:40$尝试T4

$10:40\sim11:20$尝试T3

$11:20\sim12:00$再次T2，变成60tps

题目

T2

（T1太简单，先不写了）

每个值出现了几次？

map<long long,int> cnt

记录整体操作，加了多少s。

set 把$x-s改成y-s$，注意x==y

这题用到了计数排序的思想，定义$a_i$表示数字$i$出现了$a_i$次。

出现INFLATION时，记录一个偏移量，到时候读取时下表要减去这个偏移量。

不知道为什么还没过

T3

核心思路是通过逐步缩小序列中最大元素与最小元素的差距，最终使所有元素相等。

就是每次都把最下的那一部分增加一个值，然后排序。重复操作直到所有的值相同。

步骤：

• 计算增量：d = (最大元素 - 最小元素 + 1) / 2。这里加 1 是为了向上取整。

• 寻找可加的前缀：遍历序列，找到最大的 i 使得前 i 个元素加 d 后不超过当前最大元素。

• 执行操作：为前 i 个元素加 d，记录操作（i 和 d），然后排序序列。

T4

用dp。

核心逻辑：
每张牌可以选择 “打出” 或 “不打出”。若打出，则需要考虑它在当前轮次的消耗（基于已打出的牌数，费用翻倍）。但直接按轮次处理会很复杂，可通过逆向思维优化（就是滚动数组）：

• 假设最后一张打出的牌是$i$，此时它的消耗是$C_i$（因为之后没有牌了，无需考虑翻倍）。
• 倒数第二张打出的牌$j$，消耗是$2\times C_j$（因为后面有 1 张牌，所以它的费用在打出后翻倍一次）。
• 以此类推，第$t$张（从后往前数）的消耗是$2^{t-1}×C$。

因此，逆向定义状态：dp[s] 表示 “还需打出一些牌，当前剩余能量为 s 时的最大伤害”，则转移方程为：
对于每张牌$i$，若选择它作为 “下一张要打出的牌”（即当前轮次的第一张），则消耗 C_i，剩余能量变为$(s - C_i) / 2$（因为后续牌的费用会翻倍，相当于剩余能量需除以 2 来匹配），即：$dp[s] = max(dp[s], dp[(s - C_i)/2] + D_i)$（需满足$s ≥ C_i$且$(s - C_i)$为非负偶数）。