CF1808C Unlucky Numbers 题解

可以证明答案是 \(l\) 或 \(r\) 的一段前缀，拼上后面全部相同的一段字符 \(d\)，证明方式类似数位 dp。能够自由填的数字一定是相等的，这样不会影响幸运值。前面那些不能自由填写的，就是 \(l\) 或 \(r\) 的一段前缀。假如不是 \(l\) 或 \(r\) 的一段前缀，必然填写相等的更好，而这种情况已经被考虑到了。
枚举前缀长度，枚举修改成的字符 \(d\)，复杂度 \(\mathcal O(T\log^2w\Sigma)\)，字符集大小为 \(10\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
using std::cin;using std::cout;
using std::max;using std::min;
using loli=long long;
int n;
loli l,r;
std::vector<int>b1,b2,t,ans;
int calc(std::vector<int>b){
	reverse(all(b));
	while(!b.empty()&&!b.back())b.pop_back();
	return *max_element(all(b))-*min_element(all(b));
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);cin.tie(nullptr);
	int T;cin>>T;while(T--){
		cin>>l>>r;
		b1.clear();b2.clear();
		ans.clear();
		for(;l;l/=10)b1.push_back(int(l%10));
		for(;r;r/=10)b2.push_back(int(r%10));
		n=max(siz(b1),siz(b2));
		while(siz(b1)<n)b1.push_back(0);
		while(siz(b2)<n)b2.push_back(0);
		reverse(all(b1));reverse(all(b2));
		for(int k=0;k<=n;k++)for(int d=0;d<=9;d++){
			t=b1;
			for(int j=k;j<n;j++)t[j]=d;
			if(b1<=t&&t<=b2&&(ans.empty()||calc(t)<calc(ans)))
				ans=move(t);
		}
		for(int k=0;k<=n;k++)for(int d=0;d<=9;d++){
			t=b2;
			for(int j=k;j<n;j++)t[j]=d;
			if(b1<=t&&t<=b2&&(ans.empty()||calc(t)<calc(ans)))
				ans=move(t);
		}
		reverse(all(ans));
		while(!ans.empty()&&!ans.back())ans.pop_back();
		reverse(all(ans));
		for(int i:ans)cout<<i;
		cout<<'\n';
	}
	return 0;
}