题目传送门(BZOJ)
>原文链接<

题解 :

从L到R可以直接转化成前缀求和相减.

状态 :

$F[i][j]$表示$i$位数中结尾为$j$的数字有多少

转移 :

$F[i][j] = \sum F[i-1][k] \;\;\;[abs(k-j)\ge2]$

求答案 :

对于一个数$x$, 我们先按位分解之. 设第$i$位为$X[i]$ ,个位为第一位.

若$x$的位数是$sum$ , 则$\sum\limits_{i=1}^{sum-1}\sum\limits_{j=1}^{9}F[i][j]$可以被累加到答案中

同时, $\sum\limits_{i=1}^{X[sum]-1}F[sum][i]$也要被累加到答案中.

剩下的, 就是对于每一位, 看他能取到多少, 累加到答案中, 有几个特判, 不方便写进式子:

从$sum-1$开始枚举每一位$i$, 再枚举一个$j$从$0$到$X[i]$, 当$abs(j-X[i+1])\ge 2$, $F[i][j]$ 可以被累加到答案中

当$i = 1$时, 对于每个可行的$j$, 我们还要多累加一个1到答案中.

代码 :

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int f[11][10];int l,r;void init() { int i,j,k; for(i=0;i<=9;i++) f[1][i]=1; for(i=2;i<=10;i++) for(j=0;j<=9;j++) for(k=0;k<=9;k++) if(abs(j-k)>=2) f[i][j]+=f[i-1][k];}int work(int x) { if(!x)return 0; int ret = 0; int sum = 0; int que[15]; int i,j; memset(que,0,sizeof que); while(x) { que[++sum]=x%10; x/=10; } for(i=1;i<sum;i++) for(j=1;j<=9;j++) ret+=f[i][j]; for(i=1;i<que[sum];i++) ret+=f[sum][i]; for(i=sum-1;i>=1;i--) { for(j=0;j<que[i];j++) { if(abs(j-que[i+1])>=2) ret+=f[i][j]; } if(abs(que[i+1]-que[i])<2)break; if(i==1)ret++; } return ret;}int main() { init(); scanf("%d%d",&l,&r); printf("%d\n",work(r)-work(l-1));}