思路一：暴力解法，遍历1~n，通过循环判断每个页码中各数字出现的次数(略)
思路二：参考《编程之美》132页求数字中1的个数
/*****************************牛客统测********************************** * 统计页码 * XSH/2017/3/12 *题目描述 *牛牛新买了一本算法书，算法书一共有n页，页码从1到n。牛牛于是想了一个算法题 *目：在这本算法书页码中0~9每个数字分别出现了多少次？ * *输入描述 : *输入包括一个整数n(1 ≤ n ≤ 1,000,000,000) * *输出描述 : *输出包括一行10个整数，即0~9这些数字在页码中出现的次数，以空格分隔。行末无空格。 *如果n不是超级素数幂，则输出No * *输入例子: *999 * *输出例子 : *189 300 300 300 300 300 300 300 300 300 ************************************************************************/ long long numOfEach(long long n, int i) //统计单个数字 { long long count = 0; long long iFactor = 1; long long iLowerNum = 0; long long iCurNum = 0; long long iHigherNum = 0; while (n / iFactor) { iLowerNum = n - (n / iFactor)*iFactor; iCurNum = (n / iFactor) % 10; iHigherNum = n / (iFactor * 10); if (iCurNum<i) count += iHigherNum*iFactor; else if (i==iCurNum) count += iHigherNum*iFactor + iLowerNum + 1; else if (iCurNum>i) count += (iHigherNum + 1)*iFactor; //处理0的个数 //若n为1位数，比如本来是1 2 3 4 5 6 ，之前处理成 0 1 2 3 4 5 6,多加了1个0 //若n为2位数，比如本来是1 2 3 4 5 6 7 8 9 10 11 12，之前处理成 00 01 02 ...09 10 11 12,多加了1+10个0 //若n为3位数，比如本来是1 2 3 4 ... 115，之前处理成000 001 002 ...009 010 011...099 100...115，多加了1+10+100个0 //因此需要在每层循环中减去多计算的0的个数 if (0 == i) count -= iFactor; iFactor *= 10; } return count; } vector<long long>countPage(long long n) //循环统计 { vector<long long>res(10, 0); for (int i = 0; i < 10; ++i) res[i] = numOfEach(n, i); return res; } int main() { long long n; while (cin >> n) { if (n < 1) //输入 { cout << "Input Error !" << endl; return 0; } vector<long long> res = countPage(n); for (int i = 0; i < res.size(); ++i) //输出 0 == i ? cout << res[i] : cout << " " << res[i]; } system("pause"); return 0; }
