题目

链接：https://ac.nowcoder.com/acm/contest/120561/G 来源：牛客网

小苯发现了一种特殊的数字运算，称为"数字折叠"。对于一个正整数 x，定义其 "折叠数" 为：将 x 的十进制数位翻转并去除前导 0， x 的值更改为翻转后得到的新数。 例如， 123 操作后会变为 321，而 120 会变为 21。 现在小苯拿到了一个区间 [l,r]，他想知道如果将区间中所有的整数 i(l≦i≦r) 的折叠数都求出，那么其中的最大值是多少。你的任务就是求出这个最大值

输入描述:

每个测试文件包含多组测试数据。第一行输入一个整数 T(1≦T≦10^ 4 ) 代表数据组数，每组测试数据描述如下： 在一行上输入两个整数 l,r(1≦l≦r≦10 ^ 15 )，表示询问的区间。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示区间中所有数的 "折叠数" 的最大值。

解题思路

个人做法是分类讨论，首先特判对于右边界为10的n次方的情况，对此又分为左边界与右边界相同和左边界与右边界不同两种，分别判断即可，下面继续判断右边界为1*10的n次方+10以内的情况，由于这类情况如果想要个位为9以达到翻转后更大的结果，会导致除个位以外其他所有位皆为0，翻转后得不偿失，故特判此类情况，直接将右边界翻转即可。由上面特判我们不难想到还有左边界等于右边界的情况以及一开始就不需要翻转的全9情况，也加上特判，最后剩下左边界数的长度比右边界数短的情况以及两者一样长两种常规方式，对于左边界比右边界短，那么右边界就没有什么限制，只需要避免前导零的情况即可，如果两边界长度相同，那么则需要找到两者第一个不同的位置，减1后，后面的数全取9即可，因为左边界与右边界在此位置不同，所以r在此位置上至少为1，无需担心为负数，最后翻转右边界r，再转为long long输出。

void solve()
{
	string l,r,str;
	ll num=0;
	cin>>l>>r;
	str+='1';
	for(ll i=1;i<(ll)r.size();i++) 
		str+='0';
	if(r==str)
	{
		if(l==r)cout<<1<<endl;
		else 
			cout<<stoll(str)-1<<endl;
		return;
	}
	if(stoll(r)<stoll(str)+10)
	{
		reverse(r.begin(),r.end());
		cout<<stoll(r)<<endl;
		return;
	}
	str+='0';
	if(l==r||(stoll(r)==(stoll(str)-1)))
	{
		reverse(r.begin(),r.end());
		cout<<stoll(r)<<endl;
		return;
	}
	ll i,j;
	if(l.size()!=r.size())
	{
		if(r[0]=='1')
		{
			for(i=1;i<(ll)r.size();i++)
				if(r[i]!='0')break;
		}
		else 
			i=0;
	}
	else
		for(i=0;i<(ll)r.size();i++)
			if(r[i]!=l[i])break;
	for(j=i+1;j<(ll)r.size();j++)
		if(r[j]!='9')break;
	if(j!=(ll)r.size())
	{
		r[i]-=1;
		for(i+=1;i<(ll)r.size();i++)
			r[i]='9';
	}
	reverse(r.begin(),r.end());
	num=stoll(r);
	cout<<num<<endl;
}

如有错误，烦请指正谢谢。