16-05-10 11:43 施工完毕

Day -1

接上面GDOI2016游记的离别

在火车站和大部队分开后，就剩我、CZL和姚老了

接下来是坐21小时的卧铺上帝都

于是在嘀咕着买吃的

周边跑了快十家卖方便面的才买到合味道（姚老特意要这种的我也是很不解

然后进站

恰逢五一回程高峰，人流量各种爆炸

然后就登上了绿皮火车（16:30）

接下来就是漫长的21小时的路程了

有点紧张，也有点好奇，前方就是未知的旅程

1 Hours：听姚老各种吹水

2 Hours：听姚老各种吹水

3 Hours：听姚老各种吹水

4 Hours：

拿出手机上网，然而3G怎么那么慢啊

试了试4G，诶居然扣的是普通上网流量

劲啊（之后我就全部4G了

5 Hours：

诶诶诶火车上怎么也有熄灯这玩意

被强制拉进梦乡，然后就在梦中开过了长沙和长江（擦我都想看看啊

起床的时候到了郑州

靠站的时候准备下车买烤玉米，然而忘了带钱包，回去车上拿下来后发现乘务员大叔跑不见了。。。

这才一分钟啊。。。

然后继续开，经过了石家庄，周边的风景渐渐从麦田转成了工厂

而且，天居然还是蓝的？！

这时候姚老也拿到APIO练习赛的账号了

看了第二题的题面，想了一个小时，想出来的解法都觉得好虚啊

后来看了CV群的题解，擦这样复杂度是有保证的我居然没想到

用着姚老的Win平板敲代码，然后交上去，WA

CZL也用他自己的本子敲了出来，还没交就被我拿过来对拍，然而对拍了20+分钟都没出错……

擦难不成我们错的是同个地方？！

写暴力对拍，诶怎么也是没错啊

…………感觉有可能到帝都时还是拍不出错来

要不换种方式写暴力？之前是直接随机输出0到9，这次换成随机n然后每次输出一个数字？

然后就拍出错了，擦前导0的锅，改完AC

最后，晚点一个半小时，也就是我坐了22.5小时的火车，终于到帝都辣>.<

（体验过一次后就不想坐长途卧铺了好无聊

……进地铁要安检啊，人也比广州多好多

跑到了二环内的一个宾馆，就在天坛隔壁（乾隆宾馆，这名字听起来就瘆的慌

房间小得可怜，但还是能睡的。。。

安顿好后跑到天坛，然而太晚了进不去

就跑到附近吃炸酱面+烤鸭了

顺便约定好明早去隔壁喝豆汁，听说很难喝

嘛吃完直奔天安门广场

第一感觉广场好大天安门好小

去的时候是傍晚，居然已经有人在坐着等明早升旗了

绕了一圈（被强制排拍了好多照片后

跑到大栅(zha)栏，和CZL在入门口买了StarBucks（

擦不就是步行街啊

于是就逛了一晚上步行街

被姚老各种拉去看衣服看鞋子看吃的。。。

感觉就像是被女票拖去逛街的感觉（然而并没有

于是就和CZL谈起了如何找女票的人生经验

（谈着谈着感觉我经验丰富啊（然而还是单身狗

找到了八大胡同，然而看起来感觉就像城中村

嗯并没有被开发成景区，历史痕迹依旧有，而且和当代人的生活融入到了一起

这才是真正的古韵嘛

擦居然有老北京酸奶，早知道不买StarBucks了摔

也没买什么纪念品给妹子

然后步行回宾馆

擦宾馆的厕所门是坏的！关不上！那么我们可以来嘿嘿嘿

在宾馆玩OsuMania十分来劲

睡前用iPad码子，码好了GDOI2016的游记

凌晨3点半睡觉（打破在外熬夜记录

Day 0

早上8点起床，出发报到

CV群里直播喝豆汁

豆汁还挺便宜的才一块半

端了过来，看起来像是黑芝麻豆浆啊

然而离得很远并没有闻到什么味道。。。

靠近闻闻，哇那味道好迷啊（呕

喝了一口，哇那味道好劲啊（呕

说不上来那蜜汁味道，好险一开始没喝那么多，要不然就是一嘴喷了出来

感觉就像变质食品

后来也没喝几口（然后就从旁边拿了个空碗假装自己喝完了

后来才知道豆汁是发霉的绿豆做的（这不是跟臭豆腐一样的原理么

坐地铁去昆泰，东湖渠下地铁后才发现还要步行3+km。。。

这么远要死啊，打的打的

到了昆泰，哇塞五星级酒店诶（乡下人的第一次（兴奋

报到的时候怎么志愿者知道我叫KPM。。。

擦下午试机啊（八达岭泡汤

擦主办方打乱房间的啊说是促进交♂流（然后我就和dwjshift住在一起了（膜省选rk2爷

擦房间浴帘是坏的（洗澡的时候就可以深♂入♂交♂流了

擦冰箱里雪碧和可乐一罐25，你怎么不去抢钱啊

擦一瓶矿泉水70，你怎么不去抢钱啊

啊床好软（躺

然后ztr跑来面基，跑到楼下1110面基yjq和吴彦祖队长（yjq好帅啊⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)（⁄吴彦祖队长也是啊⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

下午就去80中试机了

擦酒店怎么离学校辣么远啊1.5km走过去要20分钟大概（脚软

感觉办公楼楼上的电脑室各种高大上啊

试机虽说能联网可是明天比赛的机子是随机安排的啊，擦那我就不能把那长长的配置文件扔进去了QwQ

那我还是终端一波流吧，加个Gedit应该就好了

搞交互题，在zhouzixuan大爷的指点下懂得了正解，然后掌握了正确的交互题编写调试姿势

CZL十分悲剧，因为他并没有用过NoiLinux

试机完去食堂，诶酸辣粉好评！

感觉这次吃的挺不错啊（就是太远

吃完走回去，脚已软（以后考虑坐Taxi去好了

CV爆照活动，跑去yjq房间偷拍照秀手速玩Osu感觉十分来劲

晚上几个毕业了的师兄来各种吹水

啊都是拿了几块ACM金牌的（虽然没Claris神

现在工作了，听年薪就觉得十分可怕（百万级别

感觉自己的姿势水平还不够啊

为啥他们都说Google面试容易且辣鸡啊

长跪不已

还听他们扯了很多，信息量太大我十分害怕

扯到凌晨才走，然后也就睡了

Day 1

早起去学校，和六中两位爷搭的士去学校（终于不用走了

什么鬼啊这礼堂居然没桌子那我怎么打音游啊

诶怎么这么多人都翘课了啊

早上讲了提交答案题和AI搜索策略，都是些smg啊

前者基本没用好吧，后者还是有点用处的，加深了对蒙特卡洛搜索算法的理解

然而全程基本上都是半睡半醒（另类补眠

然后负责人登场了，将一天两节讲课硬生生拆成三节，说是中间有家长会

辣鸡安排啊这，晚上翘课翘课

中午拿饭票去换了几杯饮料，感觉劲啊

下午讲密码学。。。晚上翘课翘课！

回到房间发现有位不明人士抱着本笔记本和dwj在一起

偷看了下笔记本，擦是ioi爷啊（怎么也那么帅

围观ioi爷写代码，感觉各种高大上啊（你怎么vim得那么熟练啊

APIO同性交易群里开始有人诈称点名了，切我才不信

自己也去群里钓鱼了一发

然后还跑去ztr的房间修电脑（CV修电脑群

明天比赛啊，晚上就看了下板子，感觉十分无趣

感觉一整天都好无趣啊

那我们来看看番吧

因为宾馆辣鸡网络，于是大胆开4G流量看番

看完暗杀和坂本就睡觉了

Day 2

和各位大爷去比赛啦（十分害怕

擦A类选手居然是在图书馆。。。好挤啊

没地方放草稿纸放题目十分坑爹

插头就在眼前我喝个水都胆战心惊

左手Emacs右手Vim，怎么大爷都这么劲啊（辣鸡选手只会Gedit

开考

看了眼A题，诶感觉可以DP啊，这路绝对不会错

数的范围挺大的，离散化一发

啊公共部分还有一段段的，也都离散化，然后把点看成一小段就行了

设 $F(i,j)$ 表示第 $j$ 个人取的数在第 $i$ 段的方案数，$F(i,j)=\sum_{a<i,b<j}F(a,b)$

等会，一大段的转移要怎么搞，$F(i,j)=\sum_{a<i,b<=j}F(a,b)$？

这样会重复啊……

枚举段 $a$，然后组合数学搞一波吧，$G(i,j)$ 表示包含段 $a$ 的第i个人取了数，且 $j$ 个人取了的方案数

那么 $G(i,j)=\sum_{a<i}G(a,j-1) \frac{n-j+1}{j}$，除法用逆元，然后每段弄出 $G$ 再去计算 $F$ 再去计算下一段的 $G$。。。

循环一下就好了，复杂度 $O(n^3)$

诶 $n=500$。。。写啊不虚反正复杂度不会取满

然后就过了，花了1 Hour

诶接下来4小时2题，不虚啊

看B题

擦什么鬼，能贪心么。。。子树先相等距离然后递归上去？

貌似可行啊，每次取个中位数

等会……边不能为负，那么我们要维护个凸包？！堆+启发式合并？

一边想一边码，但是感觉这样做自己的思路不清晰啊，即使是正解我也写不出啊

还是换种思路吧，然后就在树DP的路上越走越远……

直到2小时2题……算了我看C题去了

感觉30%容易得啊，每次找最小最大去掉就行了，写完先交

然后70%的……感觉还是挺难的，想来想去没思路啊

等会……它只求差最大值啊，那么有没有办法能不用得到全部数值就能得到最大值呢？

思路正确，接下来就容易了

答案首先肯定是正整数嘛，设为1然后倍增一下

我们先全局找最小值作为起点，设为 $a$，答案设为 $A=1$

重复查找，若 $[a+1,a+A]$ 有的话就 $a=mx$，没的话就倍增：$[a+1,a+2A]$，$[a+1,a+4A]$……

找到了之后 $A=mn-a,~a=mx$，继续重复

貌似能行

等会……$n$ 太小的时候次数依旧要搞60+次啊（因为A初始为1

啊那么鸽笼原理来一发？初始时 $A=\frac{mx-mn}{n-1}$

居然过掉了！？今年的题比去年难啊，两题200，Au不虚啊（那就浪了

评测机到后面已经从ioi赛制成oi赛制了摔，延迟巨大

然后B题到最后也没写出来，浪啊浪啊最后五分钟写暴力

脑子当机，居然没想出第二部分分19分解法……（傻×DP啊（脑子！我要脑子！

算了，Au稳了就不理了

最后100+7+100=207

感觉十分劲啊

出来立刻登Q发题（CV志愿者

问了下各位大爷的，YJQ劲啊226多我B题19分暴力分，ioi爷ztr爷都挂了

还有人比较晚提交的，并不知道测试结果……惨

下午讲题，擦B题正解是啥，闵可夫斯基和？！（后来想想跟我之前的想法很接近啊，维护凸包，然而就是不会

发现C题解法和讲题人的不一样，就跑上去吹水了一发（貌似没人认识我啊QwQ

YJQ后来也上去了，全场报以热烈的掌声（帅啊

回来的时候十分开心，考之前看了太多的大爷了，感觉顶多Ag滚粗啊，结果还是稳了

（因为A,C题都是胡搞题？胡搞题欢喜

回去yjq房间玩，顺便一起叫外卖

卤肉饭好评，yjq点了回锅肉，然而肉呢（噗哈哈哈哈哈哈（跑

看yjq十分苦逼地写稿子（感觉自己已经成为了yjq的脑残粉了QwQ

和基友通了发电话，在房间趁dwj不在还和妹子用宾馆的电话聊了两个小时

感觉心情好好

洗洗睡了，明早还要打pku校赛呢

Day 3

早起喝了杯麦片就下楼了

擦地铁要转四次坐五条线，帝都地铁十分劲啊

到了北大装成学生混进校园

报到的队伍好长啊，然后就拿密码条进考场了

对面是策爷的队伍（话说这次没气球啊，期待--

yjq看前面的题，我看中间，ioi看后面

我看了眼E，妈呀这题目背景和GDOID1T4不是一样的么，不看不看（心里阴影

看F，水DP啊劲啊

这时候yjq已经把A题给切了，ioi卡J题

帮忙把J题看破后B题也被ioi切了

我上去把F题写了，交，WA？！啥？！

发现子集有多种取法的时候会炸，啥这怎么玩

后面的我就不记得多少了，反正就是ioi和yjq轮流切题，好劲啊

继续看F题，顺便口胡了下I题解法，ioi敲完发现Wa了，阈值问题？（然而后面爆OJ交了40+次还没过，想了想应该不是阈值问题

F题死活搞不出重复要怎么减掉……

只不过yjq和ioi搞得好劲啊，那我就专攻F吧

（然后我5个小时全程搞F题

午饭居然组委会有包，KFC啊（没报名费结果还送吃的好良心啊

期间猪猪侠来逛了几次（猪猪侠好帅啊

然后最后7题，rk11，我一题都没敲出来QwQ

口胡能力++

最后被姚老拐跑去逛了圈北大，然后再次坐地铁回去（没错又是换4次站（yjq打车回去好爽啊

闭幕式，诶我居然是rk5啊（然而是A队里面的

yjq好劲啊直接rk1

策策策直接AK（然而是B队所以没记排名

上去拿了个Au的证书，居然还送了个Hifi耳机（回来发现音质爆炸，爽到

啊随着闭幕式的结束，APIO也就完啦

晚上去UOJ群聚，看到了吉吉吉和策策策还有跳蚤国王，以及众多集训队爷

感觉还是太弱了，相比而言

吃了一堆羊肉串和鸡翅，顺便拍了lwr的照片（表情包+1

回到房间，dwj已经先回去了，房间就剩我一个人

感觉此时的心情

十分桑心

愉快的APIO也就这么过去了，难免会难过

（然后就拉开浴帘然后浴池洗澡，羞耻++

早早睡了，明早赶飞gay

Day 4

5点半起床（擦帝都已经天亮了啊

然而今天看起来是雾霾天

才想起前几天天都是蓝的，兹瓷啊

退房的时候我才知道宾馆的长途电话是要钱的……+44支出（怨念

做专车去机场，体验了下机场严格的安检然后就登机了

然后因为机场调度，在机箱坐了一个小时还没起飞……

第一次坐飞机感觉好劲啊（然而还是很害怕

颠簸是上下颠簸加左右倾斜的（难怪会晕飞机

感觉在云上的感觉好美妙啊

（乡下人的少见多怪

平安着陆的时候舒了一口气

然后就被老爸的车载回家了

End!

省选没退役，运气还是比较好的，不用早早就去搞文化课，毕竟已经觉得有点疏远了

而且没退役的话还能继续玩编程，感觉这才是我喜欢的啊

APIO拿了Au倒是无所谓，重要的是认识了全国各地很多大爷

好享受这种交友气氛啊

6月清华夏令营，7月noi

该继续努力了。

Other:

yjq的pku校赛游记