NOIWC 2019 冬眠记 / 游记

在我的blog查看：https://www.wjyyy.top/wc2019 # Day -1 上火车了，but手机没电了。 # Day 0 中午1点左右到了广州东站。接站只有南站和机场有，于是坐了一个多小时公交车到了广二。 从公交车站看到一个钟楼，估计就是了。 走进去又看到了一个写着“NOI奥林匹克冬令营”的巨大塑料块块（？然后后面路边还有写着类似字样的旗子，可以在照片上看到。  领完东西$^1$之后在前面的板板上签了名。不过这时`广州市第二中学`已经被改成了`广州市第五中学`，就是两个横之间加了几笔？这是~~当时~~板板的全景 > $1$ 东西 指讲义（纸质版）、营员手册、狗牌、社会活动须知、餐票！、还有一个布制袋子（很小）。还不错啦。  然后布置了寝室。寝室也比较干净，就是移动信号极其微弱。在寝室里基本发不出去QQ消息，更不用说图片什么的了。 晚上参加了开幕式。气氛特别好，而且有各种各样的~~小~~视频和节目~~不知道比xysz好到哪里去了~~。并且**NOI科学委员会主席**剧透了本次WC考试的题型：我把这段话视频发在[知乎](https://www.zhihu.com/question/310159915/answer/581261780)上了。 开幕式大概在8点结束了，感觉在寝室没什么事干，就去了自习室。自习室大概有十来个？人吧，不过没坐到有电源的位置，电脑的电应该够。然后研究了半天怎么改wordpress上传文件大小之后~~今天的游记就咕掉了~~，突然想起来十点二十五要查寝，就慢悠悠地晃了回去。 寝室的洗澡水除了后座力很大以外还是很舒服的。以及南方的水并没有HB那么冷。 > 觉得加载图片非常的~~丑~~费流量费时间于是后面的部分打算尽量少放图。 ## Day 1 早餐是蛋糕牛奶_等。并且貌似早餐做剩下的会在白天被摆出来当零食。 上午是松松松讲课，讲评测系统和有关比赛策略~~并整场穿插宣传评测鸭~~。得到了一只鸭(gē)子。听到了很多故事。  下午去了第二课堂（因为看见第一课堂是量子计算。 听到了OI界的相声，并获得了很多技能： - 如何当一名合格的OI教练 - 如何系统地学习算法 - 对AC自动机的更好理解 - ~~如何量产集训队~~ - …… 反正这个老师非常亲和。感觉来第二课堂是个正确的决定，只是可能有点挤？ 下来之后看到第一课堂的课件都是全英文的，并没有想要深入了解的愿望。 食堂排队排队排队排队排队排队但是饭还是比较好吃的（，还有酸奶和水果以及~~鸽子~~鸡汤。 晚上上机，体验极差以为vim非root不能写入文件，后来发现只要自己创建一个`.cpp`就可以了。然后在20:20左右按到了键盘上的一个月亮按钮进入了莫名状态并无法退出，最后按了一下主机才恢复。 把下午理解的AC自动机实现了一下，但是锅了——绝对是题目的问题太毒瘤了没调出来——我把题看错了。 于是叽里呱啦结束了Day 1。 # Day 2 **冬眠日。** 前一天第二课堂的李建：**“授课与讨论都是大学生学了点东西觉得好玩拿来说的。”** 实锤了。 **《具体数学》选讲**：掉线一分钟，离线半小时。本来最可听的一个板块被我在定义处掉线了，于是开始摸鱼。后面的板块简直不可听，没学过斯特林数，掉线++。没学过升幂降幂，掉线++。 > 掉线max。 **字符串前沿算法**：~~听都没听过。~~重连失败。“假定读者已经熟练掌握KMP/SA/SAM”，上来就是SAM×LCT这种东西，果然很前沿。 > 掉线max+1。 上午的两个佬师都准备了小礼物，都是steam上的啥啥啥。都是别人回答完了我才看懂题意那种问题。 下午仍然硬着头皮听，~~窝AKIOI辣！~~首先是IOI2018选讲，然后讲了一些ACM的题。一开始看错题意尴尬举手还好没把我点上去。因为知识不连续所以断线重连的机会还是很多的，虽然重连上去不久又会掉线…… 晚上是~~神仙打架~~营员交流，LCA说的好啊 > 即得易见平凡，由上自证显然，留作习题答案略，读者自证不难。 > > 反之亦然同理，推论自然成立，略去过程Q.E.D，由上可知证毕。 后面的队爷疯狂TLE也没有把课题~~定义~~讲完，感觉整场在抛定义证定理。可追溯化数据结构有望成为出题人~~lxl~~新idea。 晚上在自习室复习了普通莫队。（就是敲了一遍板子 # Day 3 起晚了没人排队，但是快没吃的了。 ——早餐 以为**模拟费用流问题**讲的是费用流建模什么的。结果前面半个小时在教怎么卡SPFA？？？并安利了zkw费用流邪教。 讲了一上午老鼠栋（雾 问题。每次以为可以贪心的时候都会有毒瘤题意来打我脸。于是识趣地溜号到了第二课堂，第二课堂听起来轻松一些而且能有收获。话说第一课堂除了鼓掌简直没有任何参与感。 第二课堂讲DP的时候听到了一点点剪枝方法。**“搜索剪枝吼啊可以艹DP标算。”** 下午仍然第二课堂，听分块。结果讲了老久数列分块，就是那种可以拿线段树秒掉的，代码还比线段树麻烦一点的那个。树分块感觉还很有意思，不过扯远了又讲了一会贪心和细节处理。 最后讲莫队的时候**由于时间关系**跳了好多证明，不过还是听懂了树上莫队的大致思路。ygp佬师还是非常的有个性+持续提问。 ***大吉大利，今晚试机！*** 下发文件在 https://www.wjyyy.top/noiwc2019d0-tar 可以下到。 前面说了这次比赛一道传统一道提答一道交互，试机风格也差不多。松松松全场答疑挺辛苦的。 - T1 【省选联考 2018】一双木棋 『传』 - T2 【CTSC 2018】组合数问题 『提』 - T3 【WC 2018】即时战略 『交』 一双木棋由于写过一遍，在差不多1h15min时A掉了。（试机一共就2h啊啊啊啊 然后开始~~玩~~读提答题意，并揣摩交互题的提交方式，问了松松松说**“提交板子(样例)可以获得5分噢”**。于是才知道要交的文件是什么。 并且松松松透露了拔掉鸭子哨子的原因。并就用鸭子发出摩斯电码/二进制数码的问题进行了激烈的讨论。（？ **新年第一锅：**）松自己说的） WC2019练习赛T2第一次下发的的simulator（大致上是一般题的checker）运行不了。工作人员努力补锅终于在开场30min左右重新下发了simulator。（附带一堆副文件/辣鸡文件/std ~~据说集训队机房也锅了？？？~~ 咕咕咕离场了。明天没有第二课堂…… # Day 4 自闭日+冬眠日。 看来偶数日都会自闭+咕咕博客呢。 上午是**简单**数论。感觉自己只有pollard-rho能上线一会，并在讲原理的时候成功掉线。上午一边摸鱼一边抽到了敬业福？？？算了吧我听讲都不认真还敬什么业啊。  听课状态大致是这样的： > 睡觉前： > >  > > 睡醒后： > >  感觉数学还有好大的坑要补啊省选只剩60几天了，~~WC只剩一晚上了~~好方啊怎么办…… 而且今天没有第二课堂，于是第一课堂**强制在线**（不如回寝室////// 下午是JOHNKRAM讲课，用非常亲切的“单项式多项式”引入了生成函数。 --- 掉线一下午。 --- 期间持续鼓掌，全程复杂度$O(n\log n)$~~不论是n=30000还是n=100000不过没有n=1e18……~~然而并没有学到什么鸭。甚至还是很考数学水平的。 差不多下午6点的时候某群里出现了“OI没有出现在2019年度举行的比赛中”这样的消息，于是 > 接教育部通知，因WC尚未申报，明天上午以寝室为单位改办肯德基三人篮球赛，望周知，谢谢。 > > 接教育部通知，因WC尚未申报，明天上午以寝室为单位改办积木，望周知，谢谢。 其实就是一个有数理化生竞赛+肯德基三人篮球赛的一个竞赛清单，没有OI大家就开始开玩笑啦。 吃饭的时候领到了~~爆零~~密码条，明天可以爆零辣！ 晚上是营员交流++，这次的课题明显比Day2的要好玩很多，比如  太爽了吧…… 今天找松松松合了影，照片咕到考完以后吧。~~又骗了一只鸭子~~ 并在晚上收到了如下祝福  WC2019 RP++！ # Day 5 考试日。 CCF仍然彰显了鸽子本性。8:00开始的比赛硬是拖到了8:10入场，8:13开考。当然结束时间也咕咕咕了大约14分钟。 前面提到了这次考试有传统提答交互三种题。题目的顺序也是这样。集训队的得分分布和非集训队的得分分布产生了较大的差异，理论上是考试目的不同吧~~谁知道呢，万一是专门虐集训队选手的怎么办23333~~。 **超长的题面。** 一开始花大约半个小时理解了三个题的题意，T1有三个子问题，虽然没有绑子任务但是还是感觉非常毒瘤。 大致关系是： - 子问题(0):“简单”数数问题，对$998,244,353$取模。 - 子问题(1):去掉一个限制求所有情况下子问题(0)的和对$998,244,353$取模。 - 子问题(2):去掉所有（两个）限制求所有情况下子问题(1)的和对$998,244,353$取模。 ~~这都什么跟什么呀~~还好送了一堆暴力分/特殊点让我这个蒟蒻能够混到一点分。。一眼看出来的有28分。 T2是提答，就是研究一种新的**编程语言**，实际上是用一些指令操纵一堆计算机互相传输信息。每个计算机有两个寄存器，给出一个图指定计算机之间的关系，有连接的计算机之间可以传输信息，通过连接的数据线来传递，并且数据线上还能存储**临时**信息%*^&%&))":}"%^%^^%……这个题是有子任务的，所以方向必须正确。不过每个点有部分分的，根据运行的~~时间复杂度~~次数来给出分别$30\%,60\%,100\%$分，感觉读完题之后子任务1,2,3是可做的。 T3是交互，是比较经典的询问返回值求解问题 我自己起的）。有长为$n$的序列，每个点为0或1，且至少有一个1。每次可以询问两个非空下标集合，当集合$S$中1的个数$|S|$小于集合$T$中1的个数$|T|$时返回0，大于返回1，等于时**任意**返回0或1，并且不给出描述中的**“任意”**算法。感觉子任务中个数与询问次数都有一些微妙的关系。 ~~窝爆零了还说这么多干嘛~~ 然后花30min拿到T1的28分，看了看T2又感觉T1还有20分比较可做，于是花15min打了超 级 大 爆 搜拿到了接下来的15分。还有5分是两个爆搜，突然发现可以利用上面15分的爆搜，于是就比较轻松地写出来了，调试了一下过了~~小~~样例。 > 我这48分搁集训队是11分啊啊啊啊啊 > > 48=18+5+5+4+4+4+4+4 > > 11=2+2+2+1+1+1+1+1 > > 然而据说集训队中位数是10。 开始玩T2，子任务1是个题意理解，只要知道`node`,`read`,`write`指令怎么用就可以了。子任务2是只给一台计算机，要求输出$Fib_k\le 10^9$，一直在想怎么递推，但是就是没有想到打表。我好菜啊。 子任务3是让若干个数从1号计算机输出到n号计算机，只要找最短路就可以了。下来之后别的dalao告诉我要用网络流，瞬间慌了。_{开动我的小脑筋}一想啊，发现只有一条边连向n号计算机，最短路是对的~~网络流是什么鬼啊还得分层输出~~。 子任务4,5根本不会。图太麻烦了。 T3想了很久，想到可能是随机，但是看到了`grader.cpp`中就是`Rand(0,1);`，之前广播提示了评测时的grader是不一样的，于是放弃了这个想法。 发现了一档比较良心的部分分，保证序列为`0...01...1`或`1...10...0`或`1...1`（至少有一个1）。但是还是没有推出什么有用的结论。 于是11:14~13:14这段时间就被鱼摸过去了。 感谢CCF给我这个爆零的机会。 _{期望得分48+40+0=88} 松松松中午吃饭的时候在食堂发鸭子的**发声器官**，学校瞬间变成了养鸭场。之前因为承诺鸭子可以带入考场又担心考试传递信息所以发下来的鸭子并不能叫。 下午查分咕咕咕。Day5是鸽子节吧。说好15:00查分咕到了17:00，于是我就在太阳下等了那么两个小时。查分，比较稳，没挂。毕竟打的最低档暴力了。 不过听说有人T2高了，有人低了，可能是收代码的**锅**？凯路鸽鸽_T2命题人说可能是judger写错了，如果是这样的话要重测。Dew由于T1没写文件Au->Fe~~OJ害人啊qaq~~。 讲题的锅全部由凯路鸽鸽_{貌似去年HB省选负责人也是他}背了，T1全程念题解，T2一边讲一边补锅，T3顺势分析了一波，毕竟是一道非传统题。于是愉快地咕到了18:30。 晚上临时筹办的文艺汇演，比较良心，~~鸽~~歌舞类节目比较多，也有LCA_蔡德仁和魏精_味精的女装相声。窝上去玩了**谁是卧底**，并在最后合唱了**《难忘今宵》**，感觉很有参与感。 谁是卧底的身份牌：~~是我本人了~~  # Day 6 社会活动日。 上午~~准时~~集合，车牌号`粤AK啥啥啥`。车程1h，到达广东科学中心。很大，感觉非常可玩。就是进去的时候还要安检，感觉是在上火车一样。 比较有意思的几个是**模拟驾驶**、**模拟翻车**、**镜子迷宫**。然后就一直摸鱼了。 中午可以出场馆吃饭，并且出去的时候可以在手臂上盖个**荧光**章，可以过会再进来。_先进！ 实际上走了一上午都只走了8000-步，可能有一段时间一直在排队吧。下午回来之后还有一个小时左右可以睡觉。 然后突然看见了Ag和Cu的交界，看到一个84分的大爷。同时有人拍现场照片说1/4的位置被贴上了名字，大致算了一下1/4只可能是Au+Ag。~~感觉自己Ag稳了。~~然后有人说看到我名字了，又过了一会官方群放出了消息，看到我是一堆人中的倒数第18。 那应该差不多压线了，88分的人挺多的~~，去了之后发现左右都是~~。 然后是比较激情的闭幕式，大家都热情鼓掌????。上去领了个小破纸之后下来了。 毕竟倒数选手坐得比较偏僻，拍照效果不好~~，懒得放图~~。 dzd讲得好啊。NOI当然要用来普及计算机~~毒瘤算法~~啦！ 于是就散了。 还去食堂拿到了自己的Fe牌参赛证明。 恭喜本次WC圆满结束。 # 总结 第一次来WC，感觉在第二课堂的收获比在第一课堂高，虽说第一课堂主要是面对集训队员。不过梗大多是在第一课堂产生的，造梗的人也都是集训队员。 那么感觉自己在弱省的话还是多去参加第二课堂吧。 考试方面的话暴力打满（并稳）是有Ag的，对于T3的话，碰运气搞出一个点说不定就有Au了。 感觉mengbi的时候读题是非常有用的。并且感觉这次读题的次数还是不够多，T2的第二个点没看出来。~~别人是20->0，我是0->0是不是我赚了啊。~~理论大众分108，实际大众分88。 实名羡慕广州二中的表演。