UOJ Logo matthew99的博客

博客

NOI2016及赛前的故事

2016-07-10 22:23:24 By matthew99

退役前最后一次NOI,如果不写点什么感觉太遗憾了。

明天是湖南省队集训的第一天,地点是师大附中。基本上是上午8点到下午1点考试,下午2:30到5:00讲题改题。

记录一下每天干的事情吧。

随之而来的15号凌晨有一场CF,19号晚上有一场SRM。我当然希望能打好,但是我也知道这往往可遇不可求。UPD:19号新增一场CF紧接着SRM UPD:决定还是不打CF了

2016年7月11日

省队集训第一天。

早上去报到,接下来去机房开始考试。

这一场前两题都非常简单,第三题是一个稍有难度的数据结构题,我在考场上很快写完了前两题,第三题却做了很久,而且做法也过于复杂。

中午发盒饭在机房吃。

下午发现包括我以内的很多人都挂了第一题。

第一题的题意是这样:

定义一个置换的平方为对1~n的序列做两次该置换得到的序列。已知一个置换的平方,并且这个结果是一个排列,求该置换。

输入第一行一个数n表示排列长度,接下来一行n个数描述排列。

有解则输出一行n个数表示原排列。否则输出一行一个-1。

这个题,几乎绝大部分同学都写了一个checker检查。

大概流程是这样:

  1. 读入排列a。

  2. 用某种途径得到输出b。

  3. 检查是否有对所有i有b[b[i]] = a[i]。

这样的检查方式以及检查通过的程序都是有问题的,你们能看出为什么吗?此外,你们能否不利用a只通过对b进行简单处理使得这个checker正确?

祝贺ppfish前两题都没有挂,第三题打满了暴力并成功获得了第一名。

此外今天才知道,g++在不开O2的情况下,开了-pg选项会变慢很多。

晚上看了一些黑(xiao)科(chang)技(shi)。

7月12日

省队集训第二天。

上午考试,去的时候发现每天中午的盒饭20元,感觉可以和火车上买饭的价格比比了。三道题做法都不难,但是我却在后两题都卡了一阵子。三题都有大样例,虽然第三题大样例过了之后我依然发现我犯了一个非常厉害的错误(虽然听说数据强度和样例差不多)

最后没挂分。然后发现第三题暴力可以过85分,因为不仅树都是随机的,而且每个点的父亲编号都小于它自己的编号= =b

共价大爷第三题被卡常数了,7s时限,链的点全部TLE了,不是链的点零点几秒,虽然为什么会这样上面已经解释了233

今天早上把公交卡塞进了手机上,考完之后才发现来的时候手机掉在了车上,但是幸亏早上坐是我们家的车而不是公交车23333。

今天的第二题是,给定$n$个点,每个点的度数都有一定的限制,现在要你选择一些点构成一棵树并满足度数限制,问你总共有多少种方法构成大小分别为$1$到$n$的树。$n \le 100$。

这道题目需要一些计数能力,你们会做吗?

下午带着自己电脑过来到隔壁机房蹭网,开了一下SRM639的hard,然后发现自己最不擅长做的就是这种类型的数学题,需要分一些情况并且要考虑的很多,我发现仔细想出了很多贪心算法却一个也不会hack,后来只好看杜爷代码发现却很简单,然后发现过不了样例,接着便沦为了人眼diff选手,一阵子之后发现居然五点了!我要和tty他们一起坐车回去,赶快收好东西到原来的机房去却发现他们早就走了,感人肺腑。

晚上做了SRM640的hard。

看到几篇和本日志风格类似的日志:

http://wronganswer.blog.uoj.ac/blog/1831

http://yjqqqaq.blog.uoj.ac/blog/1827

我写这个日志,意义在哪里呢?大概也想体验一下写日记的感觉吧。而且如果NOI出现不可理喻的低级失误,这大概就是OI生涯最后一段训练和除了NOIP之外最后一场比赛,不留下点文字太遗憾了。假如进队了,那也是最后一次作为正式选手参加NOI。

关于昨天的第一题,坑点就在于题目中给出的是一个排列。

置换对排列的作用就是交换这些数的位置,也就是说比如置换的第1个数是3,那么就将第一个数换到第三个数的位置上,而不是将排列的每个值变化成另一个值,比如说把值是1的数变成值是3的数。

所以在读入排列a之后,结果是排列a的置换应该是排列a对应的置换的逆。只需要一开始对a取逆就可以了。

那么如何不利用a只通过对b进行简单处理使得这个checker正确呢?我们可以不对a先取逆,而是得到输出b之后再对b取逆,两者对应的答案是一样的,正确性留给读者思考。

7月13日

省队集训第三天。

上午看三道题,发现第二道题居然是三年前省队集训考过的题,另外两题也不难。

开始的时候做第三题,一开始一直想用单调队列+multiset但是没注意到单调性,然后想写线段树,后来才发现居然是有单调性的,于是顺利开始写了个multiset,每次取最小值并支持插入删除。

考完之后德霸哥提醒我,我突然感觉发现了世界的奥秘。

你 大 爷 , 这 他 妈 就 是 个 堆 啊

由于这是一道考察stl基础应用的好题,一开始用专业卡stl的cena测搞得我虚的要死,后来发现改成lemon了,不虚不虚。

第一题我复杂度比标算优,不过这套题年代久远,在当时标算的复杂度就已经很不错了。

noname说HNOI也出现过同一道题出现两次的现象。省选重题,省队集训重题,接下来是什么了?现在终于知道为什么去年老师要我们把历年的NOI题都做一次了23333。

下午看到成绩,第一题数据有问题,但是实测如果数据正确应该能AC,另外两题都AC了。

第一题题意是,给定一张点数$n$不超过10000,边数$m$不超过200000的图。每条边有一个权值和长度,每种长度的边都不超过30,求最小生成树的边权和的期望(注意权值和长度不是同一个东西)。

一个经典的思路是,考虑相同权值的边,将权值比它小的边缩起来,然后考虑这种权值的边连成的每个连通块,于是问题转换成生成树计数。

用$s$表示相同权值的边的数目的最大值。考虑用矩阵树定理计算出不包括每条边的生成树个数和总的生成树个数,复杂度是每次$O(s ^ 4)$,但是考虑到如果当前图中有$x$个点,那么必有$x - 1$个点被缩起来,因此很容易证明复杂度实际上是$O(ns ^ 3)$。此外,为了避免精度误差,可以找一个大于$2 ^ s$的质数(如1073741827)并在模意义下做。

由于常数小实际上上述算法已经可以AC了,但是你们能不能做到$O(ns ^ 2)$呢?

晚上颓了很久QAQAQAQAQ,最后做了个SRM642hard,是个傻逼800分,然后网络不好,交题交了很久。交题花的时间比做题长,颓的时间比交题长,令人感动。

昨天晚上做了个噩梦,梦见我打游戏被老师抓个正着,结果就醒过来了。我现实中却很久没被抓,结果果然看别人打游戏还被老师抓了。我最近整个就没效率啊。还号称可能是最后一场OI比赛,我却用这点时间在颓,表里不一不是我想要的啊。知道自己不应该颓却像戒毒一样难以停下来,简直感觉身体被掏空。

CTSC之后去准备水考,准备好好认真搞搞文化看能不能恢复到班上前几名,却也落得个半颓半学习的下场,最后成绩也不太尽人意。平时不注意就一直颓,曾经自诩“我的下午从五点开始”,颓的时间还有一辈子,搞OI的时间却只有这么一点,还是希望明天开始能少颓一点。

想起来我做过的梦,一半准一半不准,去年HNOI之前梦见自己滚大粗但是还是踩线进队,结果果然滚大粗但还是踩线进队,CTSC之前梦中进了两次队,结果梦里把两年的队进完了,NOI之前觉得NOI滚粗了也没多大事,结果就做了个梦,梦见自己NOI 500分都没上,最后被金牌线卡(当时还是认为金牌线是集训队线),希望这是把粗在梦里滚完了吧233。

我曾经天真的想在NOI之前刷完500以后所有SRM(因为从670左右的地方开始后面的场我都做过),现在看来不太现实了,要是NOI真的滚粗了,感觉整个人还是会浑身难受啊,虽然保送了我也觉得不管怎么样也还是要继续搞算法竞赛,但是那时候再做SRM心境也不同了吧。

明天晚上(准确来说是后天凌晨,但是我还是习惯说明天晚上)有一场CF,我知道只要涨rating就能LGM,但是涨rating也不是见容易事,大概不打出一个能过WC的名次还是很危险的吧。但是如果我今年(或者今年和明年)的OI想要走的更远,就应该做到每一场比赛都打好,毕竟想想最近也没打过什么比较差的名次。如果明天真的滚大粗就会成为我NOI也可能滚粗的信号弹,所以除非出现不可理喻的低级错误我绝对不会滚粗。因此还是希望我能把最近CF名次至少都不差的现状持续下去或者争取做得更好。当然光说不做假把戏,明天至少要记住我心态不要崩盘,题目看清想清再下手,争取一遍过。总之祝我好运吧!

昨天的第二题做法是,我们容易用prüfer序列证明每个点度数分别是$d_1, d_2, \cdots, d_n$的树的个数是$\frac{(n - 2)!}{\prod{(d_i - 1)!}}$,因此,我们考虑枚举每个点选不选和每个点的度数,用$\mathrm{dp}[i][j][k]$表示前i个点,选了j个点,度数减一的和为k的所有方案的$\frac{1}{\prod{(d_i - 1)!}}$之和,容易实现转移,特判大小为1的情况(答案就是点数$n$)之后最后答案就是$\mathrm{dp}[n][\mathrm{size}][\mathrm{size} - 2] \times (\mathrm{size} - 1)!$,复杂度是$O(n ^ 4)$,常数较小可以通过。

此外可以用FFT优化,但是这仅限于理论复杂度的优化,实际上速度尚不及直接暴力。另外APIO2016的第一题也可以用FFT优化,同样暴力也可以通过,只是暴力速度不如FFT优化。

7月14日

省队集训第四天。

上午三题都挺简单。第一题强行三个subtask,前两个n是$10 ^ 6$,最后一个$k$是$10 ^ 9$而$n$只有2000。第二题KMP傻逼题我不会KMP只好强行用hash上。

接着发现我、共价大爷、owaski都能AK。

最后成绩出来我们三个都喜闻乐见的自爆了。我第一题第一个subtask一个地方没取模爆了int。共价大爷第三题答案是0就会错,owaski第一题没看到$n$有$10 ^ 6$。于是挂成了295,280,260,令人感动。

我怎么又爆int了?再爆int我真的不能忍了,为什么一个取模我就是做不到。还有读入优化快速幂也是每天错一次,简直不知道在干嘛。

所以怎么避免呢,认真写当然是最好的,我最近写程序都极为不认真,这样什么错都容易犯。

还有一些人可能会想出建一个类或者加数之后取模的函数什么的办法,让程序自动取模,但是首先这样太麻烦,其次你怎么知道你哪天就忘记用类或者是函数呢?再者这也是一个治标不治本的方法,解决了这个错还有那个错,错是犯不完的。我曾经天真的觉得错误就那么多,最后每次一到大考却出现了新的错误,改完一个又一个,时间一久老的错误又卷土重来,最后什么都解决不了。

昨天我提到过第一题存在复杂度为$O(ns ^ 2)$的做法,怎么做呢?

考虑如何快速求删掉一条边的生成树个数。我们发现删掉一条边,要求行列式的那个矩阵中最多只有两行发生了变化。

那么我们可以参考策爷去年的集训队互测题《最大异或和》的做法,考虑维护消元之后每一行是由原来的矩阵的哪几行分别乘上多少组成的,假如我们要修改某一行,我们就看看这一行对消元之后的矩阵的哪几行有贡献,找到有贡献的最后一行,让后用它消去所有行,注意这样不会导致主元发生变化。

接下来对这一行做对应的改变之后,再对这一行消一次元即可。这样每次的时间复杂度降为$O(s ^ 3)$,因此省去了一个$s$,复杂度变为$O(ns ^ 2)$。

另外要注意改变其中一行之后可能不满秩,改变另一行之后却满秩的特殊情况,以及行列式交换两行值要取反,这些都比较容易处理所以不再赘述。

晚上就是CF了,一定要沉住气啊。而且明天考我的题,上午太困也没关系咯23333

7月15日

马上就开始CF了。听说19号还一场那么这一场其实只要不暴跌,问题也不大?重点是这种比赛我本来就不应该有太大的压力。

如果LGM了,终究下一场还是不太想打了,毕竟马上NOI了真的不太想最后又把这个LGM丢了,虽然我知道我很看重rating......但是还是不太放得下。毕竟自己还是有以LGM身份参加NOI的梦想,还是不希望他在自己手上这样破灭。

即使我滚粗了,只要不太厉害下一场也完全有翻回来的机会。已经没有什么好怕的了。

虽然你们可能说我立了很多flag,以及压线从来没人涨过这种奇怪的debuff,但是看看欧洲杯这次最后两场,以前某两队之间的比赛基本都是某一边赢,这次偏偏成了另一边,一切皆有可能。

考完了,不FST是可以上LGM的。F题状态不好只会三方log,最后没敢写。

考前觉得自己A不能一遍过,很认真的写完,很晚才交结果一次过pp了,觉得果然自己的感觉不一定对。

结果快下考的时候,A被hack了= =b

不过估计这场FST的人很多,我估计也有可能FST,甚至FST多题,成事在天。

A不太可能再挂了。B挂了应该还是能LGM,C挂了不知道,D和E挂了肯定不太行了。不过还是挺充裕的,但是真的虚的很啊,这场pretest太弱了。

最后没有FST,rank4,顺利LGM。难得的国家队名次,我已经拿了不知道多少次rank5了23333。claris也拿到了面试名次,rank6。(CTSC英文面试那这个如果真的有面试是不是中文面试呢?歪果仁不会说中文岂不是大家都稳了啊)

这次上LGM,喜悦当然是有,然而我也再一次知道,所谓flag都是假的。

AC五道题rank5一定会FST吗?不一定,我最近多次证明了这一点。

压线一定会暴跌吗,不一定。

对拍过的题一定会FST吗,不一定,这次我的E题对拍了也没有FST。虽然之前的对拍过的题都FST了= =b

想起了不久之前的CF345,当时我2775的rating,第一次在div1 pretest AK,心想终于要LGM了,却没想到刚下考就被人指出B是错的,我便想估计2800+还是有的。

最后的结果令人吃惊,FST了三道题,目前我听说别人CF上FST的最多几次的也就只有某一次有人FST四道题以及某几次有人FST三道题,掉了一百多的rating,那一次之后我还是收到了不少打击。

之后的VK cup,我再一次FST了一道题,从大约四十多名变成了一百多名(也就是从集训队变成了前一百的约都拿不到23333)。

上IGM之后我的rating跌宕起伏,虽然一直没有掉下过2600,但是也足够让人胆战心惊。大概人生也可能就是这样吧。

省队集训第五天,考的是我的题。

我出的模拟题,没有一套不出事故的,这一次也做好了出事故的准备,主要还是怎样应对。上次我应对得很不好——题面出现与数据不合的地方,应当改数据而不是题面,因为改数据只要我知道就行,改题面要重新通知所有人。

23333333果然出事故了。

上午他们在考试,我在这边造数据,结果发现卡了A算法卡不掉B算法,卡了B算法A算法又轻松AC了,十分感动,最后决定大赦天下各送一半分,感觉我这么良心的出题人很难见啊。

最后还是被水过去了,肝败吓疯。

讲题的时候听说我的提答题是addition chain的特殊情况,并不是NPH的,身败名裂......

下午外面风雨大作、电闪雷鸣。

7月16日

省队集训第六天。

今天的题不太可能全部考场上写完,然而我第二题被卡常数,第一题写错,第三题暴力骗了50分。

今天的题原来是给省选模拟赛准备的,仔细想想要是真的是省选模拟赛应该还是非常贴近真正的满是瘠薄题的HNOI啊(雾)

第二题是一个裸轮廓线DP,我因为被卡常数鏼了三个小时无果,因为我没有预处理转移,仔细想想这类题目,能预处理就先预处理,因为预处理不仅复杂度是稳定的,而且即使要矩阵乘法加速也很容易,可移植性强。

第一题是一个数论七合一,虽然都没什么难度,我却犯了一个傻逼错误,我以为无根树计数双重心不用处理,结果就错了,主要是当时第二题卡了三个小时没时间太急了,唉。

第三题是一个大字符串,标算代码量差不多是我前两题的代码长度的总和(也是昨天模拟赛我标程的代码长度总和的几倍233333),由于事先知道一点信息所以果断知道要跳过把题目留给另外两题了。

不得不说第二题写错真是败笔,第一题其实也很容易多过一些点的。

今天第一题的一个子问题是,求n个点的带标号二分图个数,原题$n$是1000但是实际上可以做到$O(n \log n)$,你们会做吗?

7月17日

省队集训第七天。

今天的第二题很简单,第三题是一个送分送的和水考差不多的提答题。第一题较难得分,我最后一个多小时一直在鏼第一题,写了8K代码成功拿到0分,感人肺腑。

第二题大概是一个障碍多边形在绕着地球公转,本身在自转,自转是绕着重心,太阳是一个点地球是一个圆,求某个时刻太阳照射到地球上的弧长。

有一种的做法是,算出自转角度和公转角度,将每个点绕着重心将算出的旋转角度代入旋转矩阵算出自转后的位置,接着将每个点绕着太阳将算出的旋转角度代入旋转矩阵算出公转后的位置。这个算法对吗?

第一题题意大概是要我们维护一个亲戚关系,考场上时间不够导致写代码BUG很多所以零分是必然的了,其中一个BUG特别有趣。

父亲的因为是father,母亲的英语是mother,我用fa表示父亲,mo表示母亲,写着写着就成了ma了,然后我就发现,怎么一堆的mo啊,mo不是模数的意思吗,惨啊赶快都改成ma,然后喜闻乐见,mother我判断前两个字符是否分别是m和a而不是m和o,于是我的程序重男轻女,只认父不认母。顿时感觉自己多年的英语白学了2333333

下午听说第二题没过样例都能AC,论做UR特判样例的重要性,多拿三分啊233333,事实是第二题好像,不管障碍多边形就AC咯,结果这样都没多少人AC,人没有梦想就是咸鱼咯。

以及这么多个人连重心都不会求是怎么回事啊!感觉这不是,计算几何基础知识么,应该和求面积一起学的(雾)。论看完黑书白书的重要性。

祝贺共价大爷采取了直接不做第一题的正确策略,在第二题AC之后把时间全部留给提答题,最后成功获得第一名。

昨天我提到了$n$个点的带标号二分图个数怎的统计问题。这个问题怎么做呢。我们先看看$O(n ^ 2)$的做法吧。

对于一个图,考虑它的黑白染色方案数,那么当它不是二分图时,个数是0,是二分图时,个数是二的连通块数目次幂。

考虑对所有图求方案数之和。可以考虑枚举黑点个数,那么容易得到公式$g_n = \sum_{k = 0}^{n}{\binom{n}{k}2^{k(n - k)}}$。

接着,我们用容斥求出连通图的贡献,也就是枚举一号点所在的连通块的大小。于是有公式$f_n = g_n - \sum_{k = 1}^{n - 1}{\binom{n - 1}{k - 1}f_kg_{n - k}}$。

最后考虑求非连通图,无非也是枚举一号点所在连通块的大小。于是有公式$\mathrm{ans}_i = \sum_{k = 1}^{n}{\binom{n - 1}{k - 1}\frac{f_k}{2}\mathrm{ans}_{n - k}}$。

接着考虑如何做到更优。

首先$g_n = \sum_{k = 0}^{n}{\binom{n}{k}2^{k(n - k)}}$怎么优化呢,考虑参考CZT的思路,$2 ^ {k(n - k)}$容易拆成$-2k ^ 2 + \frac{k ^ 2}{2} + \frac{(n - k) ^ 2}{2}$,于是容易展开成FFT的形式。

接下来的两个公式容易用分治FFT做到$O(n \log ^ 2 n)$。

怎样做到$O(n \log n)$呢,可以参考策爷2015年的集训队论文,一张图是由若干个连通分量组成的,因此任意图的指数生成函数可以看做连通图的指数生成函数的$\exp$,相反连通图就是任意图的$\ln$了,所以$f_n$的生成函数就是$g_n$的生成函数的$\ln$,而$\mathrm{ans}_n$的生成函数就是$\frac{f_n}{2}$的生成函数的$\exp$,只需要用多项式$\exp$和$\ln$即可在$O(n \log n)$时间内解决该问题,而二者的做法均可以在该集训队论文中找到。

7月18日

省队集训第八天。

三道傻逼题+挂了10分=爆炸。第二题加了往点数组里加了一个终点但是离散化数组没加,挂成90分。考挂自己弱没什么好说的。

祝贺共价大爷,CyanHJWJBSRFuxeyZZD五位AK爷。

明天的CF仔细想想还是不参加了吧。不管是谁都不敢确保自己下场比赛能在2986的rating守住lgm,即使是tourist也有可能失误,一旦下场比赛滚大粗,我怕在现在还是很可能对我整个人的心态产生影响,从而影响NOI。虽然下场比赛有可能打得好,但是我感觉也不能操之过急,如果水平在那里,什么时候涨rating都一样。而且那天晚上还是TC接着CF,两场比赛连着打第二场可能会受影响,再说我也想NOI之前好好休息一下。CF打完11点而且打完CF一般比较兴奋有点难入眠。所以还是NOI之前不打CF了。

明天是省队集训的最后一天,仔细想想这次省队集训大的失误除了第一天一个基本上所有人都犯了的错误之外,还是没有别的错误的,希望这次能够完美收尾吧,不要最后一天滚个大粗。

昨天提到一个求自转公转一定时间后的位置的做法,这个算法是错误的,原因很简单,如果你用旋转公式给整个多边形进行公转,那么同时整个多边形实际上也自转了一定角度,其实理解起来和地球日太阳日的区别差不多。论地理在OI中的重要性。

正确做法很多,最简单的做法之一是先把重心公转后的位置算出来,再按照相对重心的位移恢复其他点,再进行自转即可。

7月19日

省队集训第九天也是最后一天。

今天三道题都比较有意思,第二题很快做完,第三题想了个错误算法然后很快写完,接着很快做完了第一题。然后就开始浪了。

结果喜闻乐见的第三题就挂了。

今天第三题题意是,给你一个带权完全无向图要求把点集分成两部分使得两部分的点之间的边权的最大值之和最大,这是一道原题但是我没做过。

我的做法是,一开始点集只有1号点,接着选一个与当前点集之间的点连边最大值最小的点加入点集,每次将点集和点集的补集的集合内的最大边加起来更新答案。

这个算法你能具体解释一下为什么会错吗?

今天晚上是SRM 695和CF 363,后者已经决定不打了,前者我还是要打的,希望不要考挂。

300慢慢的认真写,写完认真检查了好久。分比别人低很多。

接着看到群里都说500不会做,于是开了800。

800想了一会儿写了一个发现萎掉了,然后就一直以为有然后,然而并没有然后......当时就意识到肯定要滚粗了。还剩20+min的时候灰溜溜的开了500

500不会,800也不会。

500问策爷说考虑前21条边就够了,我为了保险考虑了30条。

结果杜爷说500要考虑31条,成为CTSC rank5和CF 2899之后又一次只差1。

结果challeng环节发现300被hack了。写这么认真+这么久,你还给我错,其他人比我快还对。最后发现我犯的错,简直不能说是错,简直可以说是我没做出来,算法核心部分我都没有实现。

naive的以为学习petr写的时候认真一点交完再认真检查就能对,结果是真正的petr以比我快很多倍的速度写完并且对了,而我还是错了。果然是水平差距太大已经无法模仿了。

hack本来还失败了一次,结果后来hack回去了,hack回去之后知道要只有25分了急了随便hack了一个又失败了。结果最后爆零了。

我还naive的觉得我能一举target,结果居然掉到了2743。这个结果,我真的完全没有想到。

NOI要是这种名次我就铜牌了。

真的很想和鏼老师还有杜老师同台竞技,最后却发现自己实力远远落后于他们,所谓同台竞技,成了不断的喊“救命”和不断的求程序对拍。

不想传播什么负能量了,NOI之前最后一次TC爆零滚粗了,如果NOI再滚粗就可以向最后一场CF、TC和OI比赛都考跪的吉司机致敬然后看吉司机吃*了(逃)

7月20日

省......不,省队集训已经结束了。

早上看了看CF发现策爷CF掉的比我TC掉的还多......同是天涯沦落人咯。杜爷rank3帅气掉rating。petr帅气TC、CF两个一起AK+win+超过tourist。

非常佩服petr啊,两场比赛连续考还能一场不挂而且都是AK+win,换做是我考完第一场第二场一般都太兴奋就挂了。

明天一早就出发了,这次NOI是我最后一场NOI,我的前三场NOI结果都算好的,这次当然希望能考好。不过这次完全没有任何压力了,毕竟已经保送,当然如果滚粗了我肯定还是很伤心啦。

昨天提到一个错误算法,那个算法为什么会错呢,可以这样想,你加入一个新点到点集,可能导致其他点到这个点集的距离都变大了很多,这样就错了。

比如假设图权值只有0和1,且权值为1的是个二分图,那么答案显然是0,但是当且仅当我集合扩展到了图的X部分或者Y部分的时候答案才会是0,而我的算法就等价于——找与当前点集没有任何边相连的顶点扩展,所以很容易就从X部扩展到了Y部,随机一个二分图我的算法就很容易出错,因为一旦扩展到了Y部,基本上就不太可能还能算出正确的答案了(比如我们可以假设Y部的点度数都不为0)。

7月21日

出了些状况......

早上七点出发到成都再转车去绵阳,然后火车路上遇到状况晚点了,于是就没赶上第二趟火车。然后我们在外面转了好久才找到宾馆在火车站附近住下来。蜀道之难,难于上青天!

看了下上场SRM的800,发现我突然一下子怎么就什么题都不会了啊QAQ

成都东站我来过很多次了,比如WC的时候我就来过一次,最早来还是2013年第一次参加NOI的时候,那年是在电子科大。

而我后面还要去百度之星,打算玩几天再从成都出发到北京。

于是乎,不论是这次NOI,还是我参加过的所有NOI,都是从成都开始,到成都结束了。

不管是什么结果,都当做是命运给我的一份礼物吧。

7月22日

报到日。

上午差点又没赶上火车。

开了下上场CF的F,发现我最近debuff好像有点严重。

7月23日

开幕式上看了很多节目,比如变脸,完全不懂京剧那一套理论。

听到了CCF和教育部抗争10年,终于取消了NOIP保送的事。其实讲道理NOIP保送也挺不公平的,首先我们都觉得NOIP一等奖很容易,比直接高考考上那些学习容易很多,其次在NOIP作弊比在高考作弊容易多了,所以我个人还是持支持态度的。

下午笔试,感觉是四年来最水的一次笔试,三分钟提交满分无压力,虽然后面还是检查了一阵子。

明天就是day1了,希望自己能不留遗憾吧。

7月24日

NOI第一天。

看完三个题发现好像都比较可做的样子,第二题一眼以为是转化为八连通之后搞搞,结果发现答案只有四种可能。

感受一下感觉第二题比较恶心,于是就决定先做第一题再做第三题再做第二题。

第一题做到一半发现暴力有95,瞬间感觉自己在做无谓的努力,然后搞到九点多,感觉非常虚,过了样例就不管了。

第三题猜想互质就行了,结果写了个暴力发现大样例跑不出,然后开始加两句优化跑两下,终于加到能跑出的时候发现答案错了,然后写个大暴力好像排上了顿时慌了。接着发现我有个地方爆int了= =b

于是愉快地开始瞎做,做到一半发现我的方法好像有点萎,接着发现好像要用杜教筛,顿时感觉我走上了不归路。思考了一会儿人生发现好像没有什么救只好强上杜教筛了。

接着到了十点半宣布考试过了一半了。我开始刚T2。

结果发现果然T2才是最难刚的,一开始觉得把每个点周围曼哈顿距离不超过2的弄出来求下tarjan是不是行了,后面发现好像要用set或者map,估计不改成hash很虚要超时。

然后开始想别的做法,发现好像可以枚举一个点判断周围八个方向的情况,然后正要开始写的时候发现不会判不连通。然后发现前面那个tarjan的方法好像也不太好做了。

接着发现好像可以扫描线,每个连通块用最下边的最右边的点统计答案就可以了。

于是开始写写写,发现各种错,过了样例发现判八个方向好像没那么容易,然后瞎几把猜了个结论过了1000个数据的对拍。

于是我在1000后面加个零,拍10000组数据,发现WA得七七八八的= =b

于是令人感动的又改了几下,瞬间面目全非,感觉一副AC不了的样子,瞬间想起了WC拍100000组数据怒挂T2的故事,觉得很慌。然后开始狂对拍狂看代码。

后来觉得还是看看另外两题比较好,然后发现第一题好像三个样例拼起来就挂了,接着发现样例里面n递增于是我一个地方没清空没发现,令人感动......

下午过去看好像AK了,非常感动。

最后说下我对题目的看法吧,我觉得这次NOI的题目还算比较科学,部分分也较为合理,送的比较多,基本属于挂分大于没写正解少的分,这也正是ACM、CF、TC这些比赛的情况。没有码农题,有一定思维难度。而且这是NOI第一次引入杜教筛,感觉科技在进步。

我的第二题判断是否有割点的方法是。考虑每个蝈蝈周围8个方向的跳蚤,按顺时针或者逆时针考虑周围八个方向,如果一个对角线(比如上面和右边)都有蝈蝈那么就在右上角加一个蝈蝈,连通性和这两个相同(因为显然这个对角线上的两个蝈蝈属于同一个连通块)。

接着我们发现,如果按逆时针或者顺时针方向,某一个连通块的两个格子中间和外面都有跳蚤,那么这个跳蚤肯定是割点。

这个做法我不会证明或者证伪,如果有人会证明或者会证伪欢迎在博客下面评论。

7月25日

社会活动日,看了核武器以及很多其他炫酷的武器,接着去了一个公园,然后到了一个阁,听tty介绍了一些建筑学知识。

中午吃饭的时候听到有人说:“你怎么一颗原子弹都没偷出来”233333333

下午和大家颓。晚上开了一个CF题,发现自己一个思路完全不会变通,而且几年前学的huffman编码怎么用两个队列维护都想不起来了。

密码条上有我day2滚粗的flag啊。虽然我并不信还是希望第二天不要考挂了。这还守不住集训队我就把脑袋留在南山。

7月26日

NOI第二天。

当了一发咸鱼,第一题写完第二题写个85分第三题写个84分之后发现分好像比day1的第二名高了就开始守,然后发现第二题居然有部分分,然后提到了91分,然后开始不断检查,最后瞎猜了第二题的几个结论发现都是错的,然后就下考了。

下考的时候很慌很怕第二题是个上百人A的傻逼题。

结果发现我周围距离不超过2的地方就有人AC第二题,令人感动。不过反正我也有91分。

下午去看一分没挂,275分。

感觉今天题目分差比较小啊,第一题还算有点意思,two pointers套线段树,第二题结论还是挺有趣的,只是我太咸鱼了就没去猜了,其实好像去猜也猜不到,我本来想给样例打个表,后来构造了一个极端例子觉得好像分段可以很随机应该不会有啥规律就不管了,事实上好像是有规律的,那我考场上肯定想错了QAQ。

第三题拿到84分之后就不敢往下做了,实际上当时还是觉得第二题不会做放不下,放下了可(gu)能(ji)会(ye)高(shi)点(yi)吧(yang)。

晚上和vfk聊了很多关于他在英国的故事,感觉非常有趣啊。比如英国松鼠很常见,街道很干净,污染很小,天空很蓝。人们喜欢说thank you,餐厅里别人来为你服务也会说一句thank you。还有就是由于版权问题网易云音乐用不了233333

7月27日

上午趣味运动会,发现节目比较高能就逃出来了233333

然后下午闭幕式颁奖领到了金杯。节目也非常厉害,健美操四女一男比例有点鬼畜啊。

感觉这篇文章到这里也要结束了,总要说些什么吧。

首先当然是感谢了。这次NOI的成功,我必须感谢我的父母和老师对我的培养,感谢机房里的同学与我的交流以及对我的支持和鼓励,还要感谢CCF以及各位出题人们和南山中学等提供了这样一个平台,当然还要感谢命运女神的眷顾。

这是我第四次拿到NOI金牌了,当然这次还带有金杯,虽然在六块IOI金牌的tourist面前还是不值一提。

不得不说这四年NOI,最好的当然还是今年和2013年。今年就不用说了,13年的时候我水平比现在差很多却混到了金牌,其实最主要还是树的计数拿到了90分以及低的令人感动的金牌线。这两年都是在四川,或许四川是我的福地吧。

当然实际上我也大概知道原因,13年的时候,我什么负担都没有,觉得就是来玩玩,因此心态很好莫名其妙的拿了金牌。14年想13年我拿了金牌,于是当然便冲着金牌去,15年高一当然想进队,这两年都有一定的负担,反而就滚粗了。今年反正保送了,负担比前两年小,所以心态也好一些。所以感觉我还是这些负担比较小的比赛反而考的好啊,所以为什么那么多人(包括我)都经常CF、TC什么的贴线暴跌。

喜悦之余当然也有忧伤,作为退役的季节,不少厉害的人都没进队。共价大爷、稳爷爷kpm的滚粗完全出于我的意料之外。我们学校的tty也失误了。absi2011也没有进队。noname由于是D类,以集训队分数忧伤的退役了,有时候进队分数都达到过却不在同一年,也是挺悲惨啊(想想我CTSC2015的分数是不是能进队呢?不过仔细想想好像dls也也经历过一样的悲剧?)。而湖南省选的第二名yml和女生A队Cyan都没有进队。

作为UOJ的管理员,以后很难在榜上看到某些人的名字,看到这些人FST而叹息,看到这些人终于有人AC了某道题而欢呼,也不能在CF、TC上看到这些人的名字了。当我看到UNR上wyy怒虐第二名68分的时候,感觉十分佩服他,却在NOI之后惊闻wyy银牌滚粗。NOI之前的那场SRM,爆零之后kpm还特意安慰过我,然而他也无缘集训队,感觉真是十分忧伤。

在闭幕式结束后,lzz和wyy还和CCF的一些人讨论过NOI的出题问题,大概就是暴力和暴力之间分差过大,而暴力和正解之间分差过小。这一点我也深深的感觉到它对某些人命运的作用。共价爷第一天写了第一题正解,第三题由于没时间只写了一个40分的暴力。然而别人第一题不会正解有95分,第三题可以写个84分的暴力。共价爷分固然比他们低,但是他就真的比这些人弱吗?并不是!他们并不会第一题正解少了5分,然而却因为第三题会一个不那么暴力的暴力,就多了整整44分,连用杜教筛优化成正解都只值16分。实际上无论是CF还是TC这些较为权威的国际网赛,都是尽量使得难题分值大,简单题分值小,而NOI似乎是反过来的,这也是共价爷为什么进不了队的原因之一。

怎么说我UR出的Yist什么的题目顿时被D啦,不过UR毕竟不是选拔性质,这样出后果并不大,而且那题做UR的A只能这样,做B又太水。

然而OI比赛,真正应该出成怎样,并不是说大家希望怎样就是对的,也没有什么依据说一定要难题分值大,简单题分值小,相反有时候做好每一件简单事,不是比做好一件大事情要重要吗?OI比赛真正的最佳形式,或许只有历史的行程能告诉我们答案。

总之NOI已经告一段落,无论结果如何,都应该当做上天给自己的礼物,无论是进队或是回去高考,前途都是广阔的,清华北大不必说,就算是北航北邮这些学校,也是许多学生心中遥不可及的目标,希望集训队员能向着国家队前进,没进队的也能通过高考考进心仪的学校。

完结撒花。

评论

yanQval
前排跪毛爷爷
bzoj
前排跪毛爷爷
WrongAnswer
前排跪毛爷爷
ruanxingzhi
前排跪毛爷爷
zhouzixuan
中排跪毛爷爷
WrongAnswer
我比较弱没看出第一题的检查方式错在哪【除了可能把有解判成无解以外 感觉我也要挂了= =
jcvb
线段树合并吼啊。。
zxozxo
后排跪毛爷爷
WrongAnswer
无根树计数只会prüfer编码= =【手动滚粗
Orz__Orz__Orz
两个第三天QAQ
WuHongxun
前排膜拜myy,感觉myy对于自己要做什么和各种flag思考了很多啊。。但是有的时候是不是抛掉胡思乱想干脆的去做比较好呢?> . < 祝myyOI顺利w
Prime
“Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete.”这个是NPC的,毛爷爷你的提答是Brauer chain,是一个特殊情况,尚不知有什么好的做法(您的做法十分优秀啊
Sengxian
@matthew99 shuti 错误的三分直接满分,碾压一波标程QAQ
dogther
大后排跪毛爷爷
WuHongxun
QAQ求教这个问题怎么nlogn啊
ppfdd
我们不会做TAT
jcvb
我们也不会做TAT
absi2011
7月17号 今天第二题很简单 表示地理不好不会做
ppfdd
myy稳啊!
ppfdd
myy好大!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。