2009-05-10 12:25| 
31 Comments | 本文内容遵从昨天和老朋友BY一起吃饭时又一次不可避免地谈到了算法问题。一个有趣的话题是：提起那些最巧妙的、最离奇的牛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张表各自所对应的选取方案数的乘积。
这题也许还有组合数学方法，但下面这个加强版估计就只能这样做了：如果再给定一些不能选的数，则又有多少种选择方案。
大家遇到的最神的算法题目又是什么呢？欢迎在下面留意与大家分享！
sf
不知道为什么第一个让我感到nb的算法是merge sort。。。
我碰到个题跟你的第一题差不多，用 n 的效率判断一堆数是否能组成连续自然数
比较nb的算法：
舞蹈链算法，http://sqybi.com/works/dlxcn/。
很nb的算法：
大衍求一术。
不知道你是否设定了链接直接删除，如果是的话我再写一遍：
http：//sqybi。com/works/dlxcn/
舞蹈链算法 ，很牛的。
喵= =。。。最后一道。。。想錯了。。。
哭ing = =。。。
喵。。。
比较菜，看到每道题都觉得很牛。。
想去听笨笨讲~~ :)
想起了Dan.Brown在[DIGITAL FORTRESS]里写的旋转明码加密算法...就为了这书疯狂地读了一遍[经典密码学与现代密码学] 以及大量的资料...
Orz那个把所有数XOR起来的题 是我同位给我讲的
第一次对XOR运算肃然起敬
在你欢迎页面上看到这句话：“永远不可能制造出这样一个机器,它可以判断任何一个命题的真假”，觉得有疑问，顺便在你这里提问了。
疑问是，那人脑算不算一种机器？人脑能不能判断一个命题的真假？如果你的这个命题是真的（老实说如果它是假的那我也就没兴趣了），那是不是说明人脑也并不能判断一个命题的真假？这在哲学上是不是意味着不可知论是正确的态度？
刚才没注意到那句话里的“任何”二字，不过疑问仍然存在：如果我们所使用的所谓真理的基础一直在被推翻重写，那我们凭什么相信我们手握的真理是可靠的？
Turing halting problem
遇到一个题目，听说是世界五百强软件公司出的：
题目：给出5组数据
A B
第一组 2481947180 874539
第二组 4130989819 785888
第三组 3472717089 508550
第四组 9140684512 986839
第五组 6111332015 805932
每组数据中的B数据是由A数据经过算法运算而得到的，请找出规律，写出算法函数B=ConverFun(A)
分享一个：给定n个数，用最快的方法找出其中异或值最大的两个数。
弦图 网络流 费用流
都很神奇吧
oier里面能把上面内容的相关定理证明出来的屈指可数
不过要说神奇的算法题
推荐一道POI的题目吧
一个n*m的矩阵，每个格子里有一个正整数A[i,j]
请你找出一个子矩阵使其权值不小于k，不大于2k（k为给定正整数）
或确定不存在这样的子矩阵
要求O(nm)
在所有m×n的扫雷格局中，求数字和最大的那一局？
那道减半的题目不就是拆点？
某博弈, 用黄金分割求解...
相当之神奇, 不由得联想起五角星, 达芬奇, 等等一系列XXYY的东东...
@14
用拉格朗日插值公式不是很简单
貌似对边减半k次的方法就是拆点最短路吧，本质上应该算是DP。f[i,j]表示到i共减半了j次，转移也很好写，写出来就看出是上面的层次图了。
喜欢匈牙利算法～
至多3[n/2]次比较，就可以同时找到n个元素中的最大值和最小值。
你说的第一个有一个巧妙的解法就是统计出每位每个数字出现的次数。最后结果的位为每位出现奇数次数的数字。
看看这个吧：
有N（N最大可为10^8）个数中，有一个数出现超过n/2次，快速找出这个数。
说起“最奇妙的算法”，我的第一反应有两个
第一个和m67牛的第一个一样，
第二个是，给出n<500000个数，其中有一个数出现了至少n/2+1次，问这个数是多少。内存卡500k。
记得这两题曾经都出现在tongji online judge上过，
另外某次sjtu办的noip模拟赛上的某题把这两题合并成一题过。
发完以后赫然发现楼上跟我说的是同一题，看来NB问题总是NB的。
我运筹学论文也打算写这个了，呵呵
平面图网络流转对应图最短路径
大巧无工，搜索题。
LSS说的是某论文里面那道吧
谢了，又是一道水题