2.2 如何把一道简单思维题变难

· · 个人记录

今天是搞笑场，符合“精神状况记录”的 tag。

方法一：将 O(n) 甚至 O(\log n) 的需要一定思维的题目，将 n 开到 1000，100 等两级。

ARC108D AB

给定 c_{A/B,A/B}\in\{A,B\}，每次可以在 XY 间插入 c_{X,Y}，问可以得到多少种长 n 序列。

重要：数据范围，n\le 1000。

想必在看完“方法一”时，大家都已经秒了吧！

首先如果有 c_{A,B}=B 且 c_{B,B}=B 那么就没救了。否则 c_{B,B}=A。我们先给序列中插上若干个 B，然后两个 B 之间可以插入零个或一个 A。

然后再看 c_{B,A}，如果 c_{B,A}=B 那么就没救了，答案为斐波那契数列。如果 c_{B,A}=A 那么相邻的 A 填什么都可以。答案为二的幂次。

然后就做完了吗？我们再看一看数据范围，$n\le1000$！ 所以我们绝对不能写 $O(n)$ 的递推，更不能写 $O(\log n)$ 的快速幂。 于是，求解 $c_{B,A}=A$ 的那个的时候，我们竟然发现 $f_n=\sum_{i<n} f_i$！于是 $O(n^2)$ 搞定。 **方法二**：对于一道操作数为 $n$（或 $n-1$） 的构造题，将其构造步数限制设为 $c\times n$，其中 $c$ 可以为 $>1$ 的正整数，或者设为 $O(n\log n)$。 例子是我和 black_trees 的一道构造题，但是不方便公开。应该有部分人看到过。