【游记】百度之星 2019 -boshi

百度之星是由百度公司组织的一年一次的比赛，分为两项赛事，分别是 “程序设计大赛” 和 “开发者大赛”。程序设计大赛针对 (也仅针对) 在校学生 (原因可能是以前的百度之星被谷歌的员工爆破掉了)，而开发者大赛允许已工作选手报名参加。

这篇文章主要介绍” 百度之星程序设计大赛”。(因为我没参加过开发者大赛)。

初赛和复赛

比赛分为初赛、复赛、决赛三个阶段。其中前两个阶段在线上完成，第三个阶段一般在北京的百度公司内部举行。2019 年的百度之星初赛在 8 月份举行，初赛共分为 4 场，在任意一场内排名前 250 即可进入复赛，并且已进入复赛的选手不参与后续初赛的排名。因此，复赛大约有 1000 名选手参加。

2019 年的复赛在 8 月末举行。

初赛和复赛的题目都非常贴近或者说完全就是传统的信息学竞赛题目。知识点涉及贪心、Dp、数据结构等，共计 4 道题。题目难度大致随题目编号递增。

如果复赛的排名比较靠前 (比如前四、五十名)，将有机会参加决赛。决赛的具体人数由百度决定，一般是 40 或 50 个人。当然，排名靠前的某些同学可能会因为自己的原因无法前往北京参加决赛，这样排名靠后一点点的同学将会有机会 “替补” 他们的名额。比如今年决赛的名额是 40 名，我复赛考了 43 名，但是决赛的编号是 37，这就说明至少前 46 名都是可以去决赛的。

决赛

简介

参加决赛的人大致分为如下两类：现役 OIer，大学生。而且现役 OIer 中有很大一部分是当年的集训队员，还有许多低年级的牛人，比如今年就有一位初二的选手。

决赛从比赛方式到题目上，与传统的 OI 比赛都存在极大的差异。而且说到百度之星的决赛，不得不提两个字：待遇。

待遇是什么？待遇就是，外地选手需要坐火车或者飞机前往北京，车票 (二等座) 和机票 (经济舱) 的钱都是百度出的。

待遇是什么？待遇就是，百度免费帮你安排好滴滴专车，出了车站，上了专车，脑子不用动一下你就到了宾馆。

待遇是什么？待遇就是，餐厅离宾馆只有 200 米，却一定要请所有选手坐着有空调的大巴车在晚高峰的西二旗堵十分钟。

待遇是什么？待遇就是，最后一顿晚餐百度会请你吃 150 元一份的汉堡。

待遇是什么？待遇就是，在衣服上贴一张贴纸，你就能随意进出百度大楼，手上拿着王海峰 (百度 CTO) 的照片，你就能随意进出需要人脸识别的房间。

决赛的题目一般非常独特，并且只有一道题，但是比赛时间却有足足 7、8 个小时。2017 年的题目是，写一个贪吃蛇 AI，并且与其他选手的 AI 实时对战。2018 年的题目是，写一个寻路 AI，在北京地图上以最短的时间从一点到达另一点。2019 年的题目是，写一个图调度算法，优化可并行算法的执行时间。可以看出，这些题目与传统 OI 题目完全不同，并且能充分体现选手的实现能力和对算法的应用能力。

这些题目的目标非常简单，并不像传统 OI 题一样有着复杂的题目背景，需要完成一个非常特定的任务。这些题目完全来自实际问题，并不像传统 OI 题一样抽象难懂。但是这些题目却更加引人入胜，因为你可以用很简单的方式解决它，也可以用很复杂的方式解决它，你可以用任何你想得到的方法解决它，并不存在一个真正意义上的 “正解”。你的解决方法会通过一种非常直观的方式去评判优劣，比如 2017 贪吃蛇游戏中按得分评判，2018 寻路算法按到达时间评判，2019 图调度算法按你的调度方式下并行算法的执行时间评判。

纪实

记录一些有趣的事。

• 我的室友是 NOI2019 的第一名，zyy。

• 参加开发者大赛的选手中有的已经有孩子了。

• 比赛过程中你可以访问互联网，甚至还能刷知乎，逛 b 站，溜 github。

• 不要想着让百度大楼里的机器人不停往后走然后撞墙，因为那个机器人有超声波传感器，而且它不傻。

• 最后的晚餐上，有一个活动是画百度的那只熊。百度给每一桌发了一个白色的小熊模型，让我们上色。我们桌照着腾讯的图标画的。隔壁桌也模仿我们画了一只企鹅熊。在接受采访的时候，隔壁桌一个人拿着那只熊信誓旦旦地说：“我最大的梦想就是来百度工作…”。

• 2019 年的题目是这样的：给定一个 DAG，你需要按拓扑序执行 DAG 的每个节点。节点分为两类，第一类不能并行，第二类可以 3 路并行。你需要给出一种执行时间尽量短的执行方式。