有关数字每一位的性质的计数问题
题目
不要62
题意
- 给定一个区间[n, m],求在区间内的数字中不包含62(6和2需要连在一起)和4的数字的个数
题解
- 状态设计:dp[i][j],长度为i的数字,最高位为j的符合条件的数字的个数。
- 状态转移方程:
j \(\neq\) 4时:
dp[i][j] = \(\sum_{k=0}^9 dp[i-1][k](j\neq6 || k\neq2)\)
- 边界:dp[0][0] = 1;
- 结果:扫一遍需要取到的dp[i][j],求和.
思路的博客:
不要62
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include <bits/stdc++.h> using namespace std; int dp[9][10]; int bits[8]; void init(){ dp[0][0] = 1; for(int i=1; i<=8; i++){ for(int j=0; j<=9; j++) for(int k=0; k<=9; k++){ if(j != 4 && !(j==6&&k==2)){ dp[i][j] += dp[i-1][k]; } } } } int n, m; int solve(int n){ int len = 1; while(n){ bits[len++] = n%10; n /= 10; } bits[len] = 0; int ans = 0; for(int i=len-1; i>=1; i--){ for(int j=0; j<bits[i]; j++){ if( j!=4 &&!(bits[i+1] ==6&&j ==2)) ans += dp[i][j]; } if(bits[i] == 4||(bits[i+1] == 6&&bits[i] == 2)) break; } return ans; } int main() { init(); while(~scanf("%d%d", &n, &m)&&n+m!=0){ printf("%d\n", solve(m+1)-solve(n)); } return 0; }
|
递归的写法:
未解决的问题