首页 > 代码库 > SDUT OJ 1704 数字统计问题
SDUT OJ 1704 数字统计问题
SDUT OJ 1704 数字统计问题
博客原文地址:http://blog.csdn.net/xuechelingxiao/article/details/40930259
昨天晚上学弟问了OJ上这个题,群里说不清楚,就写个解题报告吧。
题目大意:
中文题目,就不翻译了-。-
解题思路:
不知道算不算一个典型的数位DP,反正有点那个意思,感觉确实也可以用记忆话搜索,两个差不多的意思。
我找了一下,这个问题好像是算法设计与实验题解上面的一道题,别的OJ上没有,所以就在自己OJ上做了。
大体的思路就是,对于一个数字,比如1342,想要求出每一个数字出自出现的次数,
对于一个n位的十进制数,从一个n位十进制数的由低到高的第i个数位上,总是连续出现10^i个0,然后是10^i个1……一直到10^i个9,9之后又是连续的10^i个0,这样循环出现。找到这个规律,就可以在常数时间内算出第i个数位上每个数字出现的次数。而在第i个数位上,最后再把前导0的数量去掉就是最后要的答案了。
这样最大的时间复杂度是数字位数,也就是log10(n)的复杂度,所以就不会超时了,最后跑了0ms。
吐槽一下宿舍的网,实在是太卡了,写个博客都这么费劲。。。。。真蛋疼。。。
具体的可以看代码,代码中会有部分解释:
#include <stdio.h> #include <string.h> int a[10], ans[10], len; char s[10]; int main() { a[0] = 1; for(int i = 1; i < 10; ++i) { a[i] = a[i-1]*10; ///a[i]记录 pow(10, i) } int n = 0; scanf("%s", s);///以字符串输入 便于统计长度 len = strlen(s); for(int i = 0; i < len; ++i) { n = n*10+(s[i]-'0'); ///计算 n } // printf("%d\n", n); memset(ans, 0, sizeof(ans)); for(int i = 0; i < len; ++i) { int num = s[i]-'0'; int tmp = n/a[len-i-1]; ans[num] += n+1-tmp*a[len-i-1];///从左到右 到第i+1位数字不变的前提下,第i+1位为num的数量 tmp /= 10; int j = 0; while(j < num) { ans[j++] += (tmp+1)*a[len-i-1]; ///记录当前位置 j 出现的次数 } while(j < 10) { ans[j++] += tmp*a[len-i-1]; ///记录当前位置 j 出现的次数 } ans[0] -= a[len-i-1]; ///去掉前导零的数目 // printf("%d\n", ans[0]); } for(int i = 0; i < 10; ++i) { printf("%d\n", ans[i]); ///打印结果 } return 0; }
SDUT OJ 1704 数字统计问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。