时间安排
7:35 - 7:45
看题。前三题好像都能做,T4 T5 不能一眼。
7:45 - 7:50
写了 T1.
8:00 - 8:20
先写了 T2 暴力,正解最后再想。
8:20 - 8:50
T3 胡了个栈,过了样例和几组手造小数据就直接扔了。
9:00 - 11:00
两个小时拿 0 分。几乎可说是什么都没干,T4 T5 没有头绪,T4 写了个贪心骗分,T5 暴力调不出来。
11:00 - 11:10
决定不调 T5 暴力,写个特殊性质去想 T2 正解。
11:10 - 11:50
没写完 T2。
总结反思
- 时间利用不合理,导致两个小时一分都拿不到。
- 题目中没说不出现的都是可能出现的。
题解
A.咕咕
简单题。
B.数字面包卷
简单题。
C.找子串
KMP + 栈。
D.图论问题
考场降智简单题。
E.舞步
好题。先考虑没有时间限制的弱化版,会有若干群牛,每群牛会构成一个环。再来考虑有时间限制怎么做。设置换次数为 \(z\),则环的大小小于 \(z\) 的和无时间限制一样不受影响,而其余的环上的每一个点 \(x\) 经过这 \(z\) 次置换后到达的点是一定的,设为 \(y\),那么答案就是先进行 \(z\) 次置换经过的点的集合 + \(y\) 走剩余步经过的集合。可以用双指针在 \(O(k)\) 的时间复杂度内求解。