题意：区间[a, b]里有多少个不含前导0的十进制整数任意相邻两位之差的绝对值不小于2？（1<=a<=b<=2,000,000,000，a, b是整数）
前几天做XJOI模拟赛中有关字典序的一道题，发现可以按照某种顺序从高位向低位统计。十进制数之间的比较，把前导0补齐，实际上就是字符串的比较。
举例，如果允许前导0，小于34023的自然数可以这样生成（下划线表示0~9间任意数码）：
0 _ _ _ _
1 _ _ _ _
2 _ _ _ _
3 0 _ _ _
3 1 _ _ _
3 2 _ _ _
3 3 _ _ _
3 4 0 0 _
3 4 0 1 _
3 4 0 2 0
3 4 0 2 1
3 4 0 2 2
有了这个背景，回到本题。显然，我们可以统计[1, b+1)和[1, a)内的结果，再作差。预处理，设f[i][j]为长度为(i+1)位十进制串（允许前导0）中有多少个符合“任意相邻两位之差的绝对值不小于2”。统计[1, x)内的结果时，先统计位数小于x的，再统计最高位小于x的，然后按照上面所述顺序，统计高k位与x相同的，如果x的高k位已不符合Windy数的定义，须及时退出。
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAX_N = 10;
int f[MAX_N][10], g[MAX_N];int cal(char* s, int n)
{int ans = n > 1 ? g[n-2] : 0;for (int i = 1; i < s[0]-'0'; ++i) // 最高位ans += f[n-1][i];for (int i = 1; i < n; ++i) { // s[0..i)相同int c2 = s[i-1] - '0', c1 = s[i] - '0';for (int j = 0; j < c1; ++j)if (abs(j-c2) >= 2)ans += f[n-i-1][j];if (abs(c2-c1) < 2)break;}return ans;
}int main()
{char sa[11], sb[11];int a, b;scanf("%d %d", &a, &b);++b;int la = sprintf(sa, "%d", a), lb = sprintf(sb, "%d", b);for (int i = 0; i < 10; ++i)f[0][i] = 1;for (int i = 1; i < lb; ++i)for (int j = 0; j < 10; ++j)for (int k = 0; k < 10; ++k)if (abs(k-j) >= 2)f[i][j] += f[i-1][k];g[0] = 9;for (int i = 1; i < lb; ++i) {g[i] = g[i-1];for (int j = 1; j < 10; ++j)g[i] += f[i][j];}printf("%d\n", cal(sb, lb) - cal(sa, la));return 0;
}