首页 > 代码库 > TOJ 1183 The Counting Problem 数位dp
TOJ 1183 The Counting Problem 数位dp
http://acm.tju.edu.cn/toj/showp1183.html
题意：从a写到b，问每个数字各写了几次。
分析：昨天做了一道how many 0‘s，这题算是拓展。考虑从0..a。1到9是一样的，如果目前考虑的是digit，枚举每位，左边填0..x-1，则右边随便填(10^右边长度），左边填x，如果a的当前位大于digit，那么右边还是随便填，如果等于，只能填0..右边最大值，如果大于则没有。而0不一样在于不能作为一个数的第一位，所以左边只能填1..x-1，还有如果目前枚举的是最高位则不能填0。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 #define debug 0 7 int beg, end; 8 int d[20]; 9 int ans1[15], ans2[15];10 void cal(int x, int ans[])11 {12 for (int i = 0; i < 10; i++) ans[i] = 0;13 if (x == -1) return;14 if (x == 0){15 ans[0] = 1;16 return;17 }18 int len = 0;19 int xx = x;20 while(x){21 d[len++] = x % 10;22 x /= 10;23 }24 x = xx;25 for (int digit = 1; digit <= 9; digit ++){26 int sum = 0, res = x/10, cnt = 0, exp = 1; //res为当前位的左边，cnt为右边，exp为右边随便填的总数27 for (int i = 0; i < len; i++){28 sum = sum + res * exp; //左边填0..res-1，右边随便填29 if (digit < d[i]) sum = sum + exp; //如果小于，左边填res，右边随便填30 else if (digit == d[i]) sum = sum + cnt+1; //相等，即左边到当前位都是在最高的情况，右边只能填0..cnt31 32 if (debug){33 if (digit == 4) printf("%d\n",sum);34 }35 cnt = cnt + d[i] * exp;36 exp *= 10;37 res /= 10;38 }39 ans[digit] = sum;40 }41 int sum = 1, res = x/10, cnt = 0, exp = 1;42 for (int i = 0; i < len; i++){43 if (res > 0) sum = sum + (res-1) * exp; //单独算为0的情况，一个是左边从1开始，还有一个是最高位不能填044 if (d[i]) {45 if (i != len-1) sum = sum + exp;46 }47 else sum = sum + cnt + 1;48 cnt = cnt + d[i] * exp;49 exp *= 10;50 res /= 10;51 }52 ans[0] = sum;53 }54 int main()55 {56 while(scanf("%d %d", &beg, &end))57 {58 if (beg == 0 && end == 0) break;59 if (beg > end) swap(beg, end);60 cal(beg-1, ans1);61 cal(end, ans2);62 if (debug) for (int i = 0; i < 10; i++) printf("%d %d\n", ans1[i], ans2[i]);63 for (int i = 0; i < 10; i++) printf("%d%c", ans2[i]-ans1[i], i==9? ‘\n‘: ‘ ‘);64 }65 return 0;66 }
TOJ 1183 The Counting Problem 数位dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。