题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805430595731456
题目大意：给出一个数字N，求从1到N的所有数字里，出现‘1’的次数总和。
起初想用dp做，然后发现超时了。。于是就转为对字符串的分析。思路是，考虑每一位取’1’时，其他位置的数可以取的范围。所以总程序是对每一个位置遍历，计算这个位置取1时，这串字符串变成数字后不超过N的数字的个数，累加得到结果。
完整代码如下
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;int main() {
int N;scanf("%d", &N);string target = to_string(N);int ret = 0;for (int i = 0; i < target.size(); i++){
int now = target[i] - '0';string str1 = target.substr(0, i);string str2 = target.substr(i+1);int left = 1, right = 1;if (str1.size() != 0)left += stoi(str1);if (str2.size() != 0)right += stoi(str2);if (now > 1)ret += left*(int)pow(10, target.size()-i-1); else if (now == 1)ret += (left-1)*(int)pow(10, target.size()-i-1) + right;elseret += (left-1)*(int)pow(10, target.size()-i-1);}printf("%d", ret);return 0;
}
预处理：得到本位置的数字now，并且得到左右两边的可能取的数字的个数（如果为长度为0，就是只有空这一种情况，取1）
int now = target[i] - '0';string str1 = target.substr(0, i);string str2 = target.substr(i+1);int left = 1, right = 1;if (str1.size() != 0)left += stoi(str1);if (str2.size() != 0)right += stoi(str2);
对每一位数字now，有以下三种情况：
（1）大于1。那么只需要左边的数字小于等于原数字左边部分即可。如：
2 3 4 4 1 0 5 6 （原数字N）
? ? 1 ? ? ? ? ? （可能的数字）
只要左边小于等于23，整个数字一定小于原数字N。可能结果计算如下
if (now > 1)ret += left*(int)pow(10, target.size()-i-1);
（2）等于1。那么左边的数字小于原数字左边部分时，可能结果和（1）一样；左边数字等于原数字左边部分时，只有right种可能。如：
2 3 4 4 1 0 5 6 （原数字N）
? ? ? ? 1 ? ? ? （可能的数字）
左边小于等于2343时情况和（1）一样；左边等于2344时，只有056种可能。
else if (now == 1)ret += (left-1)*(int)pow(10, target.size()-i-1) + right;
（3）小于1。此时左边数字必须小于原数字左边，然后情况和（1）一样。如：
2 3 4 4 1 0 5 6 （原数字N）
? ? ? ? ? 1 ? ? （可能的数字）
只有左边小于等于23440的情况。
elseret += (left-1)*(int)pow(10, target.size()-i-1);