首页 > 代码库 > [数位dp] spoj 10606 Balanced Numbers
[数位dp] spoj 10606 Balanced Numbers
题意:
对于一个数的每个位上的数。
对于每个奇数,如果出现必须出现偶数次。
对于每个偶数,如果出现必须出现奇数次。
思路:
用三进制存储每个数出现的状态,0没出现,1出现奇数次,2出现偶数次。
然后其他和普通数位dp就一样了。
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; //2014年9月25日10:03:08 long long dp[22][180000]; int num[22]; int ok(int x) { int v[50],cnt=0; while(x) { v[cnt++]=x%3; x/=3; } for(int i=0;i<cnt;i++) { if(!v[i]) continue; if(i%2==0&&v[i]!=1) return 0; if(i%2!=0&&v[i]!=2) return 0; } return 1; } int js(int n,int x) { int v[50],cnt=0,tep=0; memset(v,0,sizeof(v)); while(n) { v[cnt++]=n%3; n/=3; } if(v[x]<2) v[x]++; else v[x]=1; for(int i=9;i>=0;i--) tep=tep*3+v[i]; return tep; } long long dfs(int site,int n,int zero,int f) { if(site==0) { if(zero) return 0; return ok(n); } if(!f&&!zero&&~dp[site][n]) return dp[site][n]; int len=f?num[site]:9; long long ans=0; for(int i=0; i<=len; i++) { if(zero) { if(i==0) ans+=dfs(site-1,n,zero&&i==0,f&&i==len); else ans+=dfs(site-1,js(n,i),zero&&i==0,f&&i==len); } else ans+=dfs(site-1,js(n,i),zero&&i==0,f&&i==len); } if(!f&&!zero) dp[site][n]=ans; return ans; } long long solve(long long x) { int cnt=0; while(x) { num[++cnt]=x%10; x/=10; } return dfs(cnt,0,1,1); } int main() { int t; cin>>t; memset(dp,-1,sizeof(dp)); while(t--) { long long x,y; scanf("%lld%lld",&x,&y); printf("%lld\n",solve(y)-solve(x-1)); } return 0; } //2014年9月25日10:39:37
[数位dp] spoj 10606 Balanced Numbers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。