HDU - 6899 Xor(数位dp)

题目链接：点击查看

题目大意：给出四个整数 A , B , K , W ，问满足下列条件的二元对的个数：

x , y 是整数

x <= A , y <= B

abs( x - y ) <= K

x xor y <= W

题目分析：数位dp，如果按照二进制进行数位的话，除了第三个条件都比较容易实现，所以对第三个条件进行以下转换，abs( x - y ) <= K ，去掉绝对值的话就能转换为 x - y <= K && y - x <= K ，移一下项就是 x - y + K >= 0 && y - x + K >= 0，这样我们现在就得到了五个条件，作为数位dp的五个状态：

f1：代表 x <= A

f1 == 0：x < A

f1 == 1：x = A

f2：代表 y <= B

f2 == 0：y < B

f2 == 1：y = B

f3：代表 x xor y <= W

f3 == 0：x xor y < W

f3 == 1：x xor y = W

v1：代表 x - y + K，v2：代表 y - x + K，取值为 -1 , 0 , 1

重点解释一下 v1 和 v2 的三个状态吧，为什么要分成 -1 , 0 和 1 讨论，因为整个操作是在二进制下进行运算的，所以 x , y , K ,都只能取 0 或 1 ，那么对于其中某一位的运算来说，以 x - y + K 为例，其整体的最大值为 2 ，整体的最小值为 -1，又因为是从高位到低位进行的状态转移，每次得到的 v1 和 v2，传递到低位时，需要乘以进制，也就是需要乘以 2 才能换算为低位的实际数值，那么分类讨论一下：

上一次传下来的 v1 小于等于 -2：乘以 2 后此时 x - y + K 的值为 -4，无论如何取值都无法中和，越往下将会欠的越多，永远无法到达 v1 >= 0 的状态了

上一次传下来的 v1 等于 -1：乘以 2 后此时 x - y + K 的值为 -2 ，还有被中和为 0 的机会

上一次传下来的 v1 等于 0：显然是一个合法状态

上一次传下来的 v1 大于等于 1：乘以 2 后此时 x - y + K 的值为 2，下面无论如何取值，x - y + K 的值都肯定满足 v1 >= 0 的条件了，所以大于等于 1 的状态都将其归类为 1 的状态即可，能节省大量空间

实现的话就比较简单了

代码：
 

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;LL dp[35][3][3][2][2][2];int A[35],B[35],K[35],W[35];LL dfs(int pos,int v1,int v2,int f1,int f2,int f3) {v1=min(v1,1);v2=min(v2,1);if(v1<-1||v2<-1)return 0;if(pos==-1)return v1>=0&&v2>=0;if(dp[pos][v1+1][v2+1][f1][f2][f3]!=-1)return dp[pos][v1+1][v2+1][f1][f2][f3];int upa=f1?A[pos]:1;int upb=f2?B[pos]:1;int upw=f3?W[pos]:1;LL ans=0;for(int i=0;i<=upa;i++)//枚举A for(int j=0;j<=upb;j++)//枚举B{if((i^j)>upw)continue;ans+=dfs(pos-1,v1*2+i-j+K[pos],v2*2+j-i+K[pos],f1&&i==upa,f2&&j==upb,f3&&(i^j)==upw);}return dp[pos][v1+1][v2+1][f1][f2][f3]=ans; }LL solve(int a,int b,int k,int w) {memset(dp,-1,sizeof(dp));for(int i=0;i<=30;i++){A[i]=a&1;a>>=1;B[i]=b&1;b>>=1;K[i]=k&1;k>>=1;W[i]=w&1;w>>=1;}return dfs(30,0,0,1,1,1); }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);printf("%lld\n",solve(a,b,c,d));}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU - 6899 Xor(数位dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。