你能想到的最奇妙的算法题是什么

一个有趣的话题是：提起那些最巧妙的、最离奇的牛B算法时，你想到的第一个算法题是什么？

我第一想到的算法题是那道经典问题：n个数中有且仅有一个数出现了奇数次（其它数都出现了偶数次），如何用线性时间常数空间找出这个数。解法也只有一句话：从头到尾异或一遍，结果就是要求的那个数。该问题的加强版也异常牛B，我曾经在这里介绍过。不过，这个算法我在茶余饭后已经聊过无数次了……

脑海中出现的另一个牛B算法题则是POJ3318：给你三个n*n的矩阵A、B、C，问你A*B是不是等于C。数据保证O(n^3)铁定超时，因此你需要想一个不用把A和B乘起来就可以验证的算法。一个基于概率的算法是随机生成一个n乘1的矩阵R，然后判断A*B*R是否等于C*R，而前者相当于A*(B*R)，与后者一样都可以在O(n^2)的时间里算出来。如果算出来的结果相等，几乎可以肯定A*B和C也是相等的。

还想起为高中参加省选的孩子们准备模拟题时挖到的一道可称之为“脑筋急转弯”的算法题：给你一个数列，一次操作是指将某个数移到数列中别的位置上去，然后问最少要几次操作才能让数列变得有序。例如，数列7,1,3,2,6,5就只需要三次移动，把3移到2后面，把5移到6前面，再把7移到最后面即可。当时居然只有一个人想到，这题其实就是一个最长上升子序列问题。因为整个操作过程实质上可以等价地看作是，把要移动的数先全部取出来，再挨个放回适当的位置。这就要求取出要移动的数后，剩下的那些数本身是有序的。若希望要移动的数越少越好，那也就等于说是剩下的不动的数要越多越好。

最近准备一次演讲，翻出了一道旧题，觉得讲起来会相当有意思。当时和BY分享的就是这道题。问题从一个简化版开始：给定一个图，你有一次机会将某条边的权值减半，用O(n^2)的时间求最短路。很多人可能会在第一时间内开始思考，把这次权值减半的机会用到哪里最合适呢？一个明显有欠思考的猜想是，用在边权最小的地方，因为这可以让它更小。事实上，把它用在边权最大的地方显然赚得多，不过问题是，有可能这个边权又太大了，最短路根本就不经过它。一个折衷办法就是，把权值减半的机会用在原图的最短路中的最大边上。这下看上去似乎和谐了，但稍加思索不难发现反例：S到T有两条路径，一条要走99条长为1的边，另一条只需走一条长为100的边。把权值减半的机会用在那条大边上显然更好。

这题的正确算法呢，其实也不难，预处理S到所有点的最短路，以及T到所有点的最短路，然后枚举每条边，可以直接求出将这条边减半后必须经过该边的最短路（将这条边减半了又不走这条边的人肯定有毛病）。这样，枚举得出的最小值就是我们所求的最短路。

有趣就有趣在，如果你有k次选一条边令其权值减半的机会，还存在多项式的算法吗？注意，我甚至可以把这k次机会重复用在某些边上，让其权值不断折半。又一个有趣的讨论是，把上面的算法重复套用k次可行吗？换句话说，该题是否具有最优子结构？不见得。下图就是一个反例：k=1时走下面最好，k=2时反而走上面更好。原因就在于，在同一条边上反复减半会越来越亏，还不如把机会分散用在几个权值本来不大的边上。

到底该怎么办呢？其实这题有一个非常巧妙的O(n^2·k^2)的算法，真不知是谁想出来的：把原图分成k+1层，从0到k分别标号。上面的层到下面的层有很多单向边，每条边都和原图上的某条边相对应，跨越了几层权值就打几次对折，表示我“走了一条权值减过的边”。因此，你当前走在第几层，就表示你已经用掉了几次减半机会。在这个有O(nk)个顶点的图上做最短路，其结果就是我们所要求的。

看来，除了几何问题以外，在算法中也有把2D扩展到3D的诡异的思想。图的分层思想很有用，在很多其它问题中也有类似的做法。

BY与我分享的则是这样一道题目：在1到n中选取若干个数，要求如果选了x就不能选2x和3x，问共有多少种选择方案。例如，n=3时答案为5，这5种选法分别为{}, {1}, {2}, {3}, {2,3}。我想了很久。BY提示，是动态规划。我又想了很久。BY再提示，是带状态压缩的动态规划。我又想了很久，并且觉得越来越不可思议。后来BY宣布答案，两人立即大笑起来：把数字1放在方阵最左下角，然后不断在一个数的右边填上它的两倍，在其上方填上它的三倍。问题就等价地转化为，在方阵中选取若干个格子使得任意两个不相邻，求有多少种选取方案。这是一个经典的带状态压缩的动态规划问题。另外，遇到尚未出现过的数（即除2和3以外的素数）就再开一张新的表，然后用乘法原理把它们各自对应的方案数乘起来就是了。例如当n=20时，最终答案就等于下面这7张表各自所对应的选取方案数的乘积。

这题也许还有组合数学方法，但下面这个加强版估计就只能这样做了：如果再给定一些不能选的数，则又有多少种选择方案。