LOJ 6274 数字(数位dp)

题目描述

NiroBC 姐姐脑洞了两个数字 和 ，它们满足 ，且 ， NiroBC 姐姐想知道 有多少种不同的取值，若有多组 的 值相同，则只算一次。

（其中 表示按位取或，C/C++中写作|，Pascal中写作or）

（其中 表示按位取与，C/C++中写作&，Pascal中写作and）

输入格式

一行，五个非负整数 。

输出格式

一行，一个整数，答案。

样例

样例输入

11 3 10 8 13

样例输出

7

数据范围与提示

对于所有数据，\(T,L_x,R_x,L_y,R_y<2^{60}\)

Subtask1

\(T,L_x,R_x,L_y,R_y<2^{10}\)

枚举统计答案即可

namespace pt1{
	int mk[1<<10];
	void Solve(){
		int ans=0;
		rep(i,Lx,Rx) rep(j,Ly,Ry) if((i|j)==T) mk[i&j]=1;
		rep(i,0,1023) ans+=mk[i];
		printf("%d\n",ans);
	}
}

$$\ $$

Subtask2

\(L_x=L_y=0\)

考虑简单数位\(dp\)

\(dp[i][lim1][lim2]\)表示\(\text{dp}\)到了第\(i\)位，\(lim1,lim2\)表示是否受到仍\(R_x,R_y\)的限制

枚举两个数这一位分别选择\(0,1\)，是否与\(T\)的这一位相同

但是存在一种会算重复的情况

当两个数均可以取\(0,1\)，且\(T_i=1\)的情况，则存在\((0,1),(1,0)\)两种方案且他们的与相同

如何处理重复?我们分类讨论一下（看不下去可以直接看结论）

1.\(lim1=1,lim2=1\)

这时候，把\(R_x,R_y\)中剩下的位数较大的那一个选为1，另一个选为0，这样选择一定包含反过来的情况，因为限制减轻了

2.\(lim1=1,lim2=0\)

当然是取(0,1)，理由相同

3.\(lim1=0,lim2=1\)

当然是取(1,0)，理由相同

4.\(lim1=0,lim2=0\)

那么可以随便取其中一者

最终发现：出现重复状态时，取其中\(\text{dp}\)值较大的下一步状态即可

namespace pt2{
	ll A[70],Ac,B[70],Bc;
	ll dp[70][2][2];

	ll dfs(int p,int lim1,int lim2){
		if(p==0) return 1;
		if(~dp[p][lim1][lim2]) return dp[p][lim1][lim2];
		ll res=0,a=lim1?A[p]:1,b=lim2?B[p]:1;
		rep(i,0,a) rep(j,0,b) if((i|j)==T[p]) res+=dfs(p-1,lim1&&i==a,lim2&&j==b);
		if(a==1 && b==1 && T[p]==1) res-=min(dfs(p-1,lim1,0),dfs(p-1,0,lim2));
         // 减去较小的，就是取较大的
		return dp[p][lim1][lim2]=res;
	}

	ll Calc(ll n,ll m){
		Ac=Bc=0;
		memset(A,0,sizeof A),memset(B,0,sizeof B);
		while(n) A[++Ac]=(n&1),n>>=1;
		while(m) B[++Bc]=(m&1),m>>=1;
		memset(dp,-1,sizeof dp);
		return dfs(max(Tc,max(Ac,Bc)),1,1);
	}
	void Solve(){ printf("%lld\n",Calc(R1,R2)); }
}

Subtask3

设两个数分别取\(x,y\),且\(x\and y=i\)，枚举\(i\)，然后再枚举\(x\),就能得到计算得出\(y\)，检查每一个\(i\)是否存在方案

复杂度为\(O(3^{|T|})\)

namespace pt3{
	void Solve(){
		int ans=0;
		for(ll i=Tx;;i=(i-1)&Tx) {
			int fl=0;
			for(ll j=(Tx^i);;j=(j-1)&(Tx^i)) {
				ll x=j|i,y=Tx+i-x;
				assert((x|y)==Tx && (x&y)==i);
				if(x>=L1 && x<=R1 && y>=L2 && y<=R2) {
					fl=1;
					break;
				}
				if(!j) break;
			}
			ans+=fl;
			if(!i) break;
		}
		printf("%d\n",ans);
	}
}

Subtask4

同\(Subtask2\)一样，都可以通过枚举发现同样的结论，所以只需要给\(\text{dp}\)状态加上两维即可AC

namespace pt4{
	ll A[70],Ac,B[70],Bc,C[70],Cc,D[70],Dc;
	ll dp[70][2][2][2][2];

	ll dfs(int p,int lim1,int lim2,int lim3,int lim4){
		if(p==0) return 1;
		if(~dp[p][lim1][lim2][lim3][lim4]) return dp[p][lim1][lim2][lim3][lim4];
		ll res=0;
		int a=lim1?A[p]:0,b=lim2?B[p]:1;
		int c=lim3?C[p]:0,d=lim4?D[p]:1;

		rep(i,a,b) rep(j,c,d) if((i|j)==T[p]) 
            res+=dfs(p-1,lim1&&i==a,lim2&&i==b,lim3&&j==c,lim4&&j==d);
		if(a==0 && b==1 && c==0 && d==1 && T[p]==1) {
			res-=min(dfs(p-1,lim1&&0==a,lim2&&0==b,lim3&&1==c,lim4&&1==d),
			dfs(p-1,lim1&&1==a,lim2&&1==b,lim3&&0==c,lim4&&0==d));
		}
		return dp[p][lim1][lim2][lim3][lim4]=res;
	}

	ll Calc(){
		Ac=Bc=0;
		while(L1) A[++Ac]=(L1&1),L1>>=1;
		while(R1) B[++Bc]=(R1&1),R1>>=1;
		while(L2) C[++Cc]=(L2&1),L2>>=1;
		while(R2) D[++Dc]=(R2&1),R2>>=1;
		memset(dp,-1,sizeof dp);
		ll l=0;
		cmax(l,Ac),cmax(l,Bc),cmax(l,Cc),cmax(l,Dc),cmax(l,Tc);
		return dfs(l,1,1,1,1);
	}
	void Solve(){ printf("%lld\n",Calc()); }
}

LOJ 6274 数字(数位dp)

原文：https://www.cnblogs.com/chasedeath/p/12743841.html