题解：CF2121E Sponsor of Your Problems

· · 题解

题意

对于正整数 a 和 b，定义 f(a,b) 表示 a 和 b 在十进制表示下数字相同的有几位。题目保证调用时 a 和 b 的总位数相等。给出 T 组询问，每次给定 l 和 r，求 f(l,x)+f(x,r) 的最小值，其中 l\le x \le r，保证 l 和 r 的总位数相等。

做法

从高位往低位考虑，假设当前在第 i 高的位，且更高的位上 l 和 r 相等。分以下三种情况：

  1. 这一位上 l 和 r 仍然相等。此时 x 在这一位上只有一种选择，答案加二。

  2. 这一位上 l 和 r 不相等，且差值至少为 2。此时 x 可以在这一位上选择一个在中间的数，更低位可以随便选，所以不会再有答案了，结束。

  3. 这一位上 l 和 r 不相等，且差值为 1。x 可以选择取两个值中的一个。如果选择较小者，则在 l 出现非 9 的数字之前，都会有贡献。同理，选择较大者会在 r 出现非 0 的数字之前有贡献。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
    string l,r;
    cin>>l>>r;
    int res=0;
    for(int i=0;i<l.length();i++){
        if(l[i]==r[i])res+=2;
        else if(l[i]+1==r[i]){
            int tmp=0x3f3f3f3f;
            int pos=i+1;
            while(pos<l.length()&&l[pos]=='9')pos++;
            tmp=min(tmp,pos-i);
            pos=i+1;
            while(pos<r.length()&&r[pos]=='0')pos++;
            tmp=min(tmp,pos-i);
            res+=tmp;
            break;
        }
        else{
            break;
        }
    }
    cout<<res<<"\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin>>tt;
    while(tt--)solve();
    return 0;
}