首页 > 代码库 > UVA 1640 The Counting Problem UVA1640 求[a,b]或者[b,a]区间内0~9在里面各个数的数位上出现的总次数。
UVA 1640 The Counting Problem UVA1640 求[a,b]或者[b,a]区间内0~9在里面各个数的数位上出现的总次数。
/** 题目:UVA 1640 The Counting Problem UVA1640 链接:https://vjudge.net/problem/UVA-1640 题意:求[a,b]或者[b,a]区间内0~9在里面各个数的数位上出现的总次数。 思路:数位dp; dp[leadzero][i][j][k]表示前面是否选过非0数,即i长度之后可以第一个出现0,而不是前导0,长度为i,前面出现j,k次,j出现的次数。 */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<set> #include<cmath> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf = 0x3f3f3f3f; const int maxn = 1e5+100; int dp[2][10][10][10];///dp[leadzero][i][j][k]表示前面是否选过非0数,即i长度之后可以第一个出现0,而不是前导0,长度为i,前面出现j,k次,j出现的次数。 int digit[10]; ll n; int l[10], r[10]; int dfs(int leadzero,int len,int value,int bounded,int cnt) { if(len==0){ return cnt; } if(!bounded&&dp[leadzero][len][value][cnt]!=-1) return dp[leadzero][len][value][cnt]; int d = bounded?digit[len]:9; int ans = 0; for(int i = 0; i <= d; i++){ if(leadzero){ ans += dfs(1,len-1,value,bounded&&(i==d),cnt+(i==value)); }else { if(i==0) ans += dfs(0,len-1,value,bounded&&(i==d),cnt); else ans += dfs(1,len-1,value,bounded&&(i==d),cnt+(i==value)); } } if(!bounded){ dp[leadzero][len][value][cnt] = ans; } return ans; } void cal(int n,int x[]) { int len = 0; while(n){ digit[++len] = n%10; n /= 10; } for(int j = 0; j < 10; j++){ x[j] = dfs(0,len,j,true,0); } } int main() { int a, b; memset(dp, -1, sizeof dp); while(scanf("%d%d",&a,&b)==2) { if(a==0&&b==0) break; if(a>b) swap(a,b); cal(a-1,l); cal(b,r); for(int i = 0; i < 9; i++){ printf("%d ",r[i]-l[i]); } printf("%d\n",r[9]-l[9]); } return 0; }
UVA 1640 The Counting Problem UVA1640 求[a,b]或者[b,a]区间内0~9在里面各个数的数位上出现的总次数。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。