AtCoder Beginner Conteset 201 游记
次阅读
2 min read
似乎 D、E 的套路都很明显啊,我居然这个都要调半天甚至想不出来了……
D
从 出发可以向下一格向右一格,到一格时相应的人的分数会因为格子上的
+/-
而加一或者减一,T 先, A 后,最优策略下谁赢?
我开始时居然从头开始 dp, WA 了三发才发现决策的东西不对,应该是这一格来决策下一格,而不是这一格决策从哪一格来。
而且我们仅能确定的是在 谁能赢。那么倒着 dp 一次就好了。
归根结底还是没想清楚就着急写。
E
求树上所有点对路径上边异或和的和。
我开始的想法是每一位分开处理,预处理出一个点向上/向下有多少当前位是奇数/偶数的,然后在统计,但这样显然会又重复,因为路径上 dfs 到的时候同一条路会被计算多次。
其实简单转化一下就很好做了,把它转化成根到两点的异或和的和,这样只要每一位看一下 和 的个数乘起来就可以了。这个转化似乎也挺套路的。
也是最后时间紧急了就没想清楚直接写了哇,其实想清楚后完全来得及的,以后不要再犯这种错误了。
现在状态确实越来越差了。
翘翘
是谁使你优秀
又是谁使你堕落
所以你喜欢着谁
又痛恨着谁?