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]$

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

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

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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]);
}
}

作者

Fizzmy

发布于

2020-09-29

更新于

2020-09-29

许可协议

评论