看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？
1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。
Solution:
1. 遍历链表，给每个元素赋一个0到1之间的随机数作为权重（像Treap一样），最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍，然后从后往前再扫一遍。也就是说，线性时间构造两个新数组，P[i]=A[1]*A[2]*…*A[i]，Q[i]=A[n]*A[n-1]*…*A[i]。于是，B[i]=P[i-1]*Q[i+1]。
突然想到，给别人(MM?)介绍信息学时，用这两道题当例子挺合适的。
订阅这个Blog的人可能不止OIer，或许有一些喜欢数学谜题或者智力游戏的人。Google US Puzzle Championship即将开始了，不知道是否有人感兴趣。
四道测试题已经发布，我翻译一下放在这里。
================= 我是性感的分割线 =================
Puzzle #1 – Arrow Sudoku
数独加强版：每个圆圈里的数必须要等于对应箭头标识的路径上的数之和。
Puzzle #2 – Card Trick (Cihan Altay)
14张写有数字的卡片放在了3×3的格子里，每行每列的数字之和已经给出。拿起其中两张卡片，放回格子中的任意位置，使得六个总和相等。
Puzzle #3 – Point Pairs (Cihan Altay)
用13条直线段将图中的点成对地连起来，使得这些线段的长度正好是1到13中的13个数。每个点只能用一次；线段与线段间可以交叉，但线段上不能有其它点。
Puzzle #4 – First Name Basis (Shawn Kennedy)
把上面的16个名字放在下面的格子中（每格放一个字母），使得每一行、每一列恰好出现一个名字（中间允许有空格出现）。
下面的例子演示了有12个单词的情况，其中横向的单词为WOOD, INCH, LATE, PUN, TERSE, STEW，纵向的单词为WILT, NAPS, OCTET, OUR, DENSE, HEW。
================= 我是性感的分割线 =================
这些题的答案都还很“正常”，第二题除外。第二题的答案打死你都想不到：把右边的1覆盖在下边的2上，把左上角的9当成6放回去，这样所有的和都是27。