Codeforces--C2. Good Numbers (hard version)

题目链接http://codeforces.com/contest/1249/problem/C2。这是道进制转换题，我们的目的是找到最小的一个每个位都是1的三进制数来表示一个十进制数n。做法是，先将n转换为一个三进制数，然后对当前位加上低位的进位大于等于2的位置0并进位，这一步需要注意的是，当前位如果产生进位，需要把该位的低位都给置0，这样才能保证重构后的数最小。

此外，需要注意的是，在利用重构数组计算10进制数的时候，不能用pow函数，因为，pow对3的38次幂是无法计算的，会发生溢出，需要自己写一个。

 #include<bits/stdc++.h>

 using namespace std;

 int str[];

 int intToA(long long n, long long radix){

     int len = ;

     if(!n){

         str[] = ;

         return ;

     }

     long long tmp = n;

     do{

         tmp /= radix;

         str[len++] = n - radix * tmp;

         n = tmp;

     }while(n);

     return len;

 }

 long long solve(long long num){

     int n = intToA(num, );

     int c = ;

     for(int i=;i<n;i++){

         if(str[i] + c >= ){

             fill(str, str + i, );

             str[i] = ;

             c = ;

         }

         else{

             str[i] += c;

             c = ;

         }

     }

     long long j = ;

     long long sum = ;

     if(c){

         for(int i=;i<n;i++){

             j *= ;

         }

         return j;

     }

     for(int i=;i<n;i++){

         sum += (long long) (str[i] * j);

         j *= ;

     }

     return sum;

 }

 int main(){

     int q;

     scanf("%d", &q);

     while(q--){

         long long n;

         cin>>n;

         cout<<solve(n)<<endl;

     }

     return ;

 }

巴特西

Codeforces--C2. Good Numbers (hard version)

最新文章

热门文章