526互联

ICPC2022Xian E Find Maximum 题解

发布时间 2023-11-26 21:45:44作者: Martian148

Link

ICPC2022Xian E Find Maximum

Question

定义 \(f(x)\)

image.png

求 image.png

Solution

通过打表我们可以发现 \(f(x)\) 表示三进制表达中有效位数与数码和之和

image.png

接下来考虑如何获得最大的 \(f(x)\)

贪心的去考虑，假设答案为 \(Ans\)，\((Ans)_3\) 肯定是前几位和 \((R)_3\) 的前几位一样，然后某一位是 \((R)_3\) 的某一位 -1 ，然后后面的几位都是 \(2\)

暴力枚举 \((R)_3\) -1 的那一位

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Three{
    int t[51];
    Three(){memset(t,0,sizeof t);}
    Three(LL x) {
        memset(t,0,sizeof t);
        int L=0;
        while(x){
            t[++L]=x%3;
            x/=3;
        }
    }
    LL get_int(){
        LL ret=0;
        for(int i=50;i;i--) ret=ret*3+t[i];
        return ret;
    }
    int get_len(){
        for(int i=50;i;i--) if(t[i]) return i;
        return 0;
    }
    LL get_ans(){
        LL ret=0,L=0;
        for(int i=50;i;i--)if(t[i]){L=i;break;}
        for(int i=L;i;i--) ret+=t[i];
        return ret+L;
    }
};
inline void solve(){
    LL l,r,ans;cin>>l>>r;
    Three L(l),R(r);
    ans=max(L.get_ans(),R.get_ans());
    int R_len=R.get_len();
    Three Z;
    for(int i=R_len;i;i--) Z.t[i]=2;
    for(int i=R_len;i;i--){
        
        if(R.t[i]!=0){
            Z.t[i]=R.t[i]-1;
            if(Z.get_int()>=l){
                LL now=Z.get_ans();
                ans=max(ans,now);
            }
        }
        
        Z.t[i]=R.t[i];
    }
    cout<< ans << endl;
    return ;
}
int main(){
    // freopen("E.in","r",stdin);
    int T;cin>>T;
    while(T--) solve();
}