最近在忙很多事情，抱歉很久没更新了。刚才抽时间上网闲逛，在reddit上看到了一个叫做The Hoeflin Power Test的网页，里面的大多数题目都是我从来没见过的、题目描述简单的、一般性极强的数学问题，无聊时从里面找一两道来，足以打发一整天的时间。从这个网站出发，我还顺藤摸瓜地找到了其它一些有如天书般的智商测试题目（尤其是那个图形测试），据称是专门用于测试最罕见的高智商人群的，足够大家在这个周末折磨一下自己了。
Strict Logic Sequences Examination - Form I 数字规律1
Strict Logic Sequences Examination - Form II 数字规律2
Strict Logic Spatial Examination 48 图形规律，有3页
eMiT 类比推理
查看更多：
http://www.eskimo.com/~miyaguch/hoeflin.html
http://www.iq-tests-for-the-high-range.com/
大学生活混起来很快，不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆，因此今年我主动去报了名（上次是被人给拖去的）。今年有点装怪，题目数量不变，但时间缩短为4个小时。原计划是从8:00做到12:00，结果可能是因为我们所在的7号机房迟迟没有开门，时间临时改成了8:15到12:15。总的来说，今年的题目比去年要糟糕得多，但也不乏一些精彩的题目。
和去年一样，第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁，我猜不少队伍都卡在这儿了吧。
后来我完全打翻前面的全部思路，猛然想到了一个具有决定意义的想法：街道的选取唯一地决定了整个路线。例如，假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的，其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此，我们可以用排列组合直接计算出答案来。向上走的路是五选二，向右走的路是七选三，向下走的路是四选三，向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是，计算所有的路线数只需要从小到大枚举拐弯的次数，每一次计算都是常数的，总复杂度是O(n)的；整个算法的瓶颈反倒是O(n^2)的组合数预处理，不过这个复杂度完全可以承受。
今天我又干牛B事情了……听说三教有Google的实习生招聘笔试，再想到传说中Google笔试里的牛题，我毫不犹豫地就杀去了。说实话，我倒真没想认真做题，只是过去看一看传说中的Google笔试题是什么样子的。由于我什么都没准备，连事前是否要报名都不知道，因此呢，与其说是“处女笔”，倒不如说是一次“霸王笔”。BBS上说要带简历和成绩单，于是打印了一份巨牛无比的“简历”和很不像话的成绩单。
考试时间19:00-20:30，来自各个学校的人几乎坐满了整整一层楼的教室。两个挂着工作牌的MM进来，给每个人发了一张质量巨好的草稿纸和一个用来把试卷、简历、成绩单固定在一起的曲别针。试卷很厚一叠。选择题很简单。编程题没看（最讨厌在纸上写代码了）。算法题很有意思，和大家分享一下。
说有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[i]个空间，储存计算结果则需要占据O[i]个空间（其中O[i]<R[i]）。问怎么安排这n个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。
比方说，m=14，n=2，R[1]=10，O[1]=5，R[2]=8，O[2]=6。在这个例子中，我们可以先运行第一个任务，剩余9个单位的空间足够执行第二个任务；但如果先走第二个任务，第一个任务执行时空间就不够了，因为10>14-6。
这个题到底该怎么整呢？我当时花了全部的时间去想各种网络流、费用流、图的分层思想等等，最后写了一个铁定错误的贪心上去。直到考试结束4个小时以后我才想到了正确的算法——只需要按照R值和O值之差（即释放空间的大小）从大到小排序，然后依次做就是了……想到这里开始暴汗，有时候最简单的算法往往是最后才考虑到的。
好了，不多说了。最近期中，可能更新慢一些。明天一早考数理逻辑，赶紧抱佛脚。
摘录几道题目。
计算1·2^2 + 2·3^2 + 3·4^2 + ... + 19·20^2
原式 = (1^3 + 2^3 + ... + 20^3) - (1^2 + 2^2 + ... + 20^2) = 44100 - 2870 = 41230
求2^x = 3^y - 1的所有正整数解
x=1时(1,1)是一个解；当x>1时，方程模4后左边永远等于0，右边则是(-1)^y - 1，可知y为偶数。令y=2z，那么有2^x = (3^z - 1)(3^z + 1)，这就要求3^z-1和3^z+1都是2的幂；但它们只相差2，因此它们只有可能是2和4，于是z=1，即原方程的另一个解为(3,2)。
圆周上有2008个点。选择两个点连成一条线，再选另外两点连一条线，这两条线段相交的概率为多少？
给定四个点，在三种连接方案中恰有一种会发生相交。取遍所有C(2008,4)种组合，相交的总情况数总是占了1/3，因此所求的概率就是1/3。
昨天的，一题滑动窗口，二题O(n^3)的DP。三题是二维线段树？ 大家说得对，三题用线段树套平衡树显然更简单、更科学。
四题显然应该是先二分k，关键是怎么检验？我的做法是枚举交点Pi，枚举圆Cj（Pi不在Cj上），然后找出Cj上的所有交点所能产生的弦的中点与Pi的连线的中点，对它们进行检验。如果是三个圆交成一个空心的“瘪三角形”区域的话，画画草图就能明白我这样做的理由，关键是圆多了的话不知有反例没。结果最后没调出来，搞了半天就把一二两题做了。后来一想也就算了，反正第四题这么做也没啥根据，估计是错的。
今天下午的，一题垃圾题，二题纯计算几何，三题二分加网络流？
四题是个科学题目，O(根号n)的算法：先预处理数组f[d][r][s]，表示后一半有d位数，模k余r，数字都在给定集合内，数字和为s的情况有多少种。然后枚举前面一半，直接查表累加就可以了。代码不是一般难写，要处理很多特殊情况。我已经N久没写过这么麻烦的代码了。最后还是写垃圾了，效率居然比暴力还慢，不知道是不是哪儿写错了。谢wywcgs提醒，算法错了。即使只处理一半的长度，k仍然巨大无比。 刚才在路上突然想到了（其实最初我也是这样想的，后来做着做着就忘了这个细节）：正如网友Zero所说，这道题目可以分情况套用两种不同的算法。k较小时用上面的算法没错，当k的长度超过y的一半时可以直接暴力枚举k的倍数，复杂度仍为O(根号n)。
几乎都是科学题目。算法大概都知道，就是写代码的能力太差太差了啊。
我把题目搞丢了，麻烦哪位给一个比赛题目的链接，谢了。
Update: 感谢网友dahe_1984提供两次比赛题目的链接：
http://hi.baidu.com/one%5Fperson/blog/item/ef8d0d4ce0d952fcd62afc35.html
http://hi.baidu.com/one%5Fperson/blog/item/4d211e23db8ddd4b93580737.html
小学四年级数学 第二学期期末测试题
(时间：90分钟 总分：100分)
一、直接写得数(每题0.5分，共10分)
32.8＋19＝ 0.51÷17＝ 240÷30＝ 1000×0.8＝
3.06＋0.2＝ 0.67＋1.24＝ 8×125＝ 7－6.28＝
8.2－0.01＝ 99×23＝ 50×4＝ 5÷1000＝
0.42＋9.5＝ 65×25×4＝ 0.08÷100＝ 10×0.5＝
1.82－0.63＝ 4.5＋1.5＝ 1－0.63＝ 231－99＝
二、填空(每空1分，共15分)
1．一个数，亿位上是6，百万位上是4，十万位上是5，千位上是8，其余各位上都是0，这个数写作( )，读作( )，最高位的计数单位是( )．
2．三百二十三亿六千八百七十万，写作( )，改写成用“亿”作单位的数约是( )．
3．25米60毫米＝( )毫米
4．3.45平方米＝( )平方米( )平方分米
5．150分＝( )时( )分
6．15吨60千克＝( )千克
7．自然数和0都是( )数．
8．在
、
、
、
这四个数中，最大的数是( )，最小的数是( )．
早晨7:40的闹铃。到36楼下面见到了我的两个队友后，随便吃了点东西就出发了。
计算中心门前特别热闹，N多人围在一张大桌子前，好像是在签到。我挤进去找了半天发现没我的名字，名单上全是信科的人。我抬头问，中文的在哪儿呢。一个美女姐姐用手指了远处的一个几乎没人的地方说“中文的在那边”，并说了一句“哇，中文的呀，太牛B了”。我顺着她手指的方向望过去，另一张小桌子前面贴了“中文”二字，桌子后面没有人，估计是交给了旁边负责数院和元培的人，让他们顺便管一下。从我目前所了解的情况来看，那张桌子应该是特别为我准备的，它在历史上很可能是第一次出现。
第四题是做得最顺利的一道题。我把所有题粗略看了一遍后，首先决定就想这道题。题目描述巨简单，就是问你沿对角线把一个正n边形剖分成三角形和四边形有多少种方法。上图显示了n=5时所有的10种方法。熟悉组合数学的人都知道，三角形剖分方案对应的是Catalan数列，其递推公式的推导相当经典。设C(n)表示凸n+2边形的剖分方案数，枚举底边和哪一个点相连（下图左），容易看出C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)。
现在，如果剖分中允许有四边形的出现，又该怎么办呢？看看数据规模n≤5000，估计应该是叫我们寻找类似的递推公式。容易想到，我们可以枚举底边与哪一个点相连构成三角形，统计出底边属于某个三角形的剖分方案T(n)=ΣC(i)C(j), i+j=n-1；再枚举底边和哪两个点相连构成四边形，统计底边在一个四边形上的剖分数Q(n)=ΣC(i)C(j)C(k), i+j+k=n-2。但是，枚举四边形需要O(n^2)的时间，这样的话整个程序就是O(n^3)的了，n=5000绝对超时。那怎么办呢？两分钟后，我想到了一个具有决定意义的点子：计算Q(n)可以直接利用以前算过的T(i)。枚举四边形的两个顶点时，固定四边形的左边那个顶点，你会惊奇地发现右半部分的所有情况加起来正好就是一个T(i) （上图右）。因此，ΣC(i)T(n-i-1)就是我们所需要的Q(n)。
一个有趣的细节是，这道题要求选手输出结果除以2^64的余数，不知道会不会有人想不到这个该怎么处理；事实上只需要直接用64位无符号类型来运算就可以了，超界了后计算机储存的本来就已经是2^64的余数了。
Matrix67 |
2009-12-25 19:57 | 
