百度之星 2010 题目篇

今年的百度之星改进了许多，比如可以使用百度的ID注册，而不需要另外再注册一个ID。可能已经受到高层关注了吧，因为之前的几次有传言说公司高层并不重视，组织比赛的人员只能在业余时间加班加点，比赛的质量也有所下降。不过今年依然没公开测试环境的具体参数，没公开复赛的具体成绩，虽然这些数据不重要，但我依然希望有“知情权”。另外中文数据还是用GBK编码，好像从第一届开始就这样，而不是用Unicode，公司内部标准？

废话不多说了，直接说题目吧：

初赛是一个对战类的游戏，给定一张地图，双方各用5辆坦克来争夺资源，先抢到一定资源的一方获胜。坦克有3种类型，Sniper、Striker和Pioneer：Sniper血少但射程长，比自身视野都要大1，于是就产生了一种策略“盲狙”；Striker攻击力强，射程一般，比较中庸；Pioneer血硬射程短，适合快速突破对方防线。常规的思路是计算坦克与资源点之间的二分匹配，在最短时间内抢到尽可能多的资源点，并沿路攻击敌人。这种模式配合Striker的攻击力，加上一点点优化，可以达到比较优的抢资源速度，但这样就用不到Sniper的射程优势了。于是有人提出了预测的算法，简单来说，大家都用二分匹配（或者某种贪心算法）的话，坦克都是以最短路径去资源点的，一旦知道敌对坦克的坐标和时间差，就可以猜对敌对坦克的坐标，只要进入了Sniper的射程，无论看见与否，可以直接射击。于是为了反预测，就要在行进过程中加入一些随机扰动，或者在预测到下一步会被击中的时候停止移动，不过这样会进入僵持状态，在落后的情况下，这样是很致命的。

由于初赛是前2000名晋级，并且我没多少时间可以用来调试算法，就简单写了一个二分匹配交了，心想应该没2000个人能写出预测的，果然晋级了……

复赛是传统的百度之星模式，两场，每场5题8小时前20名晋级。题目在这里：上/下。

复赛第一场：

1. 蜗牛：简单的DP，递推天数累加就行了，要注意的是结果有可能是大数。
2. 午餐聚会：当时没想出来怎么做，随便猜了一个规律-_-
3. 猜猜你在哪儿：一道交互题，随便搞了个带阈值的随机投点，效果一般。
4. A+B问题：在这题上消耗了起码三个小时，中文数字和阿拉伯数字互转实在太麻烦了，这题基本没难度，就是看细心程度。
5. 并行修复：没想法，也没时间写了，直接交样例-_-

复赛第二场：

1. 内存碎片：我的算法是把请求按长度排序之后，划分成K部分，使得总数最小。纯递推的复杂是N*N*K，显然太大，观察了中间结果发现有单调性，可以化简成N*logN*K，不过只拿了25分，不知道哪里错了-_-
2. 购物搜索调研：具体的推理忘记了，好像是要找出一段子序列中的最小值，于是想到了RMQ，不过只拿到30分-_-
3. i-Doctor：据说是Bayes公式，概率学得不好，随便写的-_-
4. url规范化：纯模拟题，考细节的，辛辛苦苦写了三个多小时，0分>.<
5. 玉树驰援：题目很长很复杂，就没怎么看，也没做……

复赛依然延续着我做Astar的规律，不管怎么做，第一场的分数总是比第二场好，下次不参加第二场了-_-

决赛是植物大战僵尸的简化版，题目在这里。时间8小时。我上手就选错了方法，尝试去写一下模拟器，然后通过遗传算法找最优解，事实证明时间完全不够，理解题目用了1小时左右，写模拟器用了4小时，而且模拟器bug很多，修完bug就差不多快结束了，真正的算法没来得及写>.<

最终就拿到一只熊，任务完成，咱也不奢望什么:P

您还可能感兴趣的日志：

1. 百度之星 2007 决赛
2. 百度之星 2007 复赛
3. 百度之星 2007 初赛
4. 百度之星 2008 初赛
5. 2010
6. 活埋 Buried 2010
7. 密室之不可告人 2010
8. 人在囧途 2010
9. 从WordPress同步到其它博客和微博的方法[更新：2010/10/12]
10. 爱情公寓2 2010