题目：处女座对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL N = 2e5 + 5; //限定N变量为只读 LL a[20]; LL dp[20]; LL dfs(LL len,bool limit) { if(len == 0) return 1LL; //longlong类型的1. 某个数*1LL是为了从int类型转成longlong类型 if(!limit && dp[len]) return dp[len]; LL m = (limit) ? a[len] : 9; //如果limit是真（是1或True），m=a【len】; 如果limit是假(是0或false），m=9 LL cnt = 0; for(LL i=0;i<=m;i++) { if(i == 6) continue; cnt += dfs(len-1,limit && (i == m)); } return dp[len] = cnt; } LL six(LL n) { memset(dp,0,sizeof(dp)); LL k = 0; while(n) { a[++k] = n % 10; n /= 10; } return dfs(k,1); } int main() { LL l,r; scanf("%lld %lld",&l,&r); LL ans = (r - l + 1) - (six(r) - six(l-1)); printf("%lld\n",ans); }
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 25; ll dp[N][10]; ll n,m; void init(){ for(int i = 1;i<=20;i++){ for(int j=0;j<=9;j++){ if(j!=6){ for(int k=0;k<=9;k++) dp[i][j]+=dp[i-1][k]; } else{ ll tmp = 1; for(int q=1;q<=i-1;q++) tmp*=10; dp[i][j]=tmp; } } } } int v[N]; ll solve(ll di){ ll res=0; v[0]=0; while(di){ // 将数字存入v数组,并且用v[0]记录位数 v[++v[0]]=di%10; di/=10; } for(int i=v[0];i>=1;i--){ // 逐位排查 for(int j=0;j<v[i];j++){ // 对此位的各种取值可能进行判断 res+=dp[i][j];// 这里面加的dp,如果是含6就会加上所有含有6的那几千万种可能，可能是1000,1000000等 } // 也就是这个大佬的解题思路是 1. 加上各位是6的dp可能 // 2. 加上一个位置是6后的各种位置的花式取值 if(v[i]==6){ // 本位的60000……的10000……种可能已经在前面加过了 ll tmp = 0; for(int k=i-1;k>=1;k--){// 500 对应后面有 500种可能，就是先5 再 *10 再*10 tmp=tmp*10+v[k]; } res+=tmp; break; } } return res; } int main(){ init(); scanf("%lld%lld",&n,&m); ll res1 = solve(m+1); ll res2 = solve(n); printf("%lld\n",res1-res2); }
不明白……
