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$。