题目
平衡三进制，是一种以 3 为基数，-1（以下用T表示）、0、1 为基本数码的进制。由于 -1 的引入，这种进制不需要额外的符号就能直接表示负数。正因为这一点，使得平衡三进制在加减法和乘法方面的效率要比二进制高。
美国著名计算机学家高德纳在《编程的艺术》一书中指出，“也许最美的进制是平衡三进制”。
平衡三进制和其他进制一样，各位的数字和位权相乘然后叠加起来，就是该数的数值。
从低位到高位数第 i 位(从0开始计数)的权值就是 3i 。如十进制数 2 可以表示为 1T ，因为 2 = 1×31 + (-1) ×30 。同理可以表示负数，如 -6 可以表示为 T10 。
平衡三进制不需要额外的符号就可以表示负数。第一个非 0 位是 T 的为负数，第一个非 0 位是 1 的是正数。
在平衡三进制中，各位上的数字之和为偶数的整数是偶数；各位上的数字之和为奇数的整数是奇数。
在平衡三进制中，四舍五入和截位的操作是等效的。
现在，你需要完成十进制到平衡三进制的转换。
输入格式
第一行一个数Q，表示有Q组数据。
下面 Q 行，每行一个整数 x ，表示要转化的十进制数。
输出格式
对于 Q 行中的每一行，输出对应的平衡三进制数。
样例数据 1
输入
6
-13
-10
-6
0
2
8
输出
TTT
T0T
T10
0
1T
10T
备注
【数据规模与约定】
对于 10% 的数据， |x|≤13 。
对于 30% 的数据， |x|≤7174453 。
对于另 30% 的数据， x≥0 。
对于 100% 的数据， |x|≤1018；1≤Q≤104 。
很普通的一道模拟题
两种做法
1、对于一个数，我们可以先用普通的三进制的方式表示出来，然后从小往大位枚举，如果该位上的数是2，那么其实就是它的下一位取一和这一位取-1，，如果是三的话那就直接往下一位进1；
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
char ch=getchar();
ll res=0;
int f=1;
while(!isdigit(ch)) if(ch=='-') f=-1,ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res*f；
}
int T,c[60],f,j;
ll a,tr[60];
inline void solve(ll k)
{
for(int i=1;i<=40;i++)
{
if(tot[i]>=k)
{
j=i;
break;
}
}
for(int i=j;i>=1;i--)//用一般二进制表示出来
{
while(tr[i]<=k) c[i]++,k-=tr[i];
}
for(int i=1;i<=j;i++)
{
if(c[i]==2) c[i]=-1,c[i+1]++;
else if(c[i]==3) c[i]=0,c[i+1]++;
}
}
int main()
{
T=read();
tr[1]=1;
for(int i=2;i<=40;i++)
{
if(tr[i-1]<1000000000000000000)
tr[i]=tr[i-1]*3;
else
{
f=i-1;break;
}
}
while(T--)
{
memset(c,0,sizeof(c));
int y=1;
a=read();
if(a==0)
{
cout<<0<<endl;
continue;
}
if(a<0)//为负数的情况只需要按整数做，最后全部取反就是了
{
y=0;
a=-a;
}
int g;
solve(a);
for(int i=40;i>=1;i--)
{
if(c[i]!=0)
{
g=i;
break;
}
}
if(!y)
{
for(int i=g;i>=1;i--)
{
if(c[i]==1) cout<<"T";
if(c[i]==-1) cout<<1;
if(c[i]==0) cout<<0;
}
}
else
{
for(int i=g;i>=1;i--)
{
if(c[i]==1) cout<<1;
if(c[i]==-1) cout<<"T";
if(c[i]==0) cout<<0;
}
}
puts("");
}
}
方法二、
我们再维护一个前缀和，这样对于一个数a，找到第一个比它大的位j的数m（也就是一个平衡三进制下100…00这样的数），而如果a大于前一个数的1/3(也就是11…1，j-1位，)那么也就是说第j位取1，然后在剩下的位中找a-m，因为a-m小于0，我们可以看作找m-a，然后给取反，最后就可以表示出来了；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
char ch=getchar();
ll res=0;
int zgs=1;
while(!isdigit(ch)) if(ch=='-') zgs=-1,ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res*zgs;
}
int T,c[60],f,j;
ll a,tr[60],tot[60];
int fan[60];//表示取是否反
inline void solve(ll k)
{
for(int i=1;i<=f;i++)//找到第j位
{
if(tot[i]>=k)
{
j=i;
break;
}
}
//cout<<j;
for(int i=j;i>=1;i--)
{
if(tr[i]<=k)c[i]=1,k-=tr[i];
if(tr[i]>k)//如果k小于的话，就相当于i位取1，然后找k-tr[i]的表示，
{
if(tot[i-1]<k)
{
c[i]=1,k=tr[i]-k;
for(int p=1;p<i;p++)
{
fan[p]^=1;//取反标记
}
solve(k);//继续找k-tr[i]的表示
break;
}
}
}
}
int main()
{
T=read();
tr[1]=1;
for(int i=2;i<=40;i++)
{
if(tr[i-1]<1000000000000000000)
tr[i]=tr[i-1]*3;
else
{
f=i-1;break;
}
}
for(int i=1;i<=f;i++)
{
tot[i]=tot[i-1]+tr[i];
}
while(T--)
{
memset(c,0,sizeof(c));
memset(fan,0,sizeof(fan));
int y=1;
a=read();
if(a==0)
{
cout<<0<<endl;
continue;
}
if(a<0)
{
for(int i=1;i<=40;i++)
fan[i]=1;
a=-a;
}
solve(a);
for(int i=40;i>=1;i--)
{
if(c[i]!=0){
j=i;break;
}
}
for(int i=j;i>=1;i--)
{
if(c[i]!=0)
{
if(fan[i]==0)cout<<1;
if(fan[i]==1) cout<<"T";
}
else cout<<0;
}
puts("");
}
}