51nod 1009：数字1的数量

不念不忘少年蓝@ 2021-12-21 00:25 207阅读 0赞

[1009 数字1的数量][1009 _1] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 [难度：1级算法题][1]

![star.png][] 收藏

![plus.png][] 关注

给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。

例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

Input

输入N(1 <= N <= 10^9)

Output

输出包含1的个数

Input示例

Output示例

没怎么学过数位dp，打算好好搞一下~

dp\[x\]代表1~10^x-1 中1出现的次数，当然0~9出现的次数都是这个。

然后从后往前扫，假设该位的值是digit，那么如果digit大于1就加上digit\*dp\[len-1\]。len代表当前扫描的长度。

然后还有就是以1开头的pow(10,len-1)，后面的数字任意，会发现这个时候算重复了反而是正确的，因为比方说11计算了两次，但也因为11有两个1，所以从不同的角度计算出来的11就不用考虑重复的情况了。

如果digit等于1，有一些麻烦，那么就等于原来的数量result(把它想象成在以1开头的数里面，这里面1的数量就是原来的result) + dp\[len-1\]这个数量，剩下的就是有多少个以1开头的数字，这个头还没有算，而这个数量就是除了1开头剩下的tail的数量。

好比141，到第三个1的时候，实际上已经算出了1~41的1的数量，那我把这个数量想象成是在100~141里面除开开头的1的数量，加上42个开头的1，这个还没算。然后还有的就是1~99的1的数量。

代码：

#include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <string>
    #include <cstring>
    #pragma warning(disable:4996)
    using namespace std;
    
    typedef long long ll;
    
    ll s;
    ll dp[20];
    
    void init()
    {
    	memset(dp, 0, sizeof(dp));
    	
    	int i, j;
    	for (i = 1; i <= 19; i++)
    	{
    		for (j = 0; j <= 9; j++)
    		{
    			dp[i] = dp[i - 1] * 10 + pow(10, i - 1);
    		}
    	}
    }
    
    ll count(ll x)
    {
    	ll result = 0;
    	ll len = 0;
    	ll digit = 0;
    	ll radix = 1;
    	ll tail = 0;
    	while (x != 0)
    	{
    		digit = x % 10;
    		x = x / 10;
    		
    		++len;
    		
    		if (digit > 1)
    		{
    			result += radix + digit*dp[len-1];//radix就代表10的多少多少次方，这个时候重复算反而是对的
    		}
    		else if (digit == 1)
    		{
    			result += tail + 1 + dp[len-1];//+1是代表取的那个整数
    		}
    		tail = tail + digit*radix;
    		radix *= 10;
    	}
    	return result;
    }
    
    int main()
    {
    	//freopen("i.txt","r",stdin);
    	//freopen("o.txt","w",stdout);
    	
    	init();
    	
    	cin >> s;
    	cout << count(s)<<endl;
    	
    	//system("pause");
    	return 0;
    }

转载于:https://www.cnblogs.com/lightspeedsmallson/p/5173975.html

[1009 _1]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1009
[ok.png]: http://file.51nod.com/images/icon/ok.png
[1]: http://www.51nod.com/onlineJudge/problemList.html#!groupId=2
[star.png]: http://file.51nod.com/images/icon/star.png
[plus.png]: http://file.51nod.com/images/icon/plus.png