前言
从最初接触oi到今年noip到来，也已经将近有一年了。从对于程序一窍不懂到现在开始学习算法，只是短短的不到一年的时间罢了。这次noip，不仅仅是我oi生涯的第一次noip，更是相当于是对我这一年的努力的一个检验。希望这次能取得一个好的成绩吧。
背景
初一时参加了南海区区赛，结果发挥失常，只有三等奖，痛心疾首，遂定下noip2018一等奖的目标。
初赛
不知道为什么前一天晚上睡眠质量极其差，基本上每个小时我是有醒来的时候，到了四点多我干脆不睡了。去厕所复习了《红星照耀中国》。
考场就在本校，所以直接呆在学校复习。
学校饭堂早餐是方便面（差评）。吃完后就去机房复习。
中午去饭堂吃饭，饭堂大叔很亲切地给每个同学打了四份菜，很饱。说实话挺感谢这位大叔的，可以看出来他是真心地祝福我们取得好成绩。
饭后休息了一会就去考场准备了。
14:30准时发试题，初赛就正式开始了。
选择题略难，感觉比去年难，考场上目测错五题左右。
问题求解和阅读程序求解很水，很快就切完了，细心一点就能拿满分。
完善程序第二题双向链表程序感觉很难，但是空全部都可以根据对称性蒙对……
剩下时间都在刚不确定的题目，最后也没什么进展。
16:30，考试结束。
考后和同学一起对答案，发现选择题有一道智障水题粗心多错了，完善程序第一题把下标当数组用了……心态爆炸，不要脸地大呼没有90pts要凉。
晚上出参考答案了，忘了自己写的答案，估分77～83pts。
几天后初赛成绩出来了。
比估分高，87pts，估计是蒙对的比预想的要多一些。
后来了解到gd分数线是60出头，没想到比去年高这么多。
当然，今年初赛的分数线比去年高应该是因为完善程序可以蒙，如果留空留得刁钻一些，可能分数线会低很多。
总而言之，今年的初赛对我来说还算是有惊无险的了。接下来就要期待我复赛的表现了。
复赛
最后一周开始全力复习，文化课都没怎么管，这几天作业没全部完成过。（还好班主任没发现）
然而复习成果貌似不怎么样。
无论如何，复赛马上就要来了，就算没复习好也要硬着头皮上。
复赛前一天晚上也是住校，学校要求直接睡别人的宿舍……
凌晨三点被蚊子吵醒，打了两个小时的蚊子，到了五点多因为劳累过度而再次睡着。
真是愉快的一夜呢。
根本没睡多久所以今天一整天都没什么精神。
饭堂早餐还是方便面。大概七点就回到机房复习了。
考前几小时看完了ac过的题后，写了几个模板，然后就上大巴出发了。
在大巴上看《算法竞赛进阶指南》，dp部分实在看不懂（我太弱啦），只好认真看搜索，特别是剪枝部分。
没过多久，就来到了广州二中。
第一次来到这所学校，大感为什么和我校差距这么大……
广州二中伙食还不错，吃的很饱。
考前紧张到发抖，一直以喝水来压惊……
两点多钟到了试室，刚开始充满激情，结果被突如其来尿意憋没了（谁叫你之前喝那么多水）。
两点二十多分进入试室，监考员早早地写上了密码，看完后去上了厕所，发现这层楼好像只有一个男厕？？？
14:30准时开考，然后可能我这一年oi生涯里最惊心动魄的三个半小时就到来了。
开考后打开题目花了近五分钟。下意识点开c盘里找，一直都找不到比赛文件，最后还是用全局搜索查找文件名，才发现东西都在d盘里，解压密码输了三次才对，导致开考后五分钟我才拿到试题……
按照ccf得难度分布惯例，我打算t1t2做一题看一题，做完后看一遍t3t4再决定做哪一题。
可惜今年ccf，貌似并不按常规出牌。
t1一如既往的水，getline再遍历一遍输出即可。切掉后检查了很久，差不多10min才过掉这题。
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
string s;
int ans;
int main()
{
freopen("title.in", "r", stdin);
freopen("title.out", "w", stdout);
getline(cin, s);
; i < s.size(); ++i)
{
') ++ans;
else if(s[i] >= 'A' && s[i] <= 'Z') ++ans;
else if(s[i] >= 'a' && s[i] <= 'z') ++ans;
}
cout << ans;
;
}
我的程序
t2大模拟，不过要注意一下精度问题以及分类讨论求解，还是考细心为主。
题目有点长，尽管全部分析完再写，也是边写边改（还是我太弱了）。大概写了20min然后测样例，没过，继续改，还是没过。最后改了快到15:20才改好，反复检查后就放心地去做剩下两题。
#include <iostream>
#include <fstream>
#include <cstdio>
#define MAX_N 100001
using namespace std;
int n, m;
long long a[MAX_N];
long long sum1, sum2;
int p1, p2;
long long s1, s2;
long long d;
inline ? x : -x;}
int main()
{
freopen("fight.in", "r", stdin);
freopen("fight.out", "w", stdout);
scanf("%d", &n);
; i <= n; ++i)
{
scanf("%lld", &a[i]);
}
scanf("%d%d%lld%lld", &m, &p1, &s1, &s2);
a[p1] += s1;
; i < m; ++i)
{
sum1 += a[i] * (m - i);
}
; i <= n; ++i)
{
sum2 += a[i] * (i - m);
}
p2 = m;
d = abs(sum1 - sum2);
; i < m; ++i)
{
if(abs(sum1 + s2 * (m - i) - sum2) < d)
{
p2 = i;
d = abs(sum1 + s2 * (m - i) - sum2);
}
else if(abs(sum1 + s2 * (m - i) - sum2) == d && i < p2)
{
p2 = i;
}
}
; i <= n; ++i)
{
if(abs(sum1 - sum2 - s2 * (i - m)) < d)
{
p2 = i;
d = abs(sum1 - sum2 - s2 * (i - m));
}
else if(abs(sum1 - sum2 - s2 * (i - m)) == d && i < p2)
{
p2 = i;
}
}
printf("%d", p2);
;
}
我的程序
感觉这次在前面两题花的时间有点长了，按照这个题目难度其实三点前就能切完。我切水题的能力还是有待提高。
看完后面两题题面之后，最先想到的就是t3用dp，t4除了暴搜+剪枝以外，没有任何思路，于是决定先做t3。（其实我应该先做t4才对，不知道当时脑子怎么就抽了）
t3方程不好想，本来刚开始想到解法，写了30min，突然想到反例，自己hack了自己，只好全部删掉。想了半天正解无果，就打算换思路骗分，写一个能拿50pts的dp。
写完之后又去乱搞优化，结果不知道是什么问题，各种莫名错误出现。一行一行代码注释去测哪里出错，还是测不出来，只能自己乱改。（其实我应该推掉重写才对）
在改的过程中，下意识看了表，发现现在都已经是16:49了！无法，只好先放弃肛这一题。
打算上厕所去放松心情，结果这层厕所又被人占了？当时就是不知道可以跨楼层上厕所，只好憋着继续考。
虽然上不了厕所，但我还是在门口外面想了一会t4，只想到暴力做法，就回试室去实现了。
花了30min去写t4的暴搜和小部分剪枝，其他剪枝因为时间问题来不及加，草草调试了一遍，看到过了两个小样例后随便测了大样例，也没认真看用时，没记错的话好像用了5s多……（可能真是我记错了）
#include <iostream>
#include <fstream>
#include <cstdio>
#define MAX_N 1000001
using namespace std;
int n;
struct Node
{
int val;
int lt, rt;
int num; // 以这个点为根的树的节点数量
}a[MAX_N];
;
void Get_Num(int x)
{
a[x].num = ;
&& a[x].rt == -) return;
&& !a[a[x].lt].num)
{
Get_Num(a[x].lt);
a[x].num += a[a[x].lt].num;
}
&& !a[a[x].rt].num)
{
Get_Num(a[x].rt);
a[x].num += a[a[x].rt].num;
}
return;
}
bool DFS(int x, int y)
{
if(a[x].val != a[y].val) return false;
if(a[x].num != a[y].num) return false;
&& a[y].num == ) return true;
&& a[x].rt != - && a[y].lt != - && a[y].rt != -)
{
if(!DFS(a[x].lt, a[y].rt)) return false;
if(!DFS(a[x].rt, a[y].lt)) return false;
return true;
}
&& a[x].rt == - && a[y].lt == - && a[y].rt != -)
{
if(!DFS(a[x].lt, a[y].rt)) return false;
return true;
}
&& a[x].rt != - && a[y].lt != - && a[y].rt == -)
{
if(!DFS(a[x].rt, a[y].lt)) return false;
return true;
}
return false;
}
int main()
{
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d", &n);
, ;
; i <= n; ++i)
{
scanf("%d", &a[i].val);
}
; i <= n; ++i)
{
scanf("%d%d", &a[i].lt, &a[i].rt);
}
Get_Num();
; i <= n; ++i)
{
|| a[i].rt == -) continue;
if(DFS(a[i].lt, a[i].rt)) ans = max(ans, a[i].num);
}
printf("%d", ans);
;
}
我的程序
回头做t3，那个时候是17:42。遗憾的是，直到考试结束还是找不到t3程序莫名re的原因在哪，来不及重构代码了，只好把这个八成会爆0的代码交上去。
看了看窗外的黄昏，这景色就和自己的心境一样，整个人都更崩溃了。
最后10min，监考老师提醒，才发现有考生注意事项的文件，估计是开考的时候太急没看到。本来想问程序存到哪里，才发现是要放到d盘（汗）。
花了几分钟去检查文件名和测能否编译。搞完后只剩最后半分钟，平复了一下心情，估了一下分，感觉要凉，心态更炸了。
18:00，比赛结束。
出了试室和同学互探考得怎么样，跟同学说了我t3的情况，越说越觉得遗憾，最后还是不想说下去了。
上了返程的大巴，全程都有人在讨论t3，貌似有人想到正解了？？
t3莫名错误搞得我很不是滋味，就因为它，这次我能否拿一等还是很悬。
考后自己估分，应该是100+100+0+(0~40)。只能坐等ccf出成绩了。
这次考不好的原因，当然还是我的实力不够强，特别是dp需要加强；其次搜索和贪心的话，因为骗分肯定会用到，所以也需要再去提高；还有最近新学的知识需要巩固的。
尽管t3错误异常，但如果我水平足够的话，其实是应该能找出缘由的，实在不行我也可以重写。这也提现了我考场策略也不怎么好。
至于考场策略不好，都是因为我的参赛经验不足。我的时间把控很不到位，前面三题花了太多时间（尤其是t3），导致t4根本没什么时间去想。我的其他方面的一些技巧也都需要去加强。
总的来讲，这次noip很好地诠释了一句话：技不如人，甘拜下风。
无论这次成功与否，该考完的已经考完了。
就这样吧。
考后第二天早上起来去洛谷自测，只交了三题，没交t3，结果全ac了，这数据太水了吧……
休息了一天再来想昨天的比赛，感觉心情好了很多。oi生涯中的第一次noip终于过去了。如果高中继续学下去的话，那也是只有四年的时间打oi了。进了竞赛这个圈子，收获了很多东西，在无数dalao面前，更加能感受到自己的渺小（弱）。在那么多从小学oi的人面前，我是毫无优势。若达到他们的高度，我还有非常多需要学习。
这次我是带着挑战ak虐场的心态来参加的，t3的dp狠狠打击了我，t4据说正解是manacher或hash，这我也根本不会。这次noip是深刻地让我意识到了我距离akpj还有多大差距。
本来打算考完这次，明年就去打tg。考成这样，明年直接参加tg估计是不可能的，应该还得继续打一年pj，希望明年能够如愿以偿。
过了几天后，ccf才公布选手程序了。
后来断断续续测了几个数据。
洛谷：100+100+10+100
学军：100+100+10+100
牛客：100+100+10+100
某大佬出的数据：100+100+35+80
本来测完前三个之后，自我感觉已经好了很多了，还真的开始有想着ccf的数据跟这上面的一样水的念头。结果在某大佬的数据下，t4re了五个点，感觉这样下去官方数据可能会re更多！现在我又慌了起来。
出成绩那天，中午没吃饭，赶着去机房查成绩，结果ccf咕了？害得我一天心情都不怎么好。
下午上电脑课，发现ccf改为明天出成绩……
第二天上午被老师叫出去，果然是ccf出成绩了。
rp爆炸，t4居然ac了，总共是100+100+5+100 = 305，在gd里也算是前几十名，应该是有一等奖了。
如果要把这次的题目放在洛谷上的话，个人认为难度如下：
标题统计：红题（不解释）。
龙虎斗：橙题（只不过是细节需要注意罢了）。
摆渡车：蓝题（这dp真的好难QAQ）。
对称二叉树：绿题（数据太水，就是剪枝水题）。
（话说我考前看剪枝，结果t4真用到了剪枝，怕不是要被禁赛）
又过了很多天，ccf公布了奖项。
得知了自己拿了一等奖，虽然这已经是不出所料的了。gd省一线215pts，有点水了。
再回想这次noip，虽然对于我的真实水平来说，这次成绩是有点差了，但毕竟还是有一等奖而且是300+，遗憾也没有那么大了。
无论如何，noip2018已经结束了，让我们noip2019再见！