HDU 5208 Where is Bob

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5208

题目翻译

两个区间,(\left [ l1,r1 \right ]) 与 (\left [ l2,r2 \right ]),Alice在第一个区间里选择一个数字(x),之后JSL在第二个区间里选择一个数字(y)。最终结果(z=x XOR y),Alice期望数字尽量小,JSL期望数字尽量大。求(z)的值。

题解

类似数位DP,我们按照每一个二进制位来处理,对于Alice的每一个的选择,JSL一定会尽可能地让自己这一位和Alice相同,从而使这一位消掉。
所以,我们数位DP,Alice的选择,贪心处理JSL的选择。
DP[pos][upAlice][downAlice][upJSL][downJSL]表示当前pos位的时候,两个人这一位的上下界情况如上的最大值。

代码