数位DP--HDU5208

题意：http://acm.hdu.edu.cn/showproblem.php?pid=5208

两个人分别有l，r的区间可以取一个数，ans=A^B，A人想让答案尽量大，B反之。

问ans。

思路：

数位dp，https://blog.csdn.net/yhn19951008/article/details/74316042

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int l1,r1,l2,r2,t;
 5 
 6 int dfs(int ans,int p,int f1,int f2,int f3,int f4)//p:二进制位置，f:能不能全取上下界,1能0不能
 7 {
 8     if(p<0)
 9         return ans;
10     if(f1&&f2&&f3&&f4)
11         return ans;
12     int u1,u2,d1,d2;
13     u1=f1?1:(r1>>p)&1;
14     d1=f2?0:(l1>>p)&1;
15     u2=f3?1:(r2>>p)&1;
16     d2=f4?0:(l2>>p)&1;
17 
18     if(u1==d1&&u2==d2)//每个人都只有一个选择
19         return dfs(ans+((u1^u2)<<p),p-1,f1,f2,f3,f4);
20     else if(u1!=d1&&u2==d2)//A可以让该位置为1
21         return dfs(ans+(1<<p),p-1,u2||f1,!u2||f2,f3,f4);
22     else if(u1==d1&&u2!=d2)//S可以让该位置为0
23         return dfs(ans,p-1,f1,f2,!u1||f3,u1||f4);
24     else if(u1!=d1&&u2!=d2)//S可以让该位置为0
25         return max(dfs(ans,p-1,1,f2,1,f4),dfs(ans,p-1,f1,1,f3,1));
26 }
27 
28 int main()
29 {
30     scanf("%d",&t);
31     for(int ca=1;ca<=t;ca++)
32     {
33         scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
34         printf("Case #%d: %d
",ca,dfs(0,30,0,0,0,0));
35     }
36 }