NOIP2018 Day2 游记
noip2018 oi今天起床晚了,不过动作比较快,7:30就到基础实验楼了,在车上坐了一会遇上了cw的大部队(校车还是没有开进来),就跟着走了,并没有遇到llf。在广场上领取了准考证就进去了。考前fy邀请我去洗手,他说考前洗手能够增加RP,我就信了他的鬼话。看到T1之后感觉RP都被洗掉了。
T1 Travel
没错我又看错题了,没有注意到只能沿到达的边返回,以为是个弱智搜索加优先队列,两分钟写出代码,顺利的没有通过样例。仔细读题后,觉得很棘手,不过看到数据范围说有情况是一棵树,那这种就很好写了,直接在每个dfs时优先选择最小的孩子走就是了,顺利通过样例和大数据。之后发现剩下一种n=m的情况只有一个环与树的情况区别不大,就先写了一个tarjan把环找出来,然后一大堆if特判,大约在9:15的样子通过了大样例。
T2 Game
这道题看到数据范围真是让我吓了一跳。感觉是状压DP+滚动数组什么的,但是对DP方程式毫无想法,对着题目傻看了二十分钟,连n=3的样例都不知道是怎么算出来的。这半个小时唯一的结论是n=1或m=1时答案为2^n,遂写了上去。然后又花了二十分钟人力枚举了2x3和3x2的情况,在尝试拿n=2,m=1e7的分,但是并没有拿到。鉴于T3我并没有什么时间去多想,所以我觉得这几乎是全卷最难的题。
T3 Defense
看到这道题时我已经不剩多少时间了,于是根本没有考虑正解,只想写n=2000的暴力44分(暴力O(n)回答每个查询)。然而!!!我又把暴力写挂了!!!能过小样例但过不了大样例,真是太奇怪了。估计得不了什么分。正解应该是某种数据结构吧。
怎么办,估分344,我好虚啊……真是太弱小了……原来D1的题这么简单是有原因的……