全英文试卷vc++ 6.0/eclipse 3.0/jdk1.5.0_06

运行要求：

内存：64M 时间：1s

 

1.15pts 求Fibonacci数列第N项，N是0~100。F0=0，F1＝1。

  解答：这个数很大的，100的话要20多位数字，一个int是肯定不够的，多个long连接或者干脆用string做比较好。我用的是long，计算速度会比较快吧。一开始没想到数字会太大，第二题做到一半忽然想起来这个问题，连忙回去改。可惜出来就自己发现还是错了：我低位的long向高位的long进位的时候，是逢2^31进位，不是10^9进位……哎，从小都是最简单的题目会出错，郁闷……

 

2.20pts S ::== () | (S) | SS，输入一个1-10的整数n，给出所有长度为2n的字符串，即n对括号。按照字母顺序排列。样例：

input：3  output：((()))  (()())  (())()  ()(())  ()()()

  解答：这道题目最烦的地方是所有的结果到底怎么排序。英文试卷，就说是less than，一开始以为是上面表达式的三个右部按照递减顺序，但样例又不是这样完全符合……困惑了好长时间。看懂了就很简单了，这种题目我最擅长了，一个指针在一个字符串上前后跳动，只要脑子清楚，不要搞，还是很好写的。

 

3.20pts 输入年月日输出星期几

  解答：很多人是计算差多少天，但是这样不小心就会溢出。我是先算年，每年差1天，每个闰年多差一天；然后是月，各个月之间差的天数是固定的；最后再加上日，这样肯定不会溢出了。不过这题很烦的，因为月和星期几都要用英文，然后就是很无聊的switch，一大段……

 

4.20pts 1000×1000的平面，输入一个n，然后输入n个矩形（对角顶点的坐标，均为整数，n<100），求总覆盖面积

  解答：我上手就是一个int[1000][1000] ，跑一下马上告诉我overflow……。改成对每个x坐标，在一个1000的数组上标记所有矩形覆盖这个x的部分，然后累加再累加，over。

 

5.15pts 二分图最大匹配。先介绍下概念：二分图就是所有点可以分为两部分，使得所有的边的两边分别落在两个部分中；匹配就是说，一个边的子集，使得每个顶点最多只能有1条边。最大匹配么，就是最大啦。先给出两个部分各自的顶点数，然后对A中的每个顶点，依次给出相连的B中的顶点集。输出最大匹配的边数和这些边

  解答：我的做法是：对每条两个顶点都没有被占用的边，分加入匹配集和不加入匹配集，在对顶点和边作标记后分别递归调用本身，选其中匹配数较大的返回。当时的问题在于，c++里面多维数组的参数引用方法忘记了，怎么都编译报错，差点想改用java了……不过最后还是试出来了，K.O.。

 

6.10pts 还是一个图，先给出顶点数，然后给一个n×n的矩阵，内容是各顶点之间有没有边。求最大完全图的顶点数。

  解答：这题没来得及做完，据说是NP-hard的问题。我的思路是，这个结果从大往小，对于每一个x，判断度大于x的顶点是否满x个，不满就x递减。然后判断每个这些顶点在它们之间的度是否满x，最后再对大小为x的子集判断。不过万一一个顶点很多，边也很多的图，偏偏不凑巧，最大完全图很小，那效率恐怕就很低了。不过后面一部分还只是想法，每来得及写。要是给点时间的话，应该再能有些判断和优化的吧。说不定，如果边很多的话，还能证明最大完全图不会很小，不去想了……

 

还好，基本上都是算法题，没有考什么乱七八糟的库什么的，我只用到一个iostream，不然就死翘翘了。差不多应该算是对了4道半吧。普通班这边好像算是最快的了，监考如是对我说。不过同在google实习的acm班班长qwt大牛提前了一个小时全做完，差距啊……崇拜的人去那张TGIF照片上膜拜一下吧※

很久么发过了，回来了就懒了……

 

有电有网有游戏的日子，过得有点昏头了……

 

saintfish已经拿到google的offer了，还有几个别的学校的也拿到了，剩下的都在苦苦等待ing……

 

上课愈发的无聊了，除了zyb的课还有一点听头，其他老师的课都只能用来补充睡眠……

 

直研的机试K.O.了，做的还不错，可惜延续了我从小学奥数比赛开始的噩梦：最简单的题目有个bug……

 

沙发会是谁的呢？那帮天天用google TKer来tk大家space的jr？是拿到了offer很high的saintfish？还是机试做的很high的qwt？

rt