CF Round #739 (Div 3) F, Nearest Beautiful Number

https://codeforces.com/contest/1560/problem/F2

这里主要总结了一下 $d l s$ 讲这道题的思路与时间复杂度证明

这首先是一个询问字典序大于某个串的第一个满足条件的串一类的问题

我们考虑直接剪枝 $D F S$ 。我们首先发现 $n$ 个 $9$ 肯定满足条件。所以我们我们只要枚举与 $n$ 相同的数位即可。我们可以用一个 $v i s [x]$ 记录并且回溯得到当前数字种类数的状态。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

// const int N = 1e2 + 100;
// const int mod = 1e9 + 7;

int n, k, vis[100];
vector<int> d;
bool ok;

void dfs(int pos, int lower, int cnt, int num) {
	if (pos == (int)d.size()) {
		printf("%d\n", num);
		ok = true;
		return ;
	}
	int s = lower ? d[pos] : 0;
	for (int i = s; i <= 9; ++i) {
		int ncnt = cnt + (vis[i] == 0);
		if (ncnt > k) continue;
		vis[i]++;
		dfs(pos + 1, lower && i == d[pos], ncnt, 10 * num + i);
		if (ok) return ;
		vis[i]--;
	}
}

void solve() {
	memset(vis, 0, sizeof vis);
	ok = false;
	d.clear();
	while(n) {
		d.push_back(n % 10);
		n /= 10;
	}
	reverse(d.begin(), d.end());
	dfs(0, 1, 0, 0);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int T; scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &k);
		solve();
	}
}

这里对复杂度做一下证明：

计算复杂度即计算枚举到的每个状态的复杂度，我们对状态分两类进行求解。

①会回溯的状态的复杂度。首先我们考虑什么样的状态会回溯呢？只有如此状态：到达这个状态的路径上的数位一定与 $n$ 的前缀相同，说白了就是通过枚举下界到达的此状态。因为如果到达这个状态的路径上的数位和 $n$ 的前缀不同，那么路径上肯定有比 $n$ 要大的数位，且此时数位种类是符合条件的，那么其是没有上界的，我们只要随便放一个前面已有的数字就可以产生答案。所以我们可以得知，若一个状态的路径上的数位与 $n$ 的前缀相同，那么其才会产生回溯，那么会产生回溯的状态所带来的复杂度显然是 $O (10 ? n 的数位长度)$ （ $10$ 是每个状态都枚举了大约 $10$ 次，因为这样的状态其路径上枚举的数位要和 $n$ 的前缀相同，那么最多就 $10$ 个这样的状态）。

②那么我们考虑不会产生回溯的状态，也就是枚举数字的时候一定有某一个可以搜到答案的情况。那么考虑每个此状态枚举的数字，若枚举的这个数字最后也搜不到答案，那么我们可以将此次枚举的复杂度视为 $O (1)$ ，因为后续状态又变成了①，其复杂度已经被计算过。那如果我们枚举的这个数字其最终可以搜到答案，那么我们发现其下一个状态肯定也是情况 $②$ 。那么我们就可以理解为，我们在最多 $O (10)$ 的复杂度下，②就会到达且总能到达下一个②，那么经过 $n 的数位个数$ 次之后就肯定找到了答案，也就是这种情况所带来的复杂度也是 $O (10 ? n 的数位长度)$ 。