首页 > 代码库 > Balanced Numbers数位dp
Balanced Numbers数位dp
三进制搞下, 0 表示没出现过, 第i位为1 表示 i出现了奇数次, 2表示i 出现了偶数次。
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;typedef long long LL;LL dp[20][101111];int up[11111];int judge(int x){ int ans=0; int a[10]; memset(a,0,sizeof(a)); while(x){ a[ans++]=x%3; x/=3; } for(int i = 0 ;i< ans;i++){ if(a[i]==1&&(i&1)) return 0 ; if(a[i]==2&&!(i&1)) return 0; } return 1;}int change(int x,int i){ int ans=0 ;int a[10]; memset(a,0,sizeof(a)); while(x){ a[ans++]=x%3; x/=3; } if(a[i]==0) a[i]=1; else if(a[i]==1) a[i]=2; else if(a[i]==2) a[i]=1; int ans1=0; for(int i = 9;i>=0;i--) ans1=ans1*3+a[i]; return ans1;}LL gao(int now,int gaojici,int first,int flag){ if(now<=0) return judge(gaojici); if(!flag&&~dp[now][gaojici]) return dp[now][gaojici]; LL limit = flag? up[now]: 9,ret=0; for(LL i= 0;i<=limit;i++){ LL kk=change(gaojici,i); ret+=gao(now-1,(first||i)?kk:0,first||i,flag&&limit==i); } return flag? ret: dp[now][gaojici]=ret;}LL solve(LL x){ int len=0; while(x){ up[++len]= x%10; x/=10; } return gao(len,0,0,1);}int main(){ int Icase;LL b;LL a; memset(dp,-1,sizeof(dp)); scanf("%d",&Icase); while(Icase--){ cin>>a>>b; cout<<solve(b)-solve(a-1)<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。