[参赛感受] NOIP2018AK记

[参赛感受] NOIP2018AK记

注明:摘要图片来自洛谷(有魔改)。本文只是日记,并没有题目和解析。
本文绝对是赛后写的,没有嫌疑。

赛前

听说文件目录要求很严格,我今天早上在家练习断网刷题,用虚拟机写代码时不小心按到重启快捷键…
然后做完提交到OJ,听取WA声一片。
因此我已经对退役做好心理准备了。

今天下午,我爸爸一定要我骑自行车去比赛场地,结果到了场地就要累死的节奏,还好有时间缓一缓。

问了一下同学准备得怎么样(杭州观成中学2017年级,最强大的打酱油团),可是由于装蒻是信奥竞赛生的本分,根本问不出来真实情况。好吧,就把心态放轻松点,当观成打酱油团都会爆零吧。

下午两点,我们就被push到了比赛场地门口的队列中。谁知队列阻塞,连续十五分钟都没pop。于是,我趁着时间充足,开启手机飞行模式和勿扰模式,全盘静音,然后关掉了手机。眼看着内存就要溢出了,队列终于以一秒10个元素的速度开始pop。经过一分钟,我们终于到了考场。

考场果然比照片中还壮观。这次比赛只有两个考场,一个是普通机房,另外一个就是学军的体育场,容纳了600多720人。要是能被分到普通机房,那得RP非常高了。座位并没有想象中那么一望无际,但是整整齐齐,每个选手都有一个“隔间”,能够极好地防止抄♂袭

比赛开始前五分钟,监考老师宣读了竞赛规则和注意事项。随后,猝不及防地,随着监考老师一声令下,比赛开始了。

比赛时

老师在屏幕上公布了试题的解密密码。这个密码真的是难猜啊… 是哪个聪明绝顶的出题人想出来的这种密码?我真想知道一下(我并没有要揍他的意思)。

junior: &GaiGeKaiFang(40)Nian
hint: 改革开放40年全拼首字母大写,密码由&开头,数字40用英文括号括起。

我并不是那种爱吃辣椒的人,所以一开始还是虐前两题。打开第一题一看:“标题统计”

What, 字符串查找?

接着往下看,竟然是统计标题里有多少字母和数字(卧槽,这么水?)。题目曰:“标题包含大小写字母、数字、空格和换行符”,输入格式中有曰:“一行”,所以getline(cin,s)估计就行了。

第二题!

看完,发现数据范围一脸可暴力的样子。太棒了!于是,我只花了40分钟就干掉了前两题,那时候我心情要多好有多好。

第三题!

题目为有N个人要从A地到B地。给定N个人到A地路边等待的时间,和摆渡车从A到B再回来所需的时间(只有一辆,但是容量无穷大)。问如何安排发车时间使所有人等待时间最小。

我一开始误解为“车一旦回到A地就必须立即出发”,那不是模拟吗?简单!暴力!等到程序写好,才发现不对,并没有那么简单。我一度想要弃疗,结果一看第四题,卧槽,更恶心… 算了,还是先做第三题吧。

一脸茫然之后我开始瞎写动态规划。我看到路边等待的时间可大至4 × 10^6,显然用这个做子问题不合适。我将状态改为两个0~N级别的数据,过了两个小的样例,极限样例数据却自测失败。仔细一想,算法不对。于是改进代码。这下好了,小样例都萎了,更别说大样例。由于要优化并提前DP状态,我又把数组范围改为从1开始,花费不少精力。时间飞速,转眼间,半小时过去了,一小时过去了,90分钟过去了,小样例答案错了又对,对了又错,大样例的答案却似二分查找——不停地逼近正确结果,却永远无法到达。又过了一会儿,我竟大胆地将状态改写为一个1~(N+1)的数据。我多次想要放弃,但是一看到第四题,想到要重新开始,我又有了那么一点点做第三题的信心和决心。

监考老师似乎也知道我们要嗝屁了,给我们发面包。然而我并没有心情吃。

眼看着第四题就要没有时间了,在羞愧、恼怒、惋惜、焦急和迫切想要砸电脑的欲望之中,我突然心血来潮,删掉之前写的核心代码,又调试了好长一段时间。大样例的答案是13490,你可知道,当我终于看到程序输出了13458时,我是何等喜悦!我立刻振奋精神,遍历整个代码,发现有一处漏写,立即加上,程序就在0.51秒的时间内得出了正确答案——13490!

哇,太棒了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!成功了!1 AK 101 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

可是我的程序总还不那么令人放心,因为毕竟耗时0.51秒,就怕奇葩测试数据一出来就挂掉了。毕竟,我的子问题有两个参数,一个1~(N+1)级别的参数,还有一个时间级参数,范围不明(我并没有理论计算过)。其中还有一层人数级的循环,该循环内还有一级人数级循环,用于累加。那累加的地方来个前缀和如何?这样最坏情况刚好卡到一秒的时限,而事实数据一定没有我推出的理论情况这么坏(因为参数二我认为它是时间级参数,而没有严谨地计算范围,实际应该不是),于是,求出正确答案的时间瞬间变成了0.13秒,翻到卷头表格一看,时限2秒,那肯定可以过了(但是万一最坏情况真的有我想得那么坏肿么办)。

于是我又仔细检查了一遍第三题代码,发现了一个天大的事情——差点爆零。freopen()文件读写是cstdio中的东西,可是我在输出时只引用了iostream(听说万能引用头文件bits/stdc++.h有毒,会出现玄学错误,不敢用)。Windows版引用iostream时会自动引用cstdio,所以调试没出错,但是到了Linux评测机上,那可就没有禁赛一年就不错了。

第四题,我认为无可优化,写完暴力就逃(骗分20)。

谁知… 比赛结束前1分钟,我突然想到一个聪明绝顶地方法,可是已经来不及了(能不能续命,要是续命搞不好就AK了)该方法后来被我证明是错的。

比赛结束前一分钟就没有机会再写代码了,因为这时要清理掉选手文件夹中的无关文件,然后坐以待毙。

赛后

比赛结束后,我整理东西时,突然听到旁边“这次比赛真是太简单了”。难道我要退役了?

赛后我去如厕,听到学军的大佬说“第一题怕是要萎”。啥?我也萎了?还是学军同学真的基础不扎实?

后来我和rzmID谈论,第一题的疑虑就消除了。他做出了前两道,第三道0分,第四道估计32。我更加放心了一点。

晚上,杭二中老师发微信朋友圈,称这是“历史上最难的NOIP试卷,第三题和第四题基本不可兼得”。当我告诉他我做出第三题时,他都觉得难以置信。

这次一等奖分数线多少?怕是到不了二百五。我终于知道自己可以免于退役了(而且成绩还不错)。

坎坷的第四题

三天后的晚自习…
Exile: 你AK了!(来自教练在洛谷用山寨数据进行的评测)

What???

不是说好的骗分32吗?于是我表示质疑,问家长,家长说第四题正解就是暴力?

评测机配置真的如此之高?于是第二天我回忆题目…

事实证明炸不掉。应该我的程序只有极端数据——树是线性时才会爆,那就是96分。哪来的100?

结果发现一件严重的事情。。。我的程序当一个节点只有左或者只有右时会立即退出。歪打正着?没有办法,反正I AK NOIP.

看到成绩

后果非常严重——AK了(第四题歪打正着,没错)

 

评论: 8

  1. rzm说道:

    我的第4题32分已萎

  2. Exile说道:

    可以,很他妈ojbk。

  3. Q_P_Q_说道:

    您什么时候去AKIOI???

添加评论

我们将在300年后停止对游客评论的支持。请尽快注册或登录
本站现已支持评论使用Markdown来发挥个性。Markdown说明