最近在做网站测试时，遇到了需要在输入框输入 3000 字的测试用例。联想到平时聊天时经常复制粘贴一堆笑脸刷屏讨 MM 欢心的行为，不由想到了一个有趣的问题：为了输入一定数量的字符，最少需要按多少个键？
大家最常用的策略或许是， 先输一些字符，然后全选复制，粘贴到一定规模后，再全选复制，粘贴到一个新的数量级，如此反复。注意到进入全选状态（并且复制后），第一次粘贴将会覆盖掉选中的部分，第二次粘贴才会增加原来的文本长度。当然，全选复制后按一次向右键也可以消除选中状态，不过却并没有节省按键次数。因此我们规定，在输入字符时只有四种原子操作：
1. 按一个按键，输入一个字符
2. 按 Ctrl + A ，全选
3. 按 Ctrl + C ，复制
4. 按 Ctrl + V ，粘贴
昨天和老朋友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也是相等的。
去年的高中同学会上，吃完饭后大家就坐成一圈开始玩猜数游戏了。主持人自己在手机上输入一个1到，比如说500，的数，然后大家轮流猜数，并由主持人告之是猜大了还是猜小了。猜中了的那个人接受惩罚，真心话，或者大冒险，然后成为新的主持人。例如，我们班班长想了个数230。然后某男猜200，班长说“200到500”，意思就是200小了，以后的人只能猜200到500之间的数；接下来某女说“300”，美女班长说“200到300”；然后另一个MM猜250，班长回答“200到250”；然后就轮到我猜了，我说“230吧”，班长一脸坏笑把手机拿出来给大家看，说“哈哈，你猜中啦”。然后呢，我就和某个MM做了一件特别牛B的事情，细节呢就不在这里说了。
当天同学会结束后我赶回学校机房继续讲课。我提出了这么一个问题：如果我不想猜中的话，怎么决策最好？如果我想猜中的话，又该猜什么呢？这个博弈过程复杂就复杂在，这是由多个人参与的游戏，目的不是尽早猜中或者最晚猜中，最佳决策很可能既不是猜正中间也不是猜最大或最小；游戏是一圈一圈地循环进行，策略要视总人数和数字范围而定，并且很可能每个人居心各不相同。
现在，我在心里想一个不超过n的正整数t。你的任务是尽可能用奇数次猜测猜中这个数（你知道n是多少）。每次猜测后，我都会告诉你你所做的猜测是大了还是小了。你不能猜测已经被排除了的数（来消耗猜测次数），你的每次猜测都必须符合我原来给出的回答。你觉得，你获胜（奇数次猜中）的几率有多大？
动态规划的几个类似的经典模型启发了我们：设a[m]表示采取最优策略后在m个数里猜奇数次猜中的概率，b[m]表示如果题目要求我们猜偶数次，那最优策略下有m个数时获胜的概率是多少。考虑现在我有m个数可以猜，我想在奇数次内猜中。现在我猜的是数字i。狗屎运最好时，我一次猜中直接就赢了，它的概率是1/m；有(i-1)/m的情况下我会得到“大了”的提示，这样的话我需要用偶数次猜测去猜前面那i-1个数；剩余的那(m-i)/m的情况中，我需要用偶数次猜测去猜m-i个数。因此，a[m] = Max {1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], 1≤i≤m} 。类似地，我们也可以得出b[m]的递推公式：b[m] = Max {(i-1)/m * a[i-1] + (m-i)/m * a[m-i], 1≤i≤m} 。
学习使用Mathematica确实是一件好事，你可以用Mathematica非常方便地描述出我们上面的两个递推公式，不需要自己去写那些冗长的程序了。
a[m_] := Max[Table[1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], {i, m}]]; a[0] := 0;
b[m_] := Max[Table[(i-1)/m * a[i-1] + (m-i)/m * a[m-i], {i, m}]]; b[0] := 0;
计算机的图片处理技术已经越来越牛B了，很多看似不可能的东西现在都已经有了比较成熟的算法，比如无锯齿放大、抠图、智能抹除等等。但你相信吗，现在竟然有这样一种算法，它可以改变图片的长宽比，同时保持画面内容的长宽比不变！
我们经常遇到这样一个问题：源图片的长宽比与目标长宽不合，把图片剪裁一部分会觉得可惜，而拉伸图片后画面内容就变形了。此时，一种叫做Retargeting的技术或许可以帮助你：当图片长宽比改变后，它能压缩图片中不重要的部分，保持画面主体内容长宽比不变，让人看不出这个图片是被拉伸过的。
算法的原理来自这篇名为Seam Carving for Content – Aware Image Resizing的论文，它第一次出现在今年8月份举行的SIGGRAPH大会上。下面一段视频简单地介绍了这个算法，看后你会发现其实质非常简单。
YouTube链接：http://www.youtube.com/watch?v=qadw0BRKeMk
你会在视频中听到一个OIer特别熟悉的词。“从最上面一排的某个像素出发，每次只能向左下、右下和正下方三个方向移动，求出到达最底端的路径中权值和最小的一条”，这是每个OIer学习动态规划的必修课程，它甚至还出现在了前几天的某次NOIp模拟赛中（记得好像是第三题）。
最近cnBeta的一篇文章提到，这个技术已经用于实践，一个叫做rsizr的Flash网站可以实现上述算法，感兴趣的同学可以去试试。