LG3107 [USACO14OPEN] Odometer S 题解 (数位DP+容斥)

题意

定义一个数是神奇的当且仅当这个数中有一个数位出现了一半及以上，比如 112，2233。求 \([l,r]\) 中有多少个好的数字，\(100\le l,r\le 10^{18}\)。

题解

考虑数位 DP，先把答案转为 \(Ans(r)-Ans(l-1)\)，我们钦定一个数 \(k\) 让他必须出现多于一半，然后我们想求 \([1,x]\) 中有多少个数满足 \(k\) 出现多于一半，所以我们想到记 \(f(x,k,t,top)\) 表示考虑我们填到了第 \(x\) 位，\(k\) 这个数出现了 \(t\) 次，当前是否达到最大值（详见数位 DP）。每次转移我们枚举第 \(x\) 位该填哪个数字，转移即可。

但是发现这样子会算重，也就是会出现 1122 这种数字，我们在 \(k=1,k=2\) 的时候都会把这个数算到里面。于是我们考虑再写一个数位 DP 处理这个问题。设 \(g(x,k1,k2,t1,t2,top)\) 表示考虑我们填到第 \(x\) 位，要求这个数里要么是 \(k1\) 要么是 \(k2\)，其中 \(k1\) 出现 \(t1\) 次，\(k2\) 出现 \(t2\) 次，每次转移考虑第 \(x\) 位是填 \(k1\) 还是 \(k2\) 即可。

为避免前导零，我们可以考虑在 \(f,g\) 外边枚举第一个数。

int f[21][21][2], d[21], tot;

int dfs1(int x, int k, int t, bool top, int vd) {
	if (x > tot) return t >= (vd + 1) / 2;
	assert(x <= 20);
	if (~f[x][t][top]) return f[x][t][top];
	int ret = 0, mx = top ? d[x] : 9;
	for (int i = 0; i <= mx; ++i) {
		ret += dfs1(x + 1, k, (i == k) + t, top && i == mx, vd);
	}
	return f[x][t][top] = ret;
}

int g[21][21][21][2];

int dfs2(int x, int k1, int k2, int t1, int t2, bool top) {
	if (x > tot) return t1 == t2;
	assert(x <= 20);
	if (~g[x][t1][t2][top]) return g[x][t1][t2][top];
	int ans = 0;
	if (!top) {
		ans += dfs2(x + 1, k1, k2, t1 + 1, t2, false);
		ans += dfs2(x + 1, k1, k2, t1, t2 + 1, false);
		return g[x][t1][t2][top] = ans;
	} else {
		if (d[x] < k1) return g[x][t1][t2][top] = 0;
		if (k1 <= d[x] && d[x] < k2) {
			return g[x][t1][t2][top] = dfs2(x + 1, k1, k2, t1 + 1, t2, k1 == d[x]);
		}
		if (k2 <= d[x]) {
			ans += dfs2(x + 1, k1, k2, t1 + 1, t2, k1 == d[x]);
			ans += dfs2(x + 1, k1, k2, t1, t2 + 1, k2 == d[x]);
			return g[x][t1][t2][top] = ans;
		}
		assert(false); // wtf???
	}
}

int calc(int x) {
	if (x == 1e18) return calc(x - 1) + 1;
	int t = x;
	tot = 0;
	while (t) {
		d[++tot] = t % 10;
		t /= 10;
	}
	reverse(d + 1, d + 1 + tot);
	int ans = 0;
	for (int i = 1; i <= tot; ++i) {
		for (int k = 0; k <= 9; ++k) {
			for (int j = 1; j <= 9; ++j) {
				if (i == 1 && j > d[1]) break;
				memset(f, -1, sizeof f);
				int tmp = dfs1(i + 1, k, j == k, i == 1 && j == d[1], tot - i + 1);
				ans += tmp;
			}
		}
	}
	for (int i = 1; i <= tot; ++i) {
		if ((tot - i + 1) % 2) continue;
		for (int k1 = 0; k1 <= 9; ++k1) {
			for (int k2 = k1 + 1; k2 <= 9; ++k2) {
				if (i != 1) {
					memset(g, -1, sizeof g);
					if (k1) ans -= dfs2(i + 1, k1, k2, 1, 0, false);
					memset(g, -1, sizeof g);
					if (k2) ans -= dfs2(i + 1, k1, k2, 0, 1, false);
					continue;
				}
				if (d[1] < k1) break;
				if (k1 <= d[1] && d[1] < k2) {
					memset(g, -1, sizeof g);
					if (k1) ans -= dfs2(i + 1, k1, k2, 1, 0, d[1] == k1);
				}
				if (k2 <= d[1]) {
					memset(g, -1, sizeof g);
					if (k1) ans -= dfs2(i + 1, k1, k2, 1, 0, d[1] == k1);
					memset(g, -1, sizeof g);
					if (k2) ans -= dfs2(i + 1, k1, k2, 0, 1, d[1] == k2);
				}
			}
		}
	}
	return ans;
}

void work() {
	int l, r; cin >> l >> r;
	cout << calc(r) - calc(l - 1) << endl;
}