题目描述
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
输入输出格式
输入格式：包含两个整数，A B。
输出格式：一个整数
输入输出样例
输入样例#1：
1 10
输出样例#1：
9
输入样例#2：
25 50
输出样例#2：
20
说明
100%的数据，满足 1 <= A <= B <= 2000000000 。
Solution：
本题显然数位$DP$，暂时不会（留着填坑～）。
提供打表的思路，先线下每$10^6$个处理一次，统计出$2000$个答案（前缀和$sum[i]$表示$1$到$i*10^6$中满足条件的个数）。
那么查询时就直接瞎搞模拟，最多计算$10^6$次。
打表代码：
/************************************************************** Problem: 1026 User: five20 Language: C++ Result: Accepted Time:256 ms Memory:1296 kb ****************************************************************/ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespace std; const int N=1e6+5; int ans,a,b,sum[2005]={0, 202174, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; inline void check(int x){ if(x<=9){ans++;return;} int a=x,b=-5; while(a){ if(abs(a%10-b)<2)return; b=a%10;a=a/10; } ans++; } int main(){ cin>>a>>b; if(b-a<=1000000){ For(i,a,b)check(i); cout<<ans; return 0; } int p=ceil(a*1.0/1000000),q=floor(b*1.0/1000000); For(i,1,2000)sum[i]+=sum[i-1]; ans+=sum[q]-sum[p]; if(!ans)ans++; p=p*1000000,q=q*1000000; if(a!=p) For(i,a,p-1)check(i); if(b!=q) For(i,q+1,b)check(i); cout<<ans; return 0;
过来填坑啦～：2018-05-26
本题套上一个数位$dp$的板子。定义状态$f[i][j]$表示第$i$位为数字$j$时的合法个数。
由于本题的约数条件是相邻两位数字之差不小于$2$（且所有个位数均视为满足条件），直接套板子肯定有问题，比如$[45,4500]$，枚举时当前几位连续为$0$时必须往后判断，否则会出兮兮，那么就必须去处理前导$0$的问题。
于是在普通的约束上界$limit1$的条件下（即每次枚举数字时是否受限），再加一个$limit2$来判断前导$0$的情况。
那么每次枚举当前位数字时，判断一下上一位是否受$limit2$的限制且当前位为$0$，是的话就说明这时存在前导$0$，往后搜索时将$lst$赋值为$-2$（这样$0-(-2)geq 2$）。
然后所有的不受限制的情况都记忆化一下，最后前缀和思想相减就是答案了。
$DP$代码：
#include<bits/stdc++.h> #define il inline #define ll long long #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespace std; ll a,b,f[20][10],cnt,p[20]; il ll dfs(int pos,int lst,bool limit1,bool limit2){ if(!pos)return 1; if(!limit2&&!limit1&&f[pos][lst]!=-1)return f[pos][lst]; int op,up=limit1?p[pos]:9; ll tmp=0; For(i,0,up){ if(abs(i-lst)<2)continue; op=i; if(limit2&&!i)op=-2; tmp+=dfs(pos-1,op,(limit1)&&(i==up),(op==-2)); } if(!limit1&&!limit2)f[pos][lst]=tmp; return tmp; } il ll solve(ll x){ cnt=0; while(x)p[++cnt]=x%10,x/=10; return dfs(cnt,-2,1,1); } int main(){ cin>>a>>b; memset(f,-1,sizeof(f)); printf("%lld ",solve(b)-solve(a-1)); return 0; }