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我并没有什么时间去多想，所以我觉得这几乎是全卷最难的题。