[参赛感受] NOIP2018普及AK记

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

赛前

听说文件目录要求很严格，我今天早上在家练习断网刷题，用虚拟机写代码时不小心按到重启快捷键...
然后做完提交到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了）~~该方法后来被我证明是错的。

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