GDKOI 2023 J 游记

_Cheems · 2024-01-12 14:06:59 · 个人记录

• DAY -? ：正常训练。
• DAY 0 ：下午到达酒店休息。（fun fact：去便利店买东西然后被门口的狗追了？？？）
• DAY 1 ：吃早餐然后去听讲座，下午考完就回酒店休息了。
• DAY 2 ：同 DAY 1，只不过是回家而已。

下面是题解（无代码），题目是我记下来的，可能有所错误。

DAY 1：

得分：180，好烂。

T1

给出 n 只怪，血量 a_1...a_n。你有 m 能量，每时刻可以选择：

1. 选一只怪扣它一点血，不耗能。
2. 选一只怪扣它两点血，耗能一点。
3. 所有怪都扣一点血，耗能一点。

每时刻你操作完后，存活的怪都会对你造成一点伤害。求你受到的最小伤害？

一道需要感性猜结论的题。显然群伤在大多数情况下都是最优的，然后计算发现只有当存活怪物数量 \le2 时才会考虑对单。于是能用群伤就用群伤，当怪 \le2 时察看是否有怪血量为奇数，有的话用一次群伤再全用对单，没能量就用普攻。这个贪心策略是对的。

T2

正常难度贪心，考场脑子抽了写了 dp，成 joker 了。

T3

斜率优化 dp，很不好想，目前还不会。

T4

玄学图论题，是原。考场还混了此题最高分。

DAY 2：

得分：140，炸了。

T1

两天唯一一道签到题，不想说了。

T2

有一本有 n 个章节的书，a_i 指的是此前必须看过至少 a_i 个章节才能看 i 章节。每天从 1 到 n 尝试看每个章节，看过了就跳过。求多少天后看完所有书，无解输出 -1。

可以考虑用线段树维护。