关于某 Trick 的一般分析

近几次 Codeforces 比赛中都出现了这个小 Trick，写文以记之。

1560F2. Nearest Beautiful Number

题目大意：

给定 $n,k$，要求找一个最小的 $x$ 使 $x\ge n$ 且 $x$ 至多由 $k$ 种数字组成。数字组成。

（原来的）分析：

拿到题：好啊，大模拟，枚举每一位然后把第一个超过 k 的位置之后全部改成前面出现的最小数字再考虑考虑进位就行了，能写。

然后分了亿些类讨论，if 里面套 if 的那种，WA 了十多次还特判数据点才过。

转头看向官方题解：嗯？？怎么十几行就秒了？？ 细看之后，才发现这个（不知道算不算）巧妙的 trick。

标算分析：

首先，我们的模拟过程基于大段的分类讨论，修改当前位置的时候通常要改变高一位，而这不仅会打乱之前分类讨论的结果更会导致之后分析过程的改变，从而导致恶性循环。
但基础操作不变，我们将 $n$ 拆解为一个位数的序列$N_i$，对这个序列循环分析；

首先制定一个规则：

• 如果 $N_i$ 中数字的种类不超过 $k$，则直接输出。
• 对超过 $k$ 的那一位进行“尝试性”分析— —每次至多 +1。因为可能之前出现的数字都大于该位，通过不断 +1 可以保证转换成之前出现的某数字。
• 若超过 $k$ 的那一位是 9 ，则进行“进位”操作— —将前面第一个非 9 项 +1，并将后面全部赋值为 0 。

之后每次基于该规则进行一次修改后就从头再次循环，直到找到答案。

string solve()
{
	string n; int k;
	cin >> n >> k;
	while (true)
	{
		set<char> s;
		for (auto c : n) s.insert(c);
		if (s.size() <= k) return n;
		
		s.clear();
		int ptr = 0;
		for (; ; ptr++) {
			s.insert(n[ptr]);
			if (s.size() > k) {
				while (n[ptr] == '9') ptr--;
				n[ptr]++;
				for (int i = ptr + 1; i < n.size(); i++) n[i] = '0';
				break;
			}
		}
	}
}

可以注意到，该过程虽然可以保证正确性，但是非常之暴力：每次只修改一位而仅仅加一，并且每次修改完成之后都要再次循环，看似非常的 TLE。

但实际上，这个程序并不会超时：设一个数字至多 m 位，而每一位修改时至多改 9 次，所以时间复杂度不超过 $O(9m)$ 。

这也暗示了一个解题思路： 对于数据范围很小的模拟题，我们没有必要进行复杂的分类讨论，只需制定一个简明而通俗的规则，并按照该规则进行逐步模拟即可。

我们常常会说 “以时间换空间”，我认为这里的空间并非仅指的是运行时的栈空间，同样可以指代码的内存空间。

1567D. Expression Evaluation Error

题目大意：

给定一个十进制数 $N$，将其拆解为 $k$ 个十进制数并以十一进制的方式累加，问如何划分可以使该十一进制和最大？

分析：

拿到题目：？？？

我们已知的是：如果该十一进制和 $S$ 没有改变仍然是 $N$，那显然是最大的，
且$S\leq N$ 是始终成立的。

我们进一步可以得出，只有在发生了十一进制进位的时候，才会造成 $S$ 的损失；
且具体来说，如果第 i 位发生进位，损失的大小为 $11^i$（十进制进位所需代价比十一进制少了一）

于是我们可以制定一下规则：

• 为了避免进位且使每位都能最大利用，我们每次随便选取一个非 10 幂的数 $a$，把它拆解为$10^m$ 与 $a-10^m$ （m为最高位数）
• 如果仅剩下 10 的幂，我们选取最小的那个 $10^x$（非 1），将其拆解为$10^{x-1}$ 与 $9*10^{x-1}$

按照该规则循环拆解的序列，由于每次操作之后各个数均合法，所以 $k$ 次操作可以得到正解。

void solve()  //对于小范围数据可以牺牲时间，对全部序列搜索并精准修改其中一项
{
    int s = read(), n = read(); int S=0, bit_s=0; vector <int> bit;
    bit.push_back( s );
    for (int tot=1;tot<n;tot++) {
        int x = -1;
        for (int i=0;i<bit.size();i++) 
        if ( !is_pw10(bit[i]) ) { x = bit[i], bit.erase(bit.begin()+i); break; }
        if ( x==-1 ) {//都拆完了，只剩10^x
            int mn = inf/2;
            for (int i=0;i<bit.size();i++) if ( is_pw10(bit[i]) && bit[i]!=1 ) mn = min( mn, bit[i] );
            for (int i=0;i<bit.size();i++) 
                if (bit[i] == mn) { x = bit[i], bit.erase(bit.begin()+i); break; }
        }
        bit.push_back( pw10(x) ), bit.push_back( x-pw10(x) );
    }  
    for (int i=0;i<bit.size();i++) printf("%d ",bit[i]);
}