思路清看代码
#include <bits/stdc++.h> #define int long long #define rep(x,y,z) for(int x = y ; x <= z ; x ++) using namespace std ; int f[20][20] , a[20] ; int calc(int x) { int len = 0 ; while(x>0) {//江数位拆开以便于处理 a[++len] = x % 10 ; x /= 10 ; }int sum = 0 ;//用于统计答案 //先求len-1位的 for(int i = 1 ; i <= len-1 ; i ++) {//枚举位数 for(int j = 1 ; j <= 9 ; j ++) { sum += f[i][j] ; } } //然后求len位,最高位比len位的数小的 for(int i = 1 ; i < a[len] ; i ++) { sum += f[len][i] ; } //然后是len位,最高位与原数相同的 for(int i = len - 1 ; i >= 1 ; i --) {//枚举每一位 for(int j = 0 ; j <= a[i]-1 ; j ++) {//枚举i位上的数字 if(abs(j-a[i+1]) >= 2) { sum += f[i][j] ;//如果和上一位相同,就相加 } }if(abs(a[i+1]-a[i]) < 2) break ; } return sum ; } int n , m ; signed main() { scanf("%lld%lld",&n,&m) ; rep(i,0,9) f[1][i] = 1 ;//初始化,[0,9]都是windy数 for(int i = 2 ; i <= 10 ; i ++) {//枚举位数 for(int j = 0 ; j <= 9 ; j ++) {//枚举最高位的数 for(int k = 0 ; k <= 9 ; k ++) {//枚举下一位的数 if(abs(k-j) >= 2) f[i][j] += f[i-1][k] ; } } } cout << calc(m+1) - calc(n) << endl ; return 0 ; } /* f[i][j] , 位数为i最高位数字为j的个数 f[i][j] += f[i-1][k] |k-j| >= 2 */