NOIP2018崩崩记

比赛前,做做往年的题目,嗯,似乎都很水,400+绝对没问题,如果完全发挥,起码500+。
然而……


Day0

这天是运动会,信息学的同学们向老师请假来机房。
然后我在机房里刷往届的题目,信心倍增。
最后,刷得有点头昏脑胀了,才去了一下运动会那边,最后买个面包匆匆吃掉,上车。
酒店是在广州市南洲路上的维也纳酒店,设施似乎不如之前……


Day1

早早起来,刷牙洗脸。
早餐虽说不如之前的酒店,但也还好。
上车了,结果发现有一个障碍挡住了车的去路,于是我们下车,司机以神车技过去了。
上车,到达广州六中,别人都已经到了。
匆匆走入考场,看注意事项,看题。
T1水题,就是围栏翻新,一眼切。
T2想了想,一开始和上一年的Day1T1建立联系,后来惊奇发现:
只需要在序列中筛掉那些没用的数就好了。
什么数没用?
后来我发现可以被其它数表示的数就是没用的数,
数据这么小,一个完全背包不就可以做了吗?
T3看见最大和最小放在一起,果断二分。
一开始发现部分分很好拿,然后我就把直径、链、菊花图打了出来,然后思考二叉树。
然后发现一个东西:对于一个节点的两个儿子,如果两两配对超过那个长度,就连在一起,否则,两个当中选一条最长的延伸上去。
又和菊花图的情况联系在了一起,我惊奇的发现,我好像摸到了正解。
不觉,心跳加速,呼吸急促……(崩崩崩~)
没有打二叉树,直接推正解。
最终,没打出来……
比赛之后很快发现,其实再套一个二分就行了,先将最多的匹配数求出来,然后二分要将哪一个伸上去,计算最大匹配数,如果不变,就继续往上找,否则往下找。
距离正解,一步之遥……

下午,去了趟纪念堂,然后去了广州塔,最终回酒店,在酒店里去拜访gjy。


Day2

这次比较早地去到了广州六中。
然后,8点到了,怎么还不给进去?
心急火燎。
后来,进去了,你告诉我不能试机?
昨天我们到的时候还看见一堆人在打程序来着……
然后看题。
浏览一遍后,先做T1。
好像很水,似乎和最小生成树差不多,结果……咦,样例没过?
题目看错了。
心态开始崩……
树的情况特别简单,随随便便就打出来了。
然后是环套树,
嗯,分类讨论,1在环上,1不在环上(后来发现和前面的本质一样),环走完一圈,环在还差一个边的时候倒着回来……
并且是边打边思考,边打边想起这些情况。
2000+了,还没打完……(心态崩崩崩)
一个半小时了,非常不爽地弃疗。
思考T2
一开始推了个伪方法,然后打了出来,WA了。
然后一波乱推……
差不多了,差不多了,差不多了……
咦?没时间了!不行,要做第三题!
匆匆打了个暴力,然后跑去看第三题(崩崩崩崩)。
T3暴力很好打,就直接暴力修改嘛!
经典问题嘛,打出来再说!
结果……
为什么WA了?为什么?
调了半天,大样例没过……
比赛结束。
后来发现T3一时心慌将概念混淆了。
明明是相邻的两个点中至少要有一个,但我搞成了另一个模型:一个点的周围至少要有一个。
人家设了fi,0/1f_{i,0/1},我设了fi,0/1/2f_{i,0/1/2},不一样……
而且相对还更难打……

其实T1删掉一条边就好了,O(nm)O(nm)能过。(还有,题目大意我理解错了,原来一个点走过之后就不能再走,即使在环上绕了一圈再回来。)
其实T2T3送的部分分很多……

心态崩了!!!

总结

  1. 在看完一道题后,千万不要随意地下结论,而是要静下心来思考,不要太急躁。
  2. 不要边打程序边想,发现自己漏了很多东西,应该先在草稿上仔细思考,磨刀不误砍柴工。
  3. 见到样例后一定要手玩一下,不然容易搞错题意,或者模型混淆。
  4. 看到题目后一定要估一下时间复杂度,不要总是想着最优解。在比赛时,拿分时关键。
  5. 最后一点,在比赛的时候心态不能崩吗,绝对不能!!!

呜呜呜……赛季报销了……

原文地址:https://www.cnblogs.com/jz-597/p/11145261.html