【游记】NOIP 2017

时间:2017.11.11~2017.11.12

地点:广东省广州市第六中学

Day1

T1:看到题目,心想这种题目也能放在T1?

这个结论我之前遇到过至少3次,自己也简单证明过。初见是NOIP2005 过河

结论是两个互素正整数a,b可以组合出>(a-1)*(b-1)的所有数字。

原理也很简单,考虑大的数字x去填补小的数字y的空隙,x每翻一倍可以填一个不同的余数(因为互素),翻y-1倍刚好填补y-1个余数,但是填补最后一个余数的时候可以往前延伸到(x-1)*(y-1)都是填补完毕的,所以得证。

T2:模拟栈,虽然题面有点繁琐,但其实挺简单的。

T3:30分的统计最短路径数先写了,然后发现k很小于是拆点dijkstra,不被卡常的话可以得到无0边的70分(卡常60分)。

正解是拓扑排序吧。

Day1一切正常。

Day2

今天真是惊心动魄……

8:30 一通狂敲读入优化和对拍,看T1。

9:00 完成T1(n^2建边后bfs)

开始看T2,用枚举边的方式写了T2的暴力。

接着看T3,写了30分暴力。

然后……天才卡题少女登场!

清晰地记得Day1的晚上,我说道:NOIP不可能考平衡树的,最多考个set。(NOIP确实很少出数据结构题嘛QAQ)

然后看到T3的部分分,经典splay操作(或者treap排名树),完全没复习。(数据结构本来就是我的弱项,平衡树确实已经半年没写了)

10:00 心态有点不好(省选也有考了未复习算法的经历),对现场推treap并不抱有信心。

心里想着说不定T3正解不需要平衡树,又想了想好像可以用块状链表代替平衡树。

但是时间还是不多了,推来推去始终需要数据结构。

开始想T2,觉得写出T2是唯一出路了。

T2的数据范围是一道明显的状态压缩题。

想到一个状态表示,f[d][x][S]表示根深度为d,状态S中的点形成一棵根为x的子树的代价。

转移复杂度爆炸,妥妥的0分算法,细节也很多。

挣扎着要优化,无果。

11:10 页面反复的在T2和T3之间跳跃,试图拿点部分分,脑袋里却一点思路也没有。

啊,这样是不是要退役了。

高二NOIP Day2目前得分100+0+30。

我的OI生涯是不是要这么结束了。

T3询问少的分数怎么写啊……不会啊……。平衡树还可以拿30分啊……好不甘心啊,我怎么没复习啊。

没时间了,比赛要结束了,我是不是要退役了。

好不甘心啊……

11:19 不能再浪费时间了,我想T2想到11:25,如果还想不出来就尽力拿部分分。

求求你了……让我想出T2吧……

11:22 简化模型,一棵树的价值是∑w(u,v)*d[v]。

我能不能枚举根,然后一个深度一个深度地向外拓展,考虑每层有哪些点。

枚举根,f[d][S]表示深度0~d结点状态S的最小代价。

转移的话,应该是算每个状态对下一深度包含此状态的状态的影响……3^n?应该反过来转移更方便。

所以用记忆化搜索的话,f[d][S]=f[d-1][S2]+w*d,w是S2^S和S之间连边的代价和,然后用记忆化搜索解决。

复杂度……O(n*3^n)?

好像可做???好像可做!!!

好像可做!!!时间不够了,快写。

11:30 开始敲T2正解。

11:40 敲完代码,强制自己冷静下来……还有20min够了,开始debug。

11:50 查出一个错误后,过了样例1和2。

求求你了,让我过样例3好吗。

445!

谢谢!!!克制住掀桌而起的想法摊在了椅子上。

12:00比赛结束。

出来后和ccz讨论发现T2写法一致,但是问题在于我处理两个集合连边多了n^2的复杂度(应该只能过70了,不过也比原来的20分好),这是可以预处理解决的。

还有就是我最后10min发现这个写法有个问题,S^S2往S连边不一定是叶子,反复考虑后觉得应该是一种放缩(条件严格化),这样计算虽然不全对,但是答案会被计算,非合格结果比答案劣,所以应该是正确的。ccz表示确实如此,长舒一口气。

NOIP 2017 期望得分:100+100+60(70)+100+70(100)+30=460(500)。

反思

有很多很多想说的话。

我已经高二了,OI生涯的最后一年。随着THUWC的出现,NOIP成绩变得非常重要。我身边的高二都是这样的想法:埋头冲刺NOIP,考得不好就退役不再搞OI。

高二的时候考试,心态已经和高一的时候完全不同了。退役的文章见多了,真正要直面退役的可能却是第一次。

嘴上说着退役了不要紧,大不了回去读高三拼文化课,其实我们中的大多数人,都没有面对退役的心理准备

其实我们中的大多数人在为了OI放弃文化课而不顾一切的时候,都没有想过承担退役的后果。

但是,无论退役的后果有多严重,我们依然愿意为了OI付出一切,为了能去想去的大学,为了自己的梦想,为了不去读枯燥的文化课,为了我们所热爱的信息学竞赛。

为了这些或大或小的梦想,我还不想退役,我还想继续战斗下去。

这次NOIP,有如下问题:

1.速度:前松后紧的问题依然存在,3.5小时3道题时间非常紧迫。暴力一定要写快一点,像Day2这样部分多题目难,就应该争分夺秒才能赢得更多的分数。

2.心态:不要总是想着这场比赛有多重要,考不好就退役了,这只会让头脑一片空白。想着考不好也无所谓,尽力去拿到更多的分数就好了。冷静!

3.战略:时间安排有问题,仍然想着要写正解,部分分意识还是很薄弱。不要花大把大把的时间想题,这样容易陷入一个怪圈出不来。勤动手,该拿的分一定要拿到,不该拿的分赶紧丢掉。

4.思考:多换换角度,不要老是围绕一个点思来想去没有突破,多尝试一些其他的切入角度。

5.复习:不要押题!不要押题!不要押题!不要抱有侥幸的心理,各方面都要准备充分,对自己的薄弱部分要不断强化,考前几天提前背好板子不要考前一晚熬夜

别忘了最初的感动,最后一刻的心动——《初梦》初音未来

想去见你,想回到那,遗失的过去。

想去见你,想迷失在,繁星的故居。

想去见你,想再一次,唱我们的歌。——《告白》初音未来

愿谁记得谁,最好的年岁。——《牵丝戏》银临/Aki阿杰

键盘微凉,鼠标微凉。指尖流淌,代码千行。

屏幕在深夜微微发亮,我心在考场。——《膜你抄》Menci

谢谢这些歌曲陪我度过NOIP 2017,不到绝境,我绝不会放弃OI。无论成绩如何,我都会继续战斗下去。

CYC never dies!

后记

最终成绩:100+100+60+100+70+30=460,和估计分数完全一致。

机房很多人考挂了,挂得很惨很惨。虽然我考得不算好,却也是少数正常发挥的幸运者了。

希望到明年五月,GDOI2018前我能对自己说,我已经有进省队的能力了。

如此,才至少不会辜负这段OI生涯吧。

幻梦终醒,本无不散之宴,却不悔付此华年。

加油!

上一篇:apache开源项目--nutch


下一篇:NOIP 2017 解题报告