BZOJ原题链接

洛谷原题链接

简单的数位\(DP\)，套模板就好。

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 15;

int f[N][N], a[N];

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline int jd(int x){ return x < 0 ? -x : x; }

int dfs(int pos, int pre, int lm, int zero)

{

	if (pos < 0)

		return 1;

	if (pre > 0 && !lm && !zero && f[pos][pre] > -1)

		return f[pos][pre];

	int i, k = lm ? a[pos] : 9, su = 0;

	for (i = 0; i <= k; i++)

		if (jd(i - pre) > 1)

			su += dfs(pos - 1, zero && !i ? -2 : i, lm && i == a[pos], zero && !i);

	if (pre > 0 && !lm && !zero)

		return f[pos][pre] = su;

	return su;

}

int calc(int x)

{

	int l = 0;

	while (x > 0)

	{

		a[l++] = x % 10;

		x /= 10;

	}

	return dfs(l - 1, -2, 1, 1);

}

int main()

{

	int x, y;

	x = re();

	y = re();

	memset(f, -1, sizeof(f));

	printf("%d", calc(y) - calc(x - 1));

	return 0;

}