hdu6899 CCPC2020网络赛 1012 Xor-数位DP

题意：

T次询问，每次给出A,B,K,W，求满足下面条件的(x,y)对数：

1.x,y是整数

2.$x \in [0,A],y\in[0,B]$

3.$|x-y|\leq K$

4.$x~ xor~ y\leq W$

$A,B,K,W\leq10^9,T\leq2000$

Solution:

首先我们把条件3拆成两个条件:$x+K\geq y$和$y+K\geq x$

然后我们考虑数位DP，因为有异或条件的限制，所以我们的每一位指的是二进制下的每一位，因为涉及到加法操作，只能从低位向高位DP，DP时记录有没有进位即可。

状态设为：

$f[len][x\leq A][y\leq B][x+K\geq y][x的进位][y+K\geq x][y的进位][xxory\leq W]$

对于不等式的判断如何转移呢？

我们只需要记录只考虑当前位和低位时不等式是否成立即可，具体转移细节看代码，应该还是挺好懂的。

以前一直以为低位向高位无法转移，今天学会了一个新的姿势。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long f[40][2][2][2][2][2][2][2];
//bit x<=a y<=b x+k>=y 进位 y+k>=x 进位 x^y<=w 
int T,a,b,k,w;
long long dfs(int len,int xa,int xb,int xky,int addx,int ykx,int addy,int xyw)
{
	if (len==31)
	{
		if (xa&&xb&&(xky||(!xky&&addx))&&(ykx||(!ykx&&addy))&&xyw) return 1;
		return 0;
	}
	if (f[len][xa][xb][xky][addx][ykx][addy][xyw]!=-1) return f[len][xa][xb][xky][addx][ykx][addy][xyw];
	long long ans=0;
	int abit=(a>>len)&1,bbit=(b>>len)&1,kbit=(k>>len)&1,wbit=(w>>len)&1;
	for (int i=0;i<=1;i++)
		for (int j=0;j<=1;j++)
		{
			bool nxa=(xa&&i<=abit)||(!xa&&i<abit);
			bool nxb=(xb&&j<=bbit)||(!xb&&j<bbit);
			bool nxky=(xky&&((i+kbit+addx)&1)>=j)||(!xky&&((i+kbit+addx)&1)>j);
			bool nykx=(ykx&&((j+kbit+addy)&1)>=i)||(!ykx&&((j+kbit+addy)&1)>i);
			bool naddx=(i+kbit+addx)>>1;
			bool naddy=(j+kbit+addy)>>1;
			bool nxyw=(xyw&&(i^j)<=wbit)||(!xyw&&(i^j)<wbit);
			ans+=dfs(len+1,nxa,nxb,nxky,naddx,nykx,naddy,nxyw);
		}
	return f[len][xa][xb][xky][addx][ykx][addy][xyw]=ans;
}
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d%d%d",&a,&b,&k,&w);
		memset(f,-1,sizeof(f));
		dfs(0,1,1,1,0,1,0,1);
		printf("%lld\n",f[0][1][1][1][0][1][0][1]);
	}
}