CSP-S2024游记

xxxaIq · 2024-11-11 20:09:44 · 生活·游记

DAY 0

下午全机房人集体请假回家。

晚上打了一会游戏，很晚才睡。大概 11 点？

DAY 1

中午吃完饭一点多就进考场了。

试题 PDF 的密码需要手动输入。

打开 \text{T1}，看到样例 2 瞬间想到一个结论：答案为众数出现的次数，手模了一个小样例之后发现没什么问题，但是大样例还没有发，我也不会证明，怕浪费时间就先没写。

开 \text{T2}，怎么是物理题？

看到下面有一坨公式首先想到是诈骗，答案和公式没关系，就是唬人的，需要根据加速度的性质和物理知识自己推出一个公式。但是高中物理我不会啊。

仔细读题发现和物理没什么关系，用给的公式直接代入就行。

看了半天只想到了 O(nm\log n) 的做法。

先去看 \text{T3}，一眼 dp，想到了 dp_{i,j,k} 表示前 i 个数上一个红色的位置为 i，上一个蓝色的位置为 j 的答案，但这样时间复杂度和空间复杂度都是 O(n^3) 的。

想了一会发现根据我设的状态，j,k 中必有一个等于 i，因为当前位置不是红就是蓝。所以就可以优化成 dp_{i,j,0/1} 表示前 i 个，第 i 个为 红/蓝 色，上一个 蓝/红色的位置为 j，的答案，这样复杂度就变成了 O(n^2)，可以拿到 50\text{pts}，迅速打完。

此时下发了大样例，把 \text{T1} 和 \text{T3} 都测了没什么问题。

然后拐回去看 \text{T2}，这时才发现 V 是固定值。

想到了 O(n\log^2 n) 的做法，打完过了样例，最大的一直 RE。不管了就这样。