Hdu 1079 Calendar Game

时间:2021-01-02 07:43:31

Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=1079

一道博弈题。刚开始想用判断P点和N点的方法来打表,但无奈不知是哪里出错,总是WA。于是看了该题的Discuss,才明白这种做法。

日子到日子之间会存在这种变化:假设初始为a月b日,且sum = a+b,则进行一次变化后即为sum = a+b+1,即奇偶性会改变。

可以发现11月4号是11+4=15,也就是奇数。那么当一开始Adam得到的和为偶数时,那么Adam就有方法将偶数变为奇数。而Eve只能将奇数变到偶数。一直到最后,Adam就有机会将11月3日或10月4日变为11月4日。

但这之中是否有几个特殊的日子对其造成影响呢?

确实有,那就是11月30日和9月30日,因为这几个日子是奇数和但却可以变成奇数和( 9.30—>10.1, 11.30—>12.1 )。如果Adam拿到这几个日子就仍有机会拿到奇数和,改变之前下的定论。而对于Eve,Eve没机会拿到这个日子,因为Adam可以故意避开到这两个日子( 8.30->8.31, 9.29->10.29, 10.30->10.31, 11.29->12.29  )。

因此最终我们可以确定:给定一个日期,只要和是奇数,或者是9.30或11.30,则Adam就可以获胜,否则必输。

对于本题题解,感谢 务殊 的解释。

代码就不上了。