E. Sagheer and Apple Tree
这场比赛的其余题目都比较无聊,不过这个博弈题倒是很有意思。
然后我仔细看题的时候发现看错题了…md…
如果没看错能不能想出来呢?
因为从根到叶子节点的路径长度奇偶性相同,所以我们可以根据根到某个点的路径长度来进行染色。
奇偶性和叶子节点相同的染成红色,否则染成黑色。
如果某些苹果从红色节点丢到了黑色节点或者从红色节点被吃掉,那么这个动作相当于取石子游戏中的取石子,游戏正常继续。
如果某些苹果从黑色节点丢到了红色节点,那么先手可以把苹果丢回去。
于是sg值就是红色节点的a[i]的异或和。
用个桶维护一下就能算出答案了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注