题目链接：点击打开链接
题目大意：给出一个正整数，应该返回 0 到该正整数之间的十进制形式的 1 出现的个数。
解题思路：累加每一位上“1”的组合数情况总和；以下都是前设在范围不能超过所求的数 n 本身的前提下。
（1）将0,1----n数字列出，为了方便这里假设n为121，也就是000-121
（2）首先看所有数字的个位，这里分为三种情况就是 n 的个位大于1、小于1、等于1。
n的个位=1：那么 1 出现的次数为：00“1”-12“1” 前面的数字是变化的从 00-12 有 13 种情况。
n的个位>1: 那么 如 122 的情况 1 出现的次数为：00“1”-12“1” 也是 13，但是如果讨论的是十位就不一样了，这是需要重点考虑的。
n的个位<1：那么 如 120 的情况，1出现的次数为：00“1”-11“1” 出现的情况是 11 次。
（3）对每个十进制位进行讨论，将结果相加。但是当 n 是十位 、百位（非个位的）的情况下，要相对复杂一点，上面的只是启发一下解题思路。
下面的是正式的解题方法：
假设数字为：abcde，对于 abcde 中的每一个数字，可以根据该数字与 1 的关系，求在该数字对应位置上1出现的次数。具体来说：假设我们要求百位出现 1 的次数，此时我们可以根据 c 与 1 的关系，求出百位 1 出现的次数。
（1）如果c = 0，则1出现的次数等于：ab * 100，即（c前面的数 * c对应的基数） 在该情况下，百位出现 1 的次数只与 c 前面的数有关。
（2）如果c = 1，则1出现的次数等于：（ab * 100） + （de + 1），即（c前面的数 * c对应的基数） +（c后面的数 + 1）在该情况下，百位出现 1 的次数与 c 前面和 c 后面的数有关。
（3）如果c >= 2，则1出现的次数等于（ab + 1）*100，即（c前面的数 + 1）* c对应的基数。
i.e. 12145
个位5：(1214+1)*10^0==1215
十位4：(121+1)*10^1==1220
百位1：(12)*10^2+(45+1)==1246
千位2：(1+1)*10^3==2000
万位1：2145+1==2146
Result == 7827
AC 代码
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; int n, len, rs; string s; int fcnt1(int p) { int sum=0,ten=int(pow(10,len-p-1)+0.5),pre=n/(ten*10),post=n%ten; char c=s[p]; if(c=='0') sum+=pre*ten; else if(c=='1') sum+=pre*ten + post+1; else sum+=(pre+1)*ten; return sum; } int main() { stringstream ss; while(cin>>s) { ss<<s; ss>>n; len=s.length(), rs=0; for(int i=0;i<len;i++) rs+=fcnt1(i); printf("%d\n",rs); } return 0; }
