题解：SP21169 TAP2014B - Balanced base-3

_WCW_ · 2025-06-08 09:20:12 · 题解

题目传送门

题目大意

给你一个十进制数，转成平衡三进制（定义见题目中），之后将转换后的平衡三进制数按照题目要求输出。

解题思路

直接转换平衡三进制不好转换，我们可以先将几个数转换成普通三进制，再和人工转换的平衡三进制对比一下。

由于直接表示负数不方便，所以下表中用 N 来表示某一位上的负数。

我们可以发现，在普通三进制下是 2 的某一位，到了平衡三进制下会变成 -1，并且向前进一位，对于 0 和 1 则不变。 按照这个思路，我们可以把一个数转成普通三进制，之后按照上面的运算规则进行转换，最后按照题目要求输出即可。

（如果你还是没看懂，可以看这里）。

AC 代码

#include<bits/stdc++.h>
using std::cout;
using std::cin;
using std::array;
int t,n,cnt;//t和n为题中意思，cnt表示最后结果位数
array<int,1010> num;//存储转普通三进制后的结果和转平衡三进制后的结果
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);//cin和cout效率优化
    cin>>t;//输入个数
    for(int i=1;i<=t;i++)//循环t次
    {
        bool jw=0;//进位标记变量，默认为false
        cnt=1;//初始化cnt为1
        cin>>n;//输入n
        while(n)//转为普通三进制，不明白原理请看文末
        {
            num[cnt++]=n%3;
            n/=3;
        }
        num[cnt++]=0;//多存一位，防止进位
        for(int j=1;j<cnt;j++)
        //循环每一位，j<cnt是因为在最后一次循环cnt会多加1
        {
            if(jw)//如果上一位到这一位有进位
            {
                num[j]++;//加1
                jw=0;//进位完毕，改为false
            }
            if(num[j]==2)//如果这一位为2
            {
                jw=1;//需要进位
                num[j]=-1;//当前为设置为-1
            }
            else if(num[j]==3)//如果这一位为3
            {
                jw=1;//需要进位
                num[j]=0;//普通三进制下满三进一，这一位为0不用管，向高位进1
            }
            //0或1的情况不用管
        }
        while(cnt>=1 && num[cnt-1]==0) cnt--;//去除最前面可能的0
        for(int j=cnt-1;j>=1;j--)//由于倒序存储，这里要倒着输出
        {
            //按照题目中的要求进行输出
            if(num[j]==0) cout<<0;
            else if(num[j]==1) cout<<'+';
            else if(num[j]==-1) cout<<'-';
        }
        cout<<'\n';//换行
    }

    return 0;
}

（OI Wiki）进制转换