这题比较考验耐心,首先:主要思路,第一位-1,后面可以全部变成9,这样逆位上来,就是最大的,不过你需要考虑一些特殊情况:1.因为l<=r,所以l是可以等于r,那么当l==r时,逆位上来只能有一个。2.当范围是x到y(除了首位一个后面的数字全是9的数字),那么你可能需要特判了,但其实你只需要把r倒过来的数字与(第一位-1,后面可以全部变成9)比较大小即可。
#include <bits/stdc++.h>//这是错的!!!!!!!!!!!!!!!!!
#define int long long
using namespace std;
string s;a
signed main() {
int t,l,r,c,sum,ans;
cin>>t;
for(int i=0; i<t; i++) {
cin>>l>>r;
c=r;
sum=0;
ans=0;
if(l<r) {
while(r) {
if(r/10==0){
if(r!=1){
ans=ans*10;
ans+=r-1;
}else {
}
}else {
ans=ans*10;
ans+=9;
}
sum=sum*10;
sum+=r%10;
r=r/10;
}
}else {
while(r) {
sum=sum*10;
sum+=r%10;
r=r/10;
}
cout<<sum<<'\n';
continue;
}
if(ans>sum){
cout<<ans<<'\n';
}else cout<<sum<<'\n';
}
return 0;
}
这是我一开始的想法,但实际上,你会遇到很多问题,你可能需要考虑好多的情况,所以,用数字来算,实在是太麻烦了,除非你一个个列出来,不过,你可以多次尝试-1(在大于等于l时)下面是另一个方法,这是一个非常有创造力的思路,按顺序把n位上的数字清理成0,然后-1,运用数学的自然运算,来让后面的数字变成99999....,然后你只需要考虑会不会出现原本数字逆位更大的情况就好了,之前的方法思维太局限于取位999了,而且容易出错,如果是直接-1的话,这样构造是不会出现问题的
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int T;
cin>>T;
while(T--){
int l,r;
cin>>l>>r;
int a=0;
int b=1;//表示当前位数,当b=1时,就是个位数
while(b<=r){
int d=(r/b)%10;//得出当前位是什么数字
if(d){
int c=r-(r%b)-1;//如果当前位不是0,其实就是后面几位都试试看变成9,那么我如果用字符串会不会更好,这是新的思路,因为其实只需要把字符串第一个数字-1,其他变成9,这样太方便了吧,然后在跟另一种情况比较
if(c>=l){
int t=c;
int v=0;
while(t){
v=v*10+t%10;
t=t/10;//计算该种情况的逆位,很简单的代码
}
if(v>a)a=v;
}
}
b*=10;
}
int t=r;
int v=0;
while(t){
v=v*10+t%10;//计算原本的逆位
t=t/10;
}
if(v>a)a=v;//比较大小
cout<<a<<'\n';
}
return 0;
}
那么我如果用字符串会不会更好,这是新的思路,因为其实只需要把字符串第一个数字-1,其他变成9,这样太方便了吧,然后在跟另一种情况比较。 这个时候我看到了官方题解,官方的题解就是关于字符串的
#include <bits/stdc++.h>//来好好的解析一下官方的题解吧,了解是怎样的思想
using namespace std;
void solve() {
string L, R;
cin >> L >> R;
// 如果 R 是 1000... 的形式
string t(1, '1');
for(int i = 0; i < (int)R.size() - 1; i++) {
t += '0';//首先,是想要制造一个和r同位的最小数字,但是不是说是要弄10000...1吗,继续往下看
}
if(R == t) { // R = 1000...
if(L == R) {
cout << 1 << endl;
} else {
long long x = stoll(R);//这是将string类型转换为long long ,学到了
cout << x - 1 << endl; //这是一个特判,如果r==10000...0那么最大的一定是99999..9(少一位)
}
return;
}
// 如果 L 和 R 位数不同,将 L 补到与 R 相同位数
if(L.size() < R.size()) {
L = t;
L.back() += 1; // L = 1000...0001,L.back()是L的最后一位,ascll码,‘0’+1变为1
}
int n = R.size();
string ans;
int k = -1;//特殊值
// 找到第一个不同的位置
for(int i = 0; i < n; i++) {
if(L[i] != R[i]) {
k = i;
break;
}
}
if(k == -1) { // L == R,L==100000....01
ans = L;
// 去掉尾部的0然后反转
while(ans.size() > 1 && ans.back() == '0') {
ans.pop_back();
}
reverse(ans.begin(), ans.end());//这个是逆位
} else {
bool ok = 1; //当l!=r时
// k 位置之后的部分先填9
for(int i = k + 1; i < n; i++) {
ans += '9';
ok &= (R[i] == '9');//这个的意思是如果r[i]是9,那么OK就还是1,到后面就是r[k]-0,而且不需要逆位了,非常聪明的思路
}
// k 位置的处理
ans += (R[k] - !ok);
// k 位置之前的来自 L
for(int i = k - 1; i >= 0; i--) {
ans += L[i];
}
}
cout << ans << endl;
}
int main() {
int T;
cin >> T;
while(T--) {
solve();
}
return 0;
}
总的来说,其实这道题就是构造越早9越好

京公网安备 11010502036488号