总结
1. 假设 n == 2212, 算法分为两个步骤. 第一步, 将这个 2212 个数分为 1~ 212, 213 ~ 2212
2. 第一部分实际上是将 n 的规模缩小到 212. 假如知道如何求解 n = 2212, n = 212 就肯定也能求出
3. 第二部分可以再分为 3 个小步骤
3.1 求解 213~2212 最高位上 1 的个数, 1000~1999, 共 1000 个
3.2 假如 n = 1212, 最高位上 1 的个数就是 213 个, 因为最高位上 1 个个数需要根据最高位上的值来讨论
3.3 计算后三位 1 出现的次数. 书上是这么描述的, 将某一位设置成 1, 其他两位各有 10 种选择, 所以 1 的个数是 3(3位分别设为 1 ) * 10 * 10, 因此 001~999 共有 300个1
4. 上面的步骤组合起来就是解
在第 3.3 步中, 求解 0 ~ 999* 中, 1 的个数时, 用一步全排列就能直接求出, 但逻辑上不太直接. 其背后的理论是, 每次仅关注某一位上 1 的个数. 对于 111 这种数, 其会被算 3 次, 因为它三位都含 1 , 所以不存在冲突什么的. 但题目若是修改成, 求解含 1 个数的个数, 那就不能不考虑冲突了, 就需要使用 c(4,3)*9 blabla 的了
代码, 没能 Pass 九度 oj
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <cstring> #include <math.h> using namespace std; char fir[3000]; char sec[3000]; int numof1(char *str) { int len = strlen(str); if(len == 1 && (*str) >= '1') return 1; if(len == 1 && (*str)== '0') return 0; int fir_pt = 0, sec_pt = 0, third_pt = 0; int first = (*str) - '0'; if(first > 1) { fir_pt = pow(10, len-1); }else{ fir_pt = atoi(str+1)+1; } sec_pt = first * (len-1)* pow(10, len-2); third_pt = numof1(str+1); return fir_pt + sec_pt + third_pt; } int main() { int a, b; while(scanf("%d%d", &a, &b) != EOF) { if(a <= 0) a = 0; else a = a-1; snprintf(fir, sizeof(fir), "%d", a); snprintf(sec, sizeof(sec), "%d", b); //printf("%s %s ", fir, sec); //printf("%s ", sec); int pt1 = numof1(fir); int pt2 = numof1(sec); printf("%d ", pt2-pt1); } return 0; }