PAT 1049 Counting Ones[dp][难]
DP PAT Counting
2023-09-14 09:11:24 时间
1049 Counting Ones (30)(30 分)
The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's in 1, 10, 11, and 12.
Input Specification:
Each input file contains one test case which gives the positive N (<=2^30^).
Output Specification:
For each test case, print the number of 1's in one line.
Sample Input:
12
Sample Output:
5
题目大意:给出一个数字N,你要找出所有1-N中包含的1的个数。N<=2^30。
//N还挺大的。猛一看很简答,直接遍历就行,但是数据量太大。如果使用动态规划,化解成子问题,怎么做呢?
代码来自:https://www.liuchuo.net/archives/2305
我还不太懂,明天再看一遍这数学问题。
#include <iostream> #include<stdio.h> using namespace std; int main() { int n, left = 0, right = 0, a = 1, now = 1, ans = 0; scanf("%d", &n); while(n / a) { left = n / (a * 10), now = n / a % 10, right = n % a; if(now == 0) ans += left * a; else if(now == 1) ans += left * a + right + 1; else ans += (left + 1) * a; a = a * 10; } printf("%d", ans); return 0; }
相关文章
- autosize px转dp_Android 屏幕适配以及autoSize的原理.md
- px像素和dp像素密度区别[通俗易懂]
- 高质量DP压轴,非常精彩的比赛。LeetCode周赛第282场
- acwing1068. 环形石子合并(区间dp+前缀和)「建议收藏」
- leetcode-124. 二叉树中的最大路径和(树形dp)
- 蓝桥杯 历届试题 对局匹配(dp满分通过)---C语言
- 蓝桥杯算法训练 金陵十三钗(dp状态压缩)------C语言—菜鸟级
- 【面试高频题】难度 3/5,可直接构造的序列 DP 题
- DP(10%状压+90%思维)
- 【Android UI】绘制圆角矩形进度条 ① ( 像素值转化 dp -> px | Paint 标志位设置 | Paint 画笔线帽样式设置 | Paint 画笔线段连接处样式设置 )
- 深入探索DP文件与Oracle的关系(dp 文件 oracle)
- 关于实现代码语法标亮dp.SyntaxHighlighter