1 solutions
-
0
难度:黄/绿
算法:数位 dp,打表
打表出奇迹。
令块长 。
我们对于每个 ,暴力打表求得 中有多少满足条件的数。
如果我们要求 中满足条件的数,只需要找到最大的 使得 ,使用事先打好的表算出这部分的结果。其余部分不足 ,直接暴力算。
打表代码:
#include<bits/stdc++.h> using namespace std; int n=2e9,b=1e7,c; inline bool ck(int x){ while(x>=10){ if(int(abs(x%10-(x/10)%10))<=1) return false; x/=10; } return true; } int main(){ freopen("windynumbers.txt","w",stdout); printf("0,"); for(int i=1;i<=n;i++){ if(ck(i)) c++; if(i%b==0){`` printf("%d",c); if(i!=n) putchar(','); } } }
时间复杂度 ,本机运行时间 秒左右。
用于提交的代码:
#include<bits/stdc++.h> using namespace std; int s=1e7,a,b; vector<int> v={0,1459689,2442570,3442552,4440413,5438525,6436637,7434498,8434480,9417361,10538745,10538745,10538745,10538745,11536606,12534718,13532830,14530691,15530673,16513554,17634938,18756322,18756322,18756322,18756322,19754434,20752546,21750407,22750389,23733270,24854654,25976038,26958919,26958919,26958919,26958919,27957031,28954892,29954874,30937755,32059139,33180523,34163404,35163386,35163386,35163386,35163386,36161247,37161229,38144110,39265494,40386878,41369759,42369741,43367602,43367602,43367602,43367602,44367584,45350465,46471849,47593233,48576114,49576096,50573957,51572069,51572069,51572069,51572069,52554950,53676334,54797718,55780599,56780581,57778442,58776554,59774666,59774666,59774666,59774666,60896050,62017434,63000315,64000297,64998158,65996270,66994382,67992243,67992243,67992243,67992243,69113627,70096508,71096490,72094351,73092463,74090575,75088436,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,76088418,77209802,78192683,78192683,78192683,78192683,79190795,80188656,81188638,82171519,83292903,84414287,85397168,86397150,86397150,86397150,86397150,87395011,88394993,89377874,90499258,91620642,92603523,93603505,94601366,94601366,94601366,94601366,95601348,96584229,97705613,98826997,99809878,100809860,101807721,102805833,102805833,102805833,102805833,103788714,104910098,106031482,107014363,108014345,109012206,110010318,111008430,111008430,111008430,111008430,112129814,113251198,114234079,115234061,116231922,117230034,118228146,119226007,119226007,119226007,119226007,120347391,121330272,122330254,123328115,124326227,125324339,126322200,127322182,127322182,127322182}; inline bool ck(int x){ while(x>=10){ if(int(abs(x%10-(x/10)%10))<=1) return false; x/=10; } return true; } int re(int x){ int u=x/s; int res=v[u]; for(int i=u*s+1;i<=x;i++){ if(ck(i)) res++; } return res; } int main(){ scanf("%d%d",&a,&b); printf("%d",re(b)-re(a-1)); }
- 1
Information
- ID
- 167
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 9
- Tags
- # Submissions
- 10
- Accepted
- 7
- Uploaded By