下面是自己想到了做法的题。

下面是现场过的题。

Likes

考虑赞数最多的方案一定是所有人先赞然后取赞；赞数最少的方案一定是能取赞的人最先点赞并立即取赞。

代码

Settlement of Guinea Pigs

考虑每次检查性别之后的最坏情况是只有一只宠物和其他宠物性别均不同；而检查之后新的宠物一定需要单开住所。模拟即可。

代码

The Very Beautiful Blanket

考虑如何利用每个 \(2\times 2\) 的矩阵有占有了两行/两列各两个元素以抵消影响。此时可以将矩阵中第 \(i\) 行第 \(j\) 列的元素设为 \(2^8i+j\) 以抵消对应影响。

代码

Music Festival

考虑“存在前缀最大值”的序列一定可以占据一段前缀且按照最大值大小升序排列。此时对于每段子序列，查询出对应所有前缀最大值的位置；则其作为“存在前缀最大值”的序列时，之前接的最长序列一定是最长且满足比某个前缀最大值小的序列。枚举前缀最大值即可。

代码

下面是赛后过的题。

Buying gifts

考虑钦定了 \(a\) 对应的最大值之后，如何将 \(b\) 的最大值最优。此时比当前 \(a\) 大的二元组一定取了 \(b\)，不比当前 \(a\) 大的二元组可以任取。此时后一部分一定有取最接近 \(a\) 的两个数进行讨论最优。

代码

The way home

考虑将路径钦定好之后，最优演出方案一定是在某个前缀最大值处演出到当前的钱刚好够到达下一个前缀最大值，如果能多走就一定会多走（意味着初始钱数还够就绝对不会停留）。此时只需要在前缀最大值处统计答案。到达某个前缀最大值点之后，一定有当前能剩余的钱变化后，对这个前缀最大值的决策影响不超过 \(1\) 天。所以只需要维护到达这个点的最小天数和对应能剩余的最多钱即可。

代码