PAT1049. Counting Ones (30)(数学)

本文主要是介绍PAT1049. Counting Ones (30)(数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一个n，求从0到n一共出现几个1

思路：

这题还是有点复杂的，看了一下别人的代码，基本思路是一位一位考虑，也就是计算这一位为1的数有几个，用now表示当前位的值，left为左边的数字，right为右边的数字，a为当前位的位数，以3105为例：

• 当now>=2时，比如分为310 5 0，此时now=5也就是说可以取(0~310)1，这些数当前位为1，res+=(left+1)*a
• 当now==1时，比如3 1 05，此时1后面的数不能取全到a，只能取到right，所以res+=left*a+right+1
• 当now==0时，比如31 0 5，此时只能当(0~30)时当前位才能取1，所以res+=left*a

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<string.h>
#include<sstream>
#include<functional>
#include<algorithm>
using namespace std;
const int INF = 0xfffff;
const int maxn = 1050;int main() {int n, left = 0, right = 0, now = 0, a = 1;scanf("%d", &n);int res = 0;while (n / a) {left = n / (a*10);right = n%a;now = n / a % 10;if (now == 0)	res += left*a;else if (now == 1)	res += left*a + right + 1;else res += (left + 1)*a;a *= 10;}printf("%d\n", res);return 0;
}

这篇关于PAT1049. Counting Ones (30)(数学)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---