【NOIP2018】 游记

All ended?
【day 0】
一点感觉没有,不过翘掉了早上的课(当然还有前三周的课),然后刚想睡一会儿,就被通知要上车了/难受
在车上玩了一会儿早上下的Super Mario(主要是早上刷了一道这个的题),一会儿之后果断放弃这种低级游戏。。主要是第二关都过不去
看着边上的巨佬玩了一会儿红警,然后睡觉......差不多到了刚好也醒了(根本没睡着?)
报道的时候意外发现义乌竟然归到了绍兴...嗯...绍兴太强了
晚上和众多同学以及教练一起吃晚饭,走了以后服务员跑出来说我们没付钱,回去之后又说付过了/大雾
回宾馆颓了一会儿,九点十五上床,意外的没有失眠

【day 1】
蹭了一顿早饭,上车,去学军中学,内心毫无波澜
比赛开始,惊奇的发现比赛开始前不让敲电脑,读优模板没法打,背景没法调,电脑时间又是错的,但当时竟然还是呆呆的,啥也没做,直到8:30开始......
解压密码很棒!
t1:
本没发现这是原题,考试的时候想了15分钟,然后打了一个没法算时间复杂度的递归计算,大样例RE了无数遍,不过最后竟然秒过(其实最差可能会有n^2),手造一组数据n开到100000,竟然还是不到半秒,OK,t2.

t2:
嗯?又是算钱的CCF还嫌坑的不够多吗?这种题肯定背包乱搞,手算了第一组样例,发现只要找最少的种类构成其他所有种类就好了,那怎么找最少呢?
60分钟后,dfs+背包水过,大样例T了一丢丢...不管,先去看t3;

t3:
又是树上的,难道是树形DP?还是贪心?还是某种高级的数据结构?
鉴于厕所上太多?反正只剩下90分钟了,还有点想优化一下T2(比如打一个模拟退火?)所以想了5分钟正解无果,直接开始特殊数据骗分...链状?噢暴力。菊花图?暴力呗。M=1,加一个二分再暴力不是更方便了...
最后20分钟
优化T2,发现选的个数有单调性,选的越多越有可能性,加了一个二分;最小的一个肯定选,少一重爆搜
只剩下10分钟了
感觉要完蛋的查了一下文件有没有打错,有把第三题不符合情况写了个srand(19260817)的随机数
【day1总结】 噢,结(wan)束(dan)了 估分100+60+40=200(随机数加成?)=200(+玄学)
晚上去银泰吃了晚饭,逛了小米之家,听说隔壁高中的人去西湖玩了,今年没考字符串?数论?明天肯定要考,赶紧看一下!!

【day2】
在迷信中吃了早饭...
在报告厅里看到了Sooke巨佬,拜了几下,希望有加成吧
感觉头有点晕,过了好久好久,终于又开始了
【T1】
完蛋了,不会?大概10分钟的时候,发现是个贪心,又卡了好一会儿,发现每次都要把访问的那颗子树访问掉才行,那岂不是写一个dfs就切掉了?显然不是这样的,有环!不管,先把树的搞掉吧...9:30,始终调不过去,环里面的就更不要想了,完蛋
【T2】
题目看不懂,跳
【T3】
树形DP啊,跟那个有一道士兵站岗的题目好像是一样的,woc,100000^2?过不去啊
打了一个暴力树上的DP,过了好久好久好久才过了小样例,大样例是一遍过,又想当然的骗了一下链上的数据...
【还有1.5h】
回去看t1,发现问题了,数组定义位置不太对劲,改掉之后过了树上的样例;
至于环上,写个并查集,暴力删边,如果连通,就试一遍,记录字典序最小的结果
【还有0.5h】
T2
还是看不懂,n,m等价,令n<=m那么n=1的时候就是2^m然后飞速打了一个快速幂,有把样例特判了上去,希望能骗几分...
【day2总结】 噢,又结(wan)束(dan)了? 估分100+20~30+44=164~174

归程:唉?T2n=1的时候答案是0,完蛋了又少了无限分

总估分:200+144=344
今年day1这么简单都没有去年省一线,而且day1一群AK和fAKe的巨佬,怕不是完蛋了。。。

洛谷自测:100+80+20=200 100+20+20=140->340

day2T3最大值赋了LONG_LONG_MAX>>1,已经除2了,没想到还是溢出了...除4就44分了;

day1T1:担心CCF老年机会RE

upd:
回来就是期中考,全部爆炸...唉

原文地址:https://www.cnblogs.com/zhenglw/p/9971920.html