自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:23:39，当前版本为作者最后更新于2021-08-04 18:19:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我只会发屑题的题解实锤了

思路

一道非常基础的数位 dp，不知道为什么是紫题。

首先要知道一个非常重要的性质：如果一个字符串不含有长度大于 $1$ 的回文子串，那么这个字符串的每个字符都不会和前两个字符相同。

于是记搜时我们添加两个状态 $\text{pre1}$ 和 $\text{pre2}$，表示当前数位的前两个数字，往下搜的时候判断一下当前数位是否不等于 $\text{pre1}$ 和 $\text{pre2}$。初始时设 $\text{pre1}$ 和 $\text{pre2}$ 为 $-1$，表示没有前两位。注意判断状态是否访问过时 $\text{pre1}$ 和 $\text{pre2}$ 要 $+1$，否则 $-1$ 可能会越界。还有一点要注意：$\text{pre1}$ 转移时，如果当前数位为前导零，则要设为 $-1$ 而不是 $0$，否则会 WA 78pts。

之后就是套模板了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll l, r, f[25][15][15], a[25];

ll dfs(ll pos, bool limit, bool lead, ll pre1, ll pre2) {
	if (!pos) {
		return 1;
	}
	ll ans = 0;
	if (!limit && !lead && f[pos][pre1 + 1][pre2 + 1] != -1) {
		return f[pos][pre1 + 1][pre2 + 1];
	}
	ll up = limit ? a[pos] : 9;
	for (ll i = 0; i <= up; ++i) {
		if (i != pre1 && i != pre2) {
			ans += dfs(pos - 1, limit && i == up, lead && !i, (!lead || i) ? i : -1, pre1);
		}
	}
	if (!limit && !lead) {
		f[pos][pre1 + 1][pre2 + 1] = ans;
	}
	return ans;
}

ll solve(ll x) {
	ll cnt = 0;
	while (x) {
		a[++cnt] = x % 10;
		x /= 10;
	}
	memset(f, -1, sizeof(f));
	return dfs(cnt, 1, 1, -1, -1);
}

int main() {
	scanf("%lld%lld", &l, &r);
	printf("%lld", solve(r) - solve(l - 1));
	return 0;
}