题目传送门(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, 再枚举一个j0X[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));}