2 条题解
-
0
#include<bits/stdc++.h> //Feliciano & Rovino using namespace std; //其实和上一道题差不多 typedef long long LL; const int N=30; LL f[N][15], a[N], K; LL calc(LL x){ int len=0, c=1; LL last=0, ans=0; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ for(int j=(i==len? 1: 0); j<a[i]; j++){ if((i==len) || abs(j-last)<=K) ans+=f[i][j];} //唯一不太一样的地方！这里i=len要特判！不能像上一道题一样直接赋值 if((i!=len) && (abs(a[i]-last)>K)) break; last=a[i]; if(i==1) ans++; } for(int i=len-1; i>=1; i--) for(int j=1; j<=9; j++) ans+=f[i][j]; return ans; } int main(){ //freopen("a.in", "r", stdin); memset(f, 0, sizeof(f)); LL a, b; scanf("%lld%lld%lld", &a, &b, &K); for(int i=0; i<=9; i++) f[1][i]=1; for(int t=2; t<=25; t++){ for(int i=0; i<=9; i++){ for(int j=0; j<=9; j++) if(abs(i-j)<=K) f[t][i]+=f[t-1][j]; } } LL x=calc(b), y=calc(a-1); printf("%lld\n", x-y); return 0; } //偷个懒少写点（=7=)v -
0
huangzheng
LV 6
@ 2025-10-8 16:57:30
#include<bits/stdc++.h> //Feliciano & Rovino using namespace std; //其实和上一道题差不多 typedef long long LL; const int N=30; LL f[N][15], a[N], K; LL calc(LL x){ int len=0, c=1; LL last=0, ans=0; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ for(int j=(i==len? 1: 0); j<a[i]; j++){ if((i==len) || abs(j-last)<=K) ans+=f[i][j];} //唯一不太一样的地方！这里i=len要特判！不能像上一道题一样直接赋值 if((i!=len) && (abs(a[i]-last)>K)) break; last=a[i]; if(i==1) ans++; } for(int i=len-1; i>=1; i--) for(int j=1; j<=9; j++) ans+=f[i][j]; return ans; } int main(){ //freopen("a.in", "r", stdin); memset(f, 0, sizeof(f)); LL a, b; scanf("%lld%lld%lld", &a, &b, &K); for(int i=0; i<=9; i++) f[1][i]=1; for(int t=2; t<=25; t++){ for(int i=0; i<=9; i++){ for(int j=0; j<=9; j++) if(abs(i-j)<=K) f[t][i]+=f[t-1][j]; } } LL x=calc(b), y=calc(a-1); printf("%lld\n", x-y); return 0; } //偷个懒少写点（=7=)v
- 1
