这是2026牛客寒假算法基础集训营1 的G题

题目链接：https://ac.nowcoder.com/acm/contest/120561/G

题目大意：给定一个区间，从这个区间中找到一个数，使其翻转过来数最大。

题目分析：首先，要让一个数翻转之后变得很大，就要让原本这个数的最后几位越大越好，当然是9的时候是最好的。这时候将给定的右区间做一个分类，第一种是十的幂次方，剩下的就是第二种。

首先，先看第一种的处理方法： 先计算右区间的字符长度，再算出10^(长度-1)与右区间是否相等： 这时候如果相等就要分出两种情况，第一种就是l==r，这时候因为都是十的幂次方，所以直接输出1，然后return结束。

string g(1,'1');
	for(int i=0;i<len-1;i++){
		g+='0';
	}
	if(g==b){
		if(a==b){
			cout<<1<<"\n";
          return；
		}

第二种就是不相等，那么直接输出全是9就行，即r-1；

else{
			ll res=stoll(b);
			cout<<res-1<<"\n";
			return；
		}

然后看如果右区间不是十的幂次方的情况：

这时候依然分成两种情况，就是l==r和l！=r的情况：

同时这里补充一点，如果l位数没有r大的时候，直接将l变成与r位数一致的十的幂次方+1就行：

if(a.length()<len){
		a=g;
		a.back()+=1;
	}

这时候先看l==r的情况，直接去除前导零输出就行：

		string ans;
		ans=a;
		while(ans.length()>1&&ans.back()=='0'){
			ans.pop_back();
		}
		reverse(ans.begin(),ans.end());
		cout<<ans<<"\n";
		return;

或者：

ll res=stoll(a);
		while(res%10==0){
			res/=10;
		}
		ans=to_string(res);
		reverse(ans.begin(),ans.end());
		cout<<ans<<"\n";
		return;

然后看l！=r的情况： 这时候要判断l与r是从第几位开始不一样的，所以设定一个变量p；

int p=-1;
	for(int i=0;i<len;i++){
		if(a[i]!=b[i]){
			p=i;
			break;
		}
	}

找到之后从r的第p+1位开始往后便利，同时将ans加上r.length()-p-1个9，因为未翻转之前的数的后几位的9是非常好凑的，所以加上这么多个9之后，再看r的p+1位后的数是不是9，如果不是9就设定一个变量e，如果都是9就为1，不是就为0：

int e=1;
		for(int i=p+1;i<len;i++){
			ans+='9';
			if(b[i]!='9'){
				e=0;
			}
		}

这时候开始加最后几位数了，如果不是全9的话就将第p位减去1，这样翻转之后就可以变成全9，这样数就可以更大，如果是全9就直接加上第p位就行，最后再加上前面相同的几位即可：

if(e==0){
			ans+=b[p]-1;
		}
		else{
			ans+=b[p];
		}
		for(int i=p-1;i>=0;i--){
			ans+=a[i];
		}

下面附上完整代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;

void solve(){
	string a,b;
	cin>>a>>b;
	ll len=b.length();
	string g(1,'1');
	for(int i=0;i<len-1;i++){
		g+='0';
	}
	if(g==b){
		if(a==b){
			cout<<1<<"\n";
		}
		else{
			ll res=stoll(b);
			cout<<res-1<<"\n";
		}
		return;
	}
	
	if(a.length()<len){
		a=g;
		a.back()+=1;
	}
	string ans;
	int p=-1;
	for(int i=0;i<len;i++){
		if(a[i]!=b[i]){
			p=i;
			break;
		}
	}
	if(p==-1){
		ll res=stoll(a);
		while(res%10==0){
			res/=10;
		}
		ans=to_string(res);
		reverse(ans.begin(),ans.end());
		cout<<ans<<"\n";
		return;
	}
	else{
		int e=1;
		for(int i=p+1;i<len;i++){
			ans+='9';
			if(b[i]!='9'){
				e=0;
			}
		}
		if(e==0){
			ans+=b[p]-1;
		}
		else{
			ans+=b[p];
		}
		for(int i=p-1;i>=0;i--){
			ans+=a[i];
		}
		cout<<ans<<"\n";
		return;
	}
	
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	}
}
//20 203
//15 89
//1 1