CSP-S2024游记

xxxaIq

2024-11-11 20:09:44

Life & Travel

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。不管了就这样。

## DAY 3 去洛谷上估分才发现 $\text{T2}$ 开的 STL 太大导致 MLE 了,只有 $20\text{pts}$。 ## DAY INF 初评成绩出来了,第二题挂没了。 $100+10+50+0=160$。