1049 Counting Ones (30 分)【难度: 难 / 知识点: 分治 / DP】

https://pintia.cn/problem-sets/994805342720868352/problems/994805430595731456
方法一: 找规律，分治做法。

//0-999  n
//0-1999 1000+2*n  0-999=n 1000-1999只看千位1000个 1001-1999 不看千位 n个 
//0-2999 1000+3*n
//0-3999 1000+4*n;
//0-4999 1000+5*n;
//0-9999 1000+10*n;

//0-9999 n
//0-19999 n*2+10000;

//2500 == 1000+2*n+f(500)  
//1234 == (b[i]+1)+dfs(n-a[i])+(n-a[i])

#include<bits/stdc++.h>
using namespace std;
int a[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
int b[]={0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000};
int dfs(int n)
{
	if(n==0) return 0;
	int i=0,j=0;
	while(n/a[i]>9) i++;
	j=n/a[i];//首位 
	if(j==1) return b[i]+1+dfs(n-a[i])+(n-a[i]);
	else return b[i]*j+a[i]+dfs(n-j*a[i]);
}
int main(void) 
{
	int n; cin>>n;
	cout<<dfs(n)<<endl;
}

这道题的正解其实是数位DP，是一道非常经典的数位DP板子题
方法二： 数位DP

/*

001~abc-1, 999

abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999

*/
#include<bits/stdc++.h>
using namespace std;
int get(vector<int> nums,int l,int r)
{
	int res=0;
	for(int i=l;i>=r;i--) res=res*10+nums[i];
	return res;
}
int count(int n,int x)
{
	vector<int>num;
	while(n) num.push_back(n%10),n/=10;
	n=num.size();
	int res=0;
	for(int i=n-1-!x;i>=0;i--)
	//处理特殊的情况例如 10 当我们处理1时零的个数 00-09 是10种情况这显然不对
	{
		if(i<n-1)//从第二位,开始算前面的
		{
			res+=get(num,n-1,i+1)*pow(10,i);//默认当前的值不是0,那么有0-abc-1这样的一共这么多种
			if(x==0) res-=pow(10,i);//如果当前位是0,那么得减去前导零的情况
		}
		if(num[i]==x) res+=get(num,i-1,0)+1;//加1的目的是有全0的情况
		else if(num[i]>x) res+=pow(10,i);
	}
	return res;
}
int main(void)
{
	int n; cin>>n;
    cout<<count(n,1);
	return 0;
}