只能吃土豆的牛牛

题目描述

旅行完了的牛牛又胖了，于是他终于下决心要戒掉零食，所以他带着他最爱的土豆回到了牛星，开始了在牛星种土豆和只吃土豆减肥的日子。（吃土豆能减肥么？）经过了辛勤的劳作，牛牛种的土豆奇迹般的收获了，于是他得到了很多很多很多很多的土豆（实在太多，数不过来了，你可以认为是无穷个）。他将这很多很多个土豆按照重量从小到大进行了排序，每个土豆的编号依次为1、2、3……N，然后他就惊奇地发现：由于牛星球的土壤很奇特，第i个土豆的重量正好是3^(i-1) 。
现在牛牛饿了要吃掉其中的若干个土豆。他每次拿的土豆的数目是任意的，选的土豆也是任意的。选中的土豆的总重量即每个土豆重量之和。例如：牛牛这一次拿了第一个土豆和第三个土豆，那么总重量为1+9=10。
牛牛想知道，在所有的选土豆方案里，他可以获得的第k大的“总重量”是多少。

输入描述:

有多组输入样例。
第一行是一个整数T，表示有T组测试样例，0 ≤ T ≤ 70。
之后的T行中，每一行有一个数字k。（k<=2^31-1）

输出描述:

针对每一个测试样例，输出一行；格式为：
“Case #A”，其中，A表示他可以获得的第k大的总重量。

题解

赤裸裸考思维，感觉这道题应该是本场比赛的签到题。
每一个数都对应一个排名，这个排名可以用二进制唯一表示，题目要你求在三进制体系下排名第K位的是谁，那么我们把给我们的排名看成一个01串，把这个01串对应到这个数字是否存在就好了。可以举几个样例自己算一算，好好理解一下

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)

template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
ll ans(ll num){
    ll sum=0,t=1;
    while(num){
        if(num&1)sum=sum+t;
        t*=3;
        num>>=1;
    }
    return sum;
}
////////////////////////////////////////////////////////////////////////
int main(){
    int T=gn();
    for(int z=1;z<=T;++z){
        ll k=gl();
        printf("Case #%d: %lld\n",z,ans(k));
    }
}