题目：数字1的数量
思路：首先考察不同位数以内的所有整数出现1的次数，例如四位数以内[0,9999]，个十百千位均有可能出现1，
出现1的时候，其它三个位均可以是0~9，所以假设固定一个位为1，另外三个位的可能性是10*10*10
所以总共出现4*10*10*10 = 4000次1，所以一个完整的k位数中包含1的个数是k * 10^(k-1)
对于一个数字n，可以将十进制拆成[p1][p2...pk]的形式，
如果p1==0，n = [p2...pk] = [p2][p3...pk]，转化为子问题
如果p1==1，这时包含了三种情况
1> p1位=0时，后边k-1位包含 (k-1) * 10^(k-2)个1
2> p1位=1时，p1位重复了[p2...pk] + 1 个1
3> p1位=1时，[p2...pk]出现1的次数（这是一个子问题，可以递归）
如果p1 > 1，这时包含了三种情况
1> p1位=0,1...p1-1时（共p1个可能），后面k-1位包含 (k-1) * 10^(k-2)个1
2> p1位=1时，p1位重复了10^(k-1)个1
3> p1位=p1时，[p2...pk]出现1的次数（这是一个子问题，可以递归）
代码是根据这个原理从后往前累加的
容易得到状态转移方程：设dp[i]为数位i及其之后的数位的1出现次数；len为数的长度；k为当前dp[i]的位置；a[i]用于存储数；
if(a[i] == 0) dp[i] += dp[i+1];
if(a[i] == 1) dp[i] += (k-1) * 10^(k-2) + [a[i+1]..a[len]] + 1 +dp[i+1];
if(a[i] > 1) dp[i] += a[i] * (k-1) * 10^(k-2) + 10^(k-1) + dp[i+1];
#include <iostream> #include <algorithm> #include <stdlib.h> #include <time.h> #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <queue> #include <stack> #include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define zero_(x,y) memset(x , y , sizeof(x)) #define zero(x) memset(x , 0 , sizeof(x)) #define MAX(x) memset(x , 0x3f ,sizeof(x)) #define swa(x,y) {LL s;s=x;x=y;y=s;} using namespace std ; #define N 50005 const double PI = acos(-1.0); typedef long long LL ; char num[20]; LL dp[20]; int len,number; int pow(int k){ int s =1; for(int i = 0; i<k; i++)s*=10;return s;} LL cal(){ zero(dp); int base = 1; int k; for(int i = len-1; i >= 0; i--){ int s = num[i] - '0'; k = len - i; if(s == 0) dp[i] += dp[i+1]; if(s == 1) dp[i] += (k-1)*pow(k-2) + number + 1 + dp[i+1]; if(s > 1) dp[i] += s*(k-1)*pow(k-2) + pow(k-1) +dp[i+1]; //cout<<i<<" "<<dp[i]<<endl; number += base * s; base *= 10; } return dp[0]; } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(false); cin.tie(0); scanf("%s", num); len = strlen(num); number = 0; printf("%I64d ",cal()); return 0; }