题解 | G-Digital Folding

G. Digital Folding（数字折叠）题解

题目大意

对于正整数 x，定义其折叠操作为：

1.将 x 的十进制表示翻转（例如123→321，120→21）

2.去掉前导零（例如120翻转后是021，去前导零得21）

给定区间 [L,R]，求该区间内所有整数的折叠数的最大值。

1 ≤ L ≤ R ≤ 10^15，T ≤ 10^4

解题思路

1.判断特殊情况：

如果 L = R，直接计算该数的折叠数即可。

2.确定位数范围：

设 n 为 R 的位数。 如果区间跨过了 10^(n-1)，则说明区间包含 n 位数的所有可能，此时答案必定是某个 n 位数的折叠数。

例如 n=3 时，如果 L ≤ 100 ≤ R，则答案一定在 3 位数中。

3.从高位到低位贪心构造：

设当前构造的折叠数为 ans。 从最高位开始（即翻转后的最低位），尝试填入 9~0 的数字。 对于第 i 位（从低位向高位数，即原数字的第 i 位），设当前位尝试填入 j。 我们需要判断：是否存在某个数 x ∈ [L,R]，使得 x 翻转后去掉前导零等于当前构造的数？ 这等价于：判断区间 [L,R] 在模 10^i 意义下，是否包含 ans 或 ans+10^i（因为翻转后位数可能少一位）。

4.边界情况处理：

注意 R 是 10^k 的形式时，位数可能会比看起来少一位。 例如 R=1000，实际上是 4 位数，但翻转后可能变成 1 位数（0001→1）。

代码示列：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll mod=998244353;

int nums[20];

inline ll qpow(ll a, ll b){
    ll res=1;
    while(b){
        if(b&1)res=(res*a);
        a=(a*a);
        b>>=1;
    }
    return res;
}

void solve(){
    ll l,r;cin>>l>>r;
    if(l==r){
        bool f=0;
        while(l){
            if(l%10==0){
                if(f)cout<<l%10;
            }else{
                cout<<l%10;
                f=1;
            }
            l/=10;
        }
        cout<<"\n";
        return;
    }
    ll n=0;
    ll x=r;
    while(x){
        n++;
        x/=10;
    }
    l=max(l,qpow(10,n-1));
    ll ans=0;
    for(int i=1;i<=16;i++)if(r==nums[i])n--;
    for(ll i=1;i<=n;i++){
        if((r-l+1)/qpow(10,i)){
            ans+=9*qpow(10,i-1);
        }else{
            for(ll j=9;j>=0;j--){
                ll x=l%qpow(10,i),y=r%qpow(10,i);
                ll val=ans+qpow(10,i-1)*j;
                if(y>x){
                    if(val>=x&&val<=y){
                        ans=val;
                        break;
                    }
                }else{
                    y+=qpow(10,i);
                    if((val+qpow(10,i)>=x&&val+qpow(10,i)<=y)||(val<=y&&val>=x)){
                        ans=val;
                        break;
                    }
                }
            }
        }
    }
    bool f=0;
    while(ans){
        if(ans%10==0){
            if(f)cout<<ans%10;
        }else{
            cout<<ans%10;
            f=1;
        }
        ans/=10;
    }
    cout<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    nums[0]=1;
    for(int i=1;i<=16;i++)nums[i]=nums[i-1]*10;
    int t;cin>>t;
    while(t--)solve();
    return 0;
}