暴力——分块打表

· · 题解

虽然本题是数位dp的模板
但是我还是想用另一些玄学的方法瞎搞——
分块打表！

对于每sqrt(n)左右的区间统计值
但是如果每sqrt(n)打一个数字，表的长度会超标
这时想到可以只统计两个区间的差，在提交时跑一遍前缀和计算
可以显著降低表的大小

但是打表实在太花空间了
我考虑改成间隔1e5，可还是不行
但是我们的暴力程序是线性的，所以即使是间隔1e6的表也是可以接受的
在代码长度的边缘左右横跳，我发现间隔2e5的表可以接受
那么就没什么好说的了
注意一下边界细节

打表程序：（20s左右）

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("biao.txt","w",stdout);
    int cnt=0,pre=0;
    for(int i=1;i<=2000000000;++i){
        int k=i,last=20,is=1;
        while(k){
            if(abs(last-(k%10))<2){
                is=0;break;
            }
            last=k%10;
            k/=10;
        }
        cnt+=is;
        if(i%200000==0){
            printf("%d,",cnt-pre);
            pre=cnt;
        }
    }
    return 0;
}

提交程序

#include<bits/stdc++.h>
using namespace std;
int biao[]={………………};
int query(int num){
    int ans=0,k=num/200000;
    for(int i=1;i<=k;++i)
        ans+=biao[i];
    for(int i=k*200000+1;i<=num;++i){
        int k=i,last=20,is=1;
        while(k){
            if(abs(last-(k%10))<2){
                is=0;break;
            }
            last=k%10;
            k/=10;
        }
        ans+=is;
    }
    return ans;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%d",query(m)-query(n-1));
    return 0;
}