1 solutions

  • 0
    @ 2024-3-9 12:18:43

    难度:黄/绿

    算法:数位 dp,打表

    打表出奇迹。

    令块长 b=107b=10^7

    我们对于每个 ii,暴力打表求得 [1,i×b][1,i\times b] 中有多少满足条件的数。

    如果我们要求 [1,r][1,r] 中满足条件的数,只需要找到最大的 ii 使得 i×bri\times b\le r,使用事先打好的表算出这部分的结果。其余部分不足 bb,直接暴力算。

    打表代码:

    #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(',');
    		}
    	}
    }
    

    时间复杂度 O(nlog10n)O(n\log_{10}n),本机运行时间 4747 秒左右。

    用于提交的代码:

    #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