AtCoder Beginner Conteset 201 游记

似乎 D、E 的套路都很明显啊,我居然这个都要调半天甚至想不出来了……

D

(1,1)(1, 1) 出发可以向下一格向右一格,到一格时相应的人的分数会因为格子上的 +/- 而加一或者减一,T 先, A 后,最优策略下谁赢?

我开始时居然从头开始 dp, WA 了三发才发现决策的东西不对,应该是这一格来决策下一格,而不是这一格决策从哪一格来。

而且我们仅能确定的是在 (n,m)(n, m) 谁能赢。那么倒着 dp 一次就好了。

归根结底还是没想清楚就着急写。

E

求树上所有点对路径上边异或和的和。

我开始的想法是每一位分开处理,预处理出一个点向上/向下有多少当前位是奇数/偶数的,然后在统计,但这样显然会又重复,因为路径上 dfs 到的时候同一条路会被计算多次。

其实简单转化一下就很好做了,把它转化成根到两点的异或和的和,这样只要每一位看一下 1100 的个数乘起来就可以了。这个转化似乎也挺套路的。

也是最后时间紧急了就没想清楚直接写了哇,其实想清楚后完全来得及的,以后不要再犯这种错误了。


现在状态确实越来越差了。

翘翘

是谁使你优秀

又是谁使你堕落

所以你喜欢着谁

又痛恨着谁?