题解：CF2086E Zebra-like Numbers

一道不那么板的数位 DP，感觉思路很清奇。

显然斑马数不超过

30

个，记斑马数为

num_i

，那么答案是一个多项式的形式，考虑将其转化为进制的形式。

考虑这个进制，由于斑马值是最小的系数和，从高位到低位贪心一定是最优的。并且由于有

num_i=num_{i-1}\times 4+1

，所以每一位上的数值都不大于

4

，并且如果有一位为

4

，则它的更低位一定是

0

。

那么 DP 状态为

dp_{i,j,lim1,lim2}

，表示当前

pos

位，数位和为

j

，是否达到数值限制，是否出现了

4

，转移即可。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
bool mbs;
ll t,l,r,k,num[32],val[32],dp[32][100][2][2];
ll dfs(int pos,int sum,int lim1,int lim2){
	if(!pos) return sum==k;
	if(dp[pos][sum][lim1][lim2]!=-1) return dp[pos][sum][lim1][lim2];
	int up=4;ll res=0;
	if(lim2) up=0;
	else if(lim1) up=val[pos];
	for(int i=0;i<=up;i++) res+=dfs(pos-1,sum+i,lim1&&i==val[pos],lim2||i==4);
	return dp[pos][sum][lim1][lim2]=res;
}
inline ll get_val(ll x){
	for(int i=30;i>=1;i--) val[i]=(x/num[i]),x-=(x/num[i])*num[i];
	memset(dp,-1,sizeof(dp));
	return dfs(30,0,1,0);
}
inline void solve(){
	l=read(),r=read(),k=read();
	printf("%lld\n",get_val(r)-get_val(l-1));
}
bool mbt;
int main(){
//	cout<<(&mbs-&mbt)/1024.0/1024.0<<endl;
	num[1]=1;
	for(int i=2;i<=30;i++) num[i]=num[i-1]*4+1;
	t=read();
	while(t--) solve();
	return 0;
}

题解：CF2086E Zebra-like Numbers

文章操作

相关推荐

评论

题解：CF2086E Zebra-like Numbers