【比赛游记】NOIP2017游记

身为FJ的选手,在师大附中AHSOFNU考试,环境很不错,考得也还可以吧。。。【考的并不好】

不过比赛前都在划水233333

另:看到这篇博客的OIer们一定要评论啊!

Day1的中午,因为穿了短袖去,可能着凉了,头有点疼……一直疼到了Day2,QAQ。。

————————————————————————————————————————————————————————

先讲讲普及吧:

T1水过
T2平衡树套后缀自动机排个序,扫一遍就过了
T3我是BFS,应该不会有错
T4可以有TG难度了,二分答案+DP+单调队列优化
之后的1h30min在玩画图和超级画板。

问题:

T2的数据似乎有前导零,我虚了。
更新:T4打跪了,T2没问题???
结果出来后:T3挂了,T4挂了。

估分:

100 + 0~100 + 100 + 100 = 300~400。
更新:100 + 100 + 100 + 0~?100 = 300~?400,偏300,luogu测出来是350反正。
结果出来后:100 + 100 + =310

提高D1:

监考老师延迟了5min发题!!

T1是数学,正解就是(a*b-a-b),结果我写了个extgcd!!!!应该过了吧,毕竟lh也是一样。
T2是字符串处理……还要写栈,不过其实也还好……
T3我只写了没有0边的70分,可以先跑dij处理路径数,然后f[i][j]记1到i,路径长度为最短长度+j的路径个数,随便转移。
正解是对0边拓扑排序,把环处理出来,扔掉有环的点再跑dij,应该是这样……nealchen告诉我的……

问题:

学长说T1用extgcd会挂,我虚了。
后续:D1T2好多学长都挂了,可是我回来瞎敲了一遍(因为是同步赛,没有代码),居然A了??!!
后后续:T1没问题;但是T2挂了,三元运算符优先级没确定好,现在虚炸了;T3应该比较稳。
结果出来后:T2又没挂,该拿的分都拿到了!

估分:

≈100 + 100? + 70? = ≈270?。
更新:≈100 + 100 + 70? = ≈270。
更更新:100 + 0~100 + 70 = 170~270。
结果出来后:100 + 100 + 70 = 270。

提高D2:

T1看上去很水,就秒切了,暴力O(n²)处理边。
T2我是暴力DFS+最优性剪枝,可以过70……n=10都能跑过……好多同学都乱做骗40……
正解是状压DP,状态是每一个点的深度,也是nealchen告诉我的,啊啊nealchen太强辣!
T3是数结题啊,丧病至极,不过我还是尽力骗到了一些分数?
前50分,对x坐标离散化,最后一列单独开,暴力跑
接下来30分,注意到x=1,于是扔掉左下的一大块,单独对第一行和第m列处理,把原数组扔进去,再开一棵树状数组记录当前有没有值(没有的就是被删除了),查询的时候树状数组二分,是log级别,于是复杂度(O(qcdot log_{2}(n+m+q))),常数略有一点点,毕竟是树状数组??
满分好像qrc想到了,不过没打出来,可怜啊。

问题:

T1后20分爆long long了,悲伤。
后续:T1出题人说了不卡long long,开心。
后后续:T1没爆ll,但是,边表的1000000被我开成3000,气死了,只剩差不多40了吧;
T2莫名在洛谷上多过了一个点,但愿在官方数据下能过更多;
T3数组还是开小了,丢了前50分,后30分居然没问题,是的,就是这么弱。

估分:

80~100 + 70? + 80? = 230~250?。???
更新:100 + 70? + 80? = 250?。???多半是假的!
更更新:40+ + 70+ + 30 = 140+。这回是真的了!
结果出来后:40 + 70 + 30 = 140。如假包换!

TG总分:

~100 + 100? + 70? + 80~100 + 70? + 80? = 500~520?。???应该会再低30~50分。
更新:~100 + 100 + 70? + 100 + 70? + 80? = 520?。???应该会再低50~80分。
更更新:100 + 0~100 + 70 + 40+ + 70+ + 30 = 310~410。啊,好气啊,比预期低了110分,我要报警了。
结果出来后:100 + 100 + 70 + 40 + 70 + 30 = 410。真的少了110分。

总结:

思想不行,D1T1,D2T2应该要想到,不注意数据范围,导致D2T1丢了20分。
后续:感谢良心出题人不卡ll,D2T1没有丢20分,YAY!
后后续:两题数组开小,丢了100分,一题三元运算符优先级搞错,可能丢爆了。
应该要多注意细节,熟悉编程语言的语法。

似乎混了个FJ的同步赛rank6,可是nealchen是同步赛rank1啊!
所以还是不能满足于此啊!

原文地址:https://www.cnblogs.com/PinkRabbit/p/NOIP2017.html