线性基思想+贪心——cf1249C

/*
1+3+9+...+3^n<3^(n+1),按这个思路贪心一下就好
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll p[100],flag[40],s[100];

int main(){
    p[0]=s[0]=1;
    for(int i=1;i<=39;i++)
        p[i]=p[i-1]*3,s[i]=s[i-1]+p[i];
    
    int Q;cin>>Q;
    while(Q--){
        ll n;cin>>n;
        ll tmp=n,sum=0;
        
        int flag[40]={},Max=0;
        for(int i=38;i>=0;i--)
            if(tmp>=p[i]){    
                Max=max(Max,i);
                tmp-=p[i],sum+=p[i];
                flag[i]=1;
            }
            
        if(tmp==0){
            cout<<n<<'
';
        }else if(n>s[Max]){
            cout<<p[Max+1]<<'
';
        }else {
            ll ans=0,id;
            for(int i=0;i<=38;i++)
                if(flag[i]==0){
                    id=i;break;
                }
            ans+=p[id];
            for(int i=id+1;i<=38;i++)
                if(flag[i])ans+=p[i];
            cout<<ans<<'
';
        }
        
    }
    
}