## 题目 ##
给定一个十进制正整数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的个数
Sample Input
12
Sample Output
5
题意分析：这个题呢，刚开始我也没有写出来，应为思维被固化了，总是在想 “有几个1”，想通过排列组合来解决，但是发现很复杂，要考虑的方面很多，最后看了看解题思路。原来要把寻找“有几个1” 变成 寻找“每一位上面有几个含有1的数字”，然后把每一位上面含有1的数字的个数，加起来就可以了。思路很简单，接下来还要分析每一位上面含有1的数字的个数。总体来说有三种情况（假设数字n为：a5a4a3a2a1a0, 下面我们先针对 a2 进行分析）：
《1》a2 == 0
这时候呢，a2前面剩下的高位，只有在 【0， a5a4a3-1】这个范围内，才会让a2出现1的情况，该为含有1的数的个数为：(a5a4a3-1 - 0 + 1) * (10的i次方），（这里i是2）。
《2》a2 > 1
这个情况和上面等于0的情况类似，只是高位的数字不用减一就可以满足出现1的情况了高位范围是：【0，a5a4a3】，该位含有1的数字的个数为：(a5a4a3 - 0 + 1) * (10的i次方），（这里i是2）。
《3》a2 == 1
这个情况相对来说要特殊一点，前面两种都是只用考虑高位数字即可，这种情况还要考虑低位数字，应为1刚好是处于0和大于1的数字之间，所以要在第一种情况的基础之上还要加上低位数字的个数，加上：a1a0 + 1
另外可能我的方法可能不是很好，还需要考虑该为数字是不是最高位的问题，当最高位== 1 的时候，只需要加上低位的数字即可，如a4a3a2a1a0 + 1; 如果最高位大于1，那么就直接加上（10的i次方）这里的i表示5。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;int Shift(int *arr, int n)//将数字n的每一位放到数组当中，并返回位长
{int index = 0;while (n){arr[index++] = n % 10;n /= 10;}return index;
}int demo(int *arr, int s, int e, int mark)//计算数据
{int sum = 0;for (int i = e; i >= s; i--){if (mark == i)sum = sum * 10 + arr[i] - 1;else sum = sum * 10 + arr[i];}return sum;
}int fact(int n)// 返回10的n次方
{int area = 1;for (int i = 0; i < n; i++)area *= 10;return area;
}int main()
{int n;int arr[15];LL one_num = 0;int len = 0;scanf("%d", &n);memset(arr, 0, sizeof(arr));len = Shift(arr, n);for (int i = 0; i < len-1; i++){if (arr[i] == 0){one_num += (demo(arr, i+1, len-1, i+1) + 1) * fact(i);}else if (arr[i] == 1){one_num += (demo(arr, i+1, len-1, i+1) + 1) * fact(i) + demo(arr, 0, i-1, -1) + 1;}else if (arr[i] > 1){one_num += (demo(arr,i+1,len-1,-1) + 1) * fact(i);}}//最高位特判if (arr[len-1] == 1)one_num += demo(arr, 0, len-1-1, -1) + 1;else if (arr[len-1] > 1)one_num += fact(len-1);printf("%d\n", one_num);return 0;
}