松江品划做企业网站/百度营销官网

题意：给出两个数l，r，要求在这个闭区间【l，r】的所有数中，找出一个要求数，要求数的要求是从这个数中选出所有位中最大的数字和最小的数字，让他们的差值最小，问这个是谁，如果有多个输出其中一个，tips：123【3-1】比121【2-1】大.

思路：

1.这道题可能很容易上来想到数位dp（当然好像确实有这种做法，但我不是），但其实你会发现它用数位dp很难解决（可能是我学艺不精），但是换一个思路，既然要求极差最小，那肯定代表有个答案肯定有个固定的最大最小值，那么如果我暴力枚举一个数字能出现的最大和最小，试图将它构造出来并符合在l，r内，那不就是答案吗？

2.所以枚举一个可能的数字的出现的最大值和最小值，接下来check判断这个数字能不能被构造就可以了。从高位到低位填，如果对当前这一位填上后，后面都填能填的最小数字，结果还比区间的r大，那是不是绝对不可能构造出来，相应的，如果都填最大还没有l大，那一样代表这个数字不可能构造出来。最后返回结果就可以了。

代码：   参考了Codeforces 861 Div2 C. Unlucky Numbers - 知乎

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 998244353;int len,L,R;int check(int r,int l){int now=0;for(int i=0;i<len;i++){int f=-1;for(int j=r;j>=l;j--){int temp=now*10+j;for(int k=i+1;k<len;k++){temp=temp*10+l;}if(temp>R){continue;}temp=now*10+j;for(int k=i+1;k<len;k++){temp=temp*10+r;}if(temp<L){return -1;}f=j;break;}if(f!=-1)now=now*10+f;else return -1;}return now;}void solve(){string x,y;cin >> x >> y;len=x.size();L=stoll(x);R=stoll(y);int ans=20,res=-1;for(int l=9;l>=0;l--){for(int r=0;r<=l;r++){int ned=check(l,r);if(ned!=-1 && l-r<ans){ans=l-r;res=ned;}}}cout << res << endl;}signed main(){IOS;int t=1;cin >> t;while(t--){solve();}
}

跟队友一起看了这道，但是他们居然都认死是数位dp……确实很像数位dp，其实想到了只要枚举就好了，不过没敲代码，刚好学习一下别人优美的代码吧