hihoCoder #1770 : 单调数（数位dp）

时间：2022-12-03 15:38:53

题面

我们定义一个数是单调数，当且仅当构成这个数每一个数位都是单调不降或不增的。

例如 \(123\) 和 \(321\) 和 \(221\) 和 \(111\) 是单调的，而 \(312\) 不是单调的。

给定 \(T\) 组 \(l, r\)，每次询问 \([l, r]\) 中有几个单调的数。

\(l, r \le 10 ^ {18}, T \le 10^4\)

题解

今天 hihoCoder 竟然 \(AK\) 了，真舒服（虽然题目很水，还被罚时坑惨了）qwq

显然考虑一个数位 \(dp\) ，不难发现我们只需要记下当前在哪一位，以及最后一位是什么数字就行了。

然后对于不降和不增做个两遍就行了，但有很多细节后面细讲。

写的时候发现自己摸索了一套数位 \(dp\) 的套路？（逃

套路：

我们常常是要求 \(\le n\) 的有多少个满足要求的数。

这个限制有些恶心，我们需要多一位来看是否被限制。

我们一般按位考虑，令 \(dp[i][0 / 1]\) 为到从高到低考虑到第 \(i\) 位，当前有/没被 \(n\) 限制。

我们考虑把 \(n\) 按位拆下来，变成一个数组 lim[i] ，然后取出 \(n\) 的位数 Bit 。

每次考虑后一位放什么数字就行了。具体实现如下（用刷表法方便转移）：

dp[0][0] = 1;

for (int i = 0; i < Bit; ++ i)

    for (int now = 0; now <= 1; ++ now)

		for (int dig = 0; dig <= 9; ++ dig) if (now || (dig <= lim[i + 1]))

    		dp[i + 1][now || (dig < lim[i + 1])] += dp[i][now];

然后最后的答案就是

ans = dp[Bit][0] + dp[Bit][1];

不难发现这样写，每个位数的数都会被考虑到。因为我们枚举的时候允许了前缀 \(0\) 的存在。

并且如果存在前缀 \(0\) 那么后面的所有数都不会存在限制了，可以随便填。

但是注意这样的话，全部为 \(0\) 的也会考虑进去，我们平常要考虑是否 \(-1\) 就行了。

对于这道题我们可以类比这种方法去做。

首先把答案差分表示 \(ans = ans_r - ans_{l - 1}\) 。

然后令 dp[i][j][0/1] 为到第 \(i\) 位，最后一次填 \(j\) ，有/没 被 \(n\) 限制住的情况。

直接这样写的话，递增是没有问题的，递减的时候就会存在问题了。

因为我们把前导 \(0\) 考虑进去了，结果导致没有正确算上这部分贡献。

所以我们还要多一维，也就是 dp[i][j][0/1][0/1] 前三个同上，最后一个意义是当前完全不/是前缀 \(0\) 。

然后转移的时候也是枚举数字，然后按照两种情况考虑下填的这个数的限制就行了。

注意有一些数会被递增递减算两次，也就是 \(111\) ，\(3333\) ，这些完全相同的数。可以直接暴力枚举减去就行了。

复杂度是 \(O(T * 18 * 10)\) 的。

总结

碰到数位 \(dp\) 直接上套路去讨论。

然后就需要对于具体问题具体分析了，根据题目要求设出需要的状态。

有时候可以根据需要卡卡状态数，因为通常不可能到满。

一定要写个暴力拍，这个东西其实很好调？

代码

建议看看代码，其实写的很简洁？（可读性也是很鲁棒的qwq）

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << x << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x = 0, fh = 1; char ch = getchar();

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;

    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);

    return x * fh;

}

void File() {

#ifdef zjp_shadow

	freopen ("1770.in", "r", stdin);

	freopen ("1770.out", "w", stdout);

#endif

}

typedef long long ll;

ll dp[19][10][2][2];

int lim[19];

inline int Get_Bit(ll x) {

	int tot = 0;

	for (; x; x /= 10) lim[++ tot] = x % 10;

	reverse(lim + 1, lim + tot + 1);

	return tot;

}

inline ll Calc(ll n) {

	if (!n) return 0;

	ll ans = 0;

	For (opt, 0, 1) {

		Set(dp, 0); dp[0][0][0][1] = 1;

		int Bit = Get_Bit(n);

		For (i, 0, Bit - 1) For (j, 0, 9) For(now, 0, 1) For (fir, 0, 1) {

			For (dig, opt ? 0 : j, opt ? (fir ? 9 : j) : 9) if (now || dig <= lim[i + 1])

				dp[i + 1][dig][now || (dig < lim[i + 1])][fir && !dig] += dp[i][j][now][fir];

		}

		For (j, 0, 9) For(now, 0, 1) For (fir, 0, 1) ans += dp[Bit][j][now][fir];

		-- ans;

	}

	For (dig, 1, 9) {

		ll tmp = dig;

		while (tmp <= n) -- ans, tmp = tmp * 10 + dig;

	}

	return ans;

}

int main() {

	File();

	for (int cases = read(); cases; -- cases) {

		ll l, r; cin >> l >> r;

		printf ("%lld\n", Calc(r) - Calc(l - 1));

	}

	return 0;

}

相关文章