T1 的 Hack 数据提醒我,尽管时间复杂度没有变化,但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。
T2 没有认真读题,忽略了“恰执行一次”的要求。
T3 里面没有使用自己熟悉的存边方式,时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。
简单题解
A – 跳棋
从 $(x,y)$ 跨步跳能够跳到 $(x\pm 2,y),(x,y\pm 2)$,以及 $(x+k,y+k),k=\pm 2$。可以发现 $x,y$ 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块,在这些连通块上 BFS 即可。
若采用 std::map 存储,时间复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)$。需要采纳“避免遍历不存在的连通块”之类的优化。 (更多…)