| Purple Spaz 的个人资料Purple Spaz's Nest照片日志列表 |  工具  帮助 |
|
|
2007/1/31 大学的课程和考试全部落幕了好不容易终于连上来了，真不容易，也难为我家的33.6k小猫了。
考试都没了，估计没什么问题，大四的考试还是很容应付过去的。转眼间，大学只剩下了一个毕设和相互间的bg了。再过几个月，也许就乘着北上的火车，和这边的朋友们说bye bye了……
在家闲的慌，整天除了睡觉就没什么事情做。电视没什么兴趣，电脑太破，只能勉强用来上网。真后悔没有把寝室的电脑带回家…… 2006/10/1 保研机考后记临离开学校前听到了小鱼的bg，现在轮到拿到保研名额的人了，主动点！好歹看在我没来抢你们的名额的份上！
机试的成绩还是比较满意的。错的地方么，第一题的粗心，最后一题没做，第五题算法太复杂，图一大肯定会超时。记得算法书上是有这个标准算法的，可惜是裸考，不记得了。此外大牛们说第三题很容易错，不过我还是很有自信的啦。毕竟我四岁就会口算这个问题了，可惜那时侯的算法长大后就失传了……去参加这个机试的主要目的就是为了测试下自己的实力，现在看下来，暑假里能去到google实习除了运气外还是有那么点实力因素的，哈哈~~
不过从结果看，普通班和acm班的差距还是很大的，acm班很多人都提前交的。不过真正的牛人倒也没几个。自觉自己的最大问题是平时代码写太少，只能用int来弥补exp上的劣势。如果第一第五题都做对，前面由于exp而白白浪费的时间用来做最后一题，这种连大牛都用暴力方法应付的NP问题，写个暴力方法还是绰绰有余的。这样的话，在acm班也能有前几名了。所以往后就要多练习练习啦。
最后，有人问我第二题的算法，贴一下：先建一个字符数组，内容写成“(((())))”的样子，作为第一个答案输出。定义一个指针指向最后一个字符。然后，对这个指针进行如下循环：如果指向第一个字符，就结束。如果指向一个“)”，则向左走一步。如果指向一个“(”，那么判断这个“(”能不能变成“)”：不可以的话就往左走一步；可以的话就变成“)”，然后右面依次填充所有剩下的“(”然后填充“)”，作为一个答案输出。很简单吧 :-) 2006/9/30 保研机试试题全英文试卷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照片上膜拜一下吧※ 2006/9/29 开学一周小记很久么发过了，回来了就懒了……
有电有网有游戏的日子，过得有点昏头了……
saintfish已经拿到google的offer了，还有几个别的学校的也拿到了，剩下的都在苦苦等待ing……
上课愈发的无聊了，除了zyb的课还有一点听头，其他老师的课都只能用来补充睡眠……
直研的机试K.O.了，做的还不错，可惜延续了我从小学奥数比赛开始的噩梦：最简单的题目有个bug……
沙发会是谁的呢？那帮天天用google TKer来tk大家space的jr？是拿到了offer很high的saintfish？还是机试做的很high的qwt？ 2006/6/23 总算有点明白读研的意义了今天系里开会，系里各个老师来介绍各自实验室的研究内容，准备瓜分没有找到实习的xdjm们。看了那些题目，很多都是模糊理论的那块，例如有很多中文语义分析的，像Internet信息获取之类，还有人脸识别什么的。此外还有一点是分布计算，还有一块是和ZF有关的密码破解等，主要是信息监控。其中以语义分析方面的最多，感觉跟google要做的事差不多了。怪不得小硕出去更容易找工作，相关经验比较丰富啊~~~8zd我去google两个月能不能也有些这样的经验呢？ 2006/6/16 DB2 SA果然没过fundamental和SA都是做对61%就过，前者54题，后者70题
前者关于SQL的问题都没什么难度，毕竟刚考完DB，但是关于DB2各个组件功能的题目，对我这种没有好好背的人就有难度了。正确率70%+通过~~~
后者就难多了，自己会做的+上课老师讲到的大概有20-，剩下的就只能PRP了。结果居然有53%正确率，哪来的这么好的rp……早知道对了这么多，就网上搜搜凑够61%算了……
总结：这个认证实在是没有什么意思。通过认证的办法是背题库，题库一共才100多道题目/难度，稍微背背就好了，简直没有含金量。强烈建议最多只考个fundamental，算是满足下老师，SA实在没有什么技术含量…… 2006/6/15 DB挂不掉吧这种卷子做完一点底都没有，不过应该挂不掉了。早上和大家讨论的题目也考到了，没讨论过肯定做不对……
明天DB2咋办呢？fundamental估计是不会有问题的，sa就没什么希望了……要白扔75块钱了…… 2006/6/14 形势政策考试好BT！居然出的题目都是书后面选择题里的，提前最多出一道单选里的，这次居然大量题目出现在多选里。第一遍卷子做下来，居然选择题空了快一半。然后看打印的复习资料，居然有一道大题目还空着，填空也没补上几个空，快抓狂了。还好我接下来就开始看选择题，果然答案全在选择里……
最后还有大概10个空没填上，很不爽的，那些包含很多小点的单个大空我都填满了，没填的都是些一个小点一个的小空。大空小空都是半分，so不爽。这卷子真BT！
最贱的还有ZJQ，居然要我们在卷子后面写上每次课的主题和印象最深的一句话，作平时成绩。卷子都做不完，哪来的时间跟他搞这种花头！不过估计也没几个人会写吧。
不过交卷子的时候，看见好些人填空都大片大片的空着，估计是没注意到选择题吧。算是略有些心理安慰……哎，最后一次形势政策考试，居然这么不爽……不说了，复习DB去了，不然明天就铁定挂了…… 2006/6/8 闲聊ebay上马哲课的时候，几个人闲聊，发现我们知道的ebay给offer的人中只有一个是强人，其他都是些什么技术都不懂，或者是考试乱挂科的，狂ft……最后决定bs ebay，聊以自慰 2006/6/5 网络成绩出来了03届学生的成绩计算：
平时成绩为：课内练习每次2分，交作业每章1分，超过6章（包括6章）的算6分
总成绩为：卷面成绩x 0.9 + 平时成绩
最终成绩 = Max（卷面成绩，总成绩）
序 学号 姓名 性别 课内练习 平时作业 平时成绩 卷面成绩 总成绩 最终成绩
24 5030309195 雷恒 男 ▲ 245678 8 80 80 80 数字好整齐的说……
rank 20/85，还能接受。03CS被关了12个（连缺考的），重修的一共12个过了5个……zyb果然不愧是zyb…… 2006/5/22 考试日程出来了
|
|
|
