基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题
收藏
关注给定一个十进制正整数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示例
12
Output示例
5
没怎么学过数位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;
}