前情提要

书接上回：CCF CSP-J/S 2025 游记

Day -18

Day (-16)~(-12)

Day -11

Day -2

Day -1

Day 0

参加 NOIP 模板自测赛，复习模版。

Day 1

听到有人黑《原神》，众多角色纷纷表示不满。

我常常追忆过去。

云朵之间亦有分别：积（jǐ）云厚重，而（èr）卷（juàn）云（yùn）飘渺。

T1

T2

• 暴力：枚举所有定价方案，DP 检查贪心方案是否是最优方案。时间复杂度 $O(2^nnm)$。期望得分 $20 \text{pts}$。
• $m=2$：考虑什么情况下才会出锅，当且仅当性价比最大的 $w=1$，性价比次大的 $w=2$。枚举这个最大值，它右边的都要除以 $2$，比最大值除以 $2$ 大的都要除以 $2$，小的是自由的。时间复杂度 $O(n \log n)$。期望得分 $20 \text{pts}$。
• $m=2n-1$ 和 A 性质：输出 $2^n$。期望得分 $8 \text{pts}$。
• $m=2n-2$：出锅当且仅当最后只剩 $2$ 元时，买那个性价比高的 $1$ 不如买性价比低但原价高的 $2$。枚举那个 $1$ 是谁，并检查是否满足上述情况。观察样例发现好像那个 $1$ 只有可能是最小值。期望得分 $4 \text{pts}$。
• B 性质：所有 $1$ 都在 $2$ 前面。情况有点复杂，想了半天各种推组合数都是 $O(n^3)$。破防了。没看见 B 性质 $O(n^3)$ 有 $12 \text{pts}$。没写。

T3

T4

• 暴力：考虑把 $a$ 前缀和。对于每个 $i$，枚举包含它的区间的左端点，那么右端点肯定在一个范围内。此时左端点固定，只用找这段区间内 $a$ 的前缀和的最大值。ST 表启动。时间复杂度 $O(qnL)$。赛时没发现 B 性质可以这样闯过去，所以期望得分 $15 \rm pts$。
• A 性质：区间 check max，单点查询。看我线段树。怎么跑 $6\rm s$？？原来 $O(nq\log n)$ 在这道题可爱的数据下被炸飞了。死了。

Day 2

Day 3~7

Day 8

后记