mysql dp.cal 显示汉子_计算1到N中各个数字出现的次数 --数位DP
题意：给定一个数n，问从1到n中，0~9这10个数字分别出现了多少次。比如366这个数，3出现了1次，6出现了2次。
题解：《剑指offer》P174；《编程之美》P132 都给出了统计数字1的O(log(n))的解法。把他们进行改进就得到了这个问题的答案。
下面这个代码是我改的剑指offer的，也有类似编程之美的：传送门。
//《剑指offer》P174
#include
using namespace std;
int pow1(int n,int len)//注意算的时候不要用math里的pow 会产生误差
{
int ans=;
while(len--) ans*=n;
return ans;
}
int cal(char *c,int i)
{
int len=strlen(c);
int f=*c-'',g=*(c+)-'';
if(len==&&(f
if(len==&&f>=i) return ;
int a1=,a2=,a3=;
if(i==||f
else if(f>i) a1=pow1(,len-);
else if(f==i) a1=atoi(c+)+;
a2=f*(len-)*pow1(,len-);
if(g==&&i==) a2=a2-pow1(,len-)+atoi(c+)+;
a3=cal(c+,i);
return a1+a2+a3;
}
int solve(int n,int i)
{
char c[];
sprintf(c,"%d",n);
return cal(c,i);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
for(int i=;i
printf("%d%c",solve(n,i),i==?'\n':' ');
}
return ;
}
官方标程：
#include
using namespace std;
vector solve(int n) {
vector res(, );
if(!n) return res;
if(n % < ) {
res = solve(n - );
while(n) {
res[n % ]++;
n /= ;
}
return res;
}
res = solve(n / );
for(int i = ; i < ; i++) res[i] = res[i] * + n / + (i > );
return res;
}
int main() {
int n;
cin >> n;
vector ans = solve(n);
for(int i = ; i < ans.size(); i++) {
i == ? cout << ans[i] : cout << " " << ans[i];
}
return ;
}
C语言：统计整型变量m中各数字出现的次数，-去掉一个最高分和一个最低分，然后求平均值，(注意最低分和最高分可能有多个数并列)
//统计整型变量m中各数字出现的次数,并存放在数组a中,其中,a[0]存放0出现的次数,a[1]存放1出现的次数. #include ]) { int i; ; i&l ...
计算1到N中包含数字1的个数
转自:http://pandonix.iteye.com/blog/204840 Mark N为正整数,计算从1到N的所有整数中包含数字1的个数.比如,N=10,从1,2...10,包含有2个数字1. ...
笔试算法题(30)：从已排序数组中确定数字出现的次数 &; 最大公共子串和最大公共序列(LCS)
出题:在已经排序的数组中,找出给定数字出现的次数: 分析: 解法1:由于数组已经排序,所以可以考虑使用二分查找确定给定数字A的第一个出现的位置m和最后一个出现的位置n,最后m-n+1就是A出现的次数: ...
51nod 1009 - 数字1的数量 - [数位DP][模板的应用以及解释]
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1009 基准时间限制:1 秒 空间限制:131072 KB 给 ...
51Nod 1009 数字1的个数 | 数位DP
题意: 小于等于n的所有数中1的出现次数 分析: 数位DP 预处理dp[i][j]存 从1~以j开头的i位数中有几个1,那么转移方程为: if(j == 1) dp[i][j] = dp[i-1][9 ...
1009 数字1的数量 数位dp
1级算法题就这样了,前途渺茫啊... 更新一下博客,我刚刚想套用数位dp的模板,发现用那个模板也是可以做到,而且比第二种方法简单很多 第一种方法:我现在用dp[pos][now]来表示第pos位数字为 ...
51nod 1009 数字1的数量 数位dp
1009 数字1的数量 基准时间限制:1 秒 空间限制:131072 KB 给定一个十进制正整数N,写下从1开始,到N的所有正数,计算出其中出现所有1的个数. 例如:n = 12,包含了5个1 ...
nyoj281 整数中的1(二) 数位DP
和整数中的1一毛一样.就是输入时改了一下罢了. AC代码: #include const int maxn = 35; int w[maxn], h[maxn]; void ...
51nod 1042 数字0-9的数量 数位dp
1042 数字0-9的数量 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 收藏 关注 给出一段区间a-b,统计这个区间内0-9出现的次数. 比如 10-1 ...
随机推荐
js继承方式
1.原型链 实现的本质是重写原型对象,代之以一个新类型的实例: 给原型添加方法的代码硬顶放在替换原型的语句之后: 不能使用对象字面量查收能见原型方法,这样会重写原型链. 缺点:包含引用类型值的原型属性 ...
常用jar包用途
jar包 用途 axis.jar SOAP引擎包 commons-discovery-0.2.jar 用来发现.查找和实现可插入式接口,提供一些一般类实例化.单件的生命周期管理的常用方法. jaxrp ...
cocos2d-x之初试内存管理机制
bool HelloWorld::init() { if ( !Layer::init() ) { return false; } Size visibleSize = Director::getIn ...
#if...#endif的用法总结
在写到 pwm音阶程序的时候,在代码中有#if...#endif的用法问题,相关音阶的代码如下: /************************************************* ...
【HDOJ】1606 Excuses, Excuses!
简单字符串. #include #include #define MAXLEN 105 #define MAXN 25 char keys ...
mvc Action上面加 [HttpPost]
mvc Action上面加 [HttpPost] 意思就是这个action只能响应post请求. 如果发get请求这里是没有响应的
通过ViewPager 实现图片轮播
通过ViewPager 实现图片轮播 首先来个效果图 布局文件: LinearLayout 用来存放下方的几个小白点. <?xml version="1.0" encodin ...
跨年操作--new Date()
//时间在2017/12/31 17:00 --- 2018/1/1 06:00区间,提示用户无法操作公告. //time.js (function(){ var date = new Date(); ...
bzoj千题计划236：bzoj2300: [HAOI2011]防线修建
http://www.lydsy.com/JudgeOnline/problem.php?id=2300 维护动态凸包,人懒用的set 用叉积判断,不要用斜率 #include ...
硬盘img镜像备份工具
linux下使用dd,Windows下使用WinImage,不过dd使用的比较多.