l-r1出现的次数
注意端点处理
垃圾算法书 垃圾代码毁我青春
自己研究写了写
1 #include <iostream> 2 #include <string> 3 #include <string.h> 4 #include<fstream> 5 #include <algorithm> 6 using namespace std; 7 int dp[10][10];//dp[i][j],表示开头是j的i位数满足条件的有多少个 8 //注意计算得到的i位数并不是数学意义上的i位数 最高位可以为0 9 void init() 10 { 11 memset(dp, 0, sizeof(dp));//初始化数组all 0 12 dp[1][1] = 1; 13 for (int i = 2; i <= 7; i++) 14 { 15 for (int j = 0; j<10; j++)//枚举第i位可能出现的数 16 { if (j == 1) 17 dp[i][j] += pow(10,i-1); 18 for (int k = 0; k<10; k++)//枚举第i-1位可能出现的数 19 { 20 dp[i][j] += dp[i - 1][k]; 21 22 } 23 } 24 } 25 } 26 int solve(int n) 27 { 28 init(); 29 int digit[10]; 30 int len = 0; 31 while (n>0)//把我们要计算的数一位一位地存到digit数组中 32 { 33 digit[++len] = n % 10; 34 n /= 10; 35 } 36 digit[len + 1] = 0;//最高位补零（只要不是6），因为下面从最高位开始参考前一位是否和现在构成62 37 int ans = 0;//初始化符合个数 38 int tens = 0,times=0; 39 for (int i = len; i; i--)//从最高位开始 40 { 41 tens = i; times = 0; 42 while (tens <len) 43 { 44 if (digit[tens + 1] == 1) 45 times++; 46 tens++; 47 } 48 if (i != 1) 49 for (int j = 0; j < digit[i]; j++) 50 { 51 ans += dp[i][j]; 52 ans += times*pow(10, i - 1); 53 } 54 else//最后一位 55 for (int j = 0; j <= digit[i]; j++) 56 { 57 ans += dp[i][j]; 58 ans += times*pow(10, i - 1); 59 } 60 } 61 return ans; 62 } 63 int main() 64 { 65 int l, r; 66 while (cin >> l >> r) 67 { 68 if (l + r == 0) 69 break; 70 else 71 { 72 if (r < l) 73 { 74 int temp = r; 75 r = l; 76 l = temp; 77 } 78 cout << solve(r) - solve(l-1) << endl; 79 } 80 } 81 return 0; 82 83 }