AT_past202107_g 题解

· · 题解

前言

本题可以视为平衡三进制的模版题。

1. 前置知识 - 平衡三进制

平衡三进制是一种以 3 为基数，以 -1,0,1 为基本数码的三进制计数体系。为便于书写，一般会将平衡三进制某一位上的 -1 用字母 \text Z 来表示。将一个平衡三进制数转化为十进制，只需要将对应数位上的数乘以 3 的幂次累加即可，计算方法和常规三进制的计算方法相同。

例如要将平衡三进制下的数字 1\text Z101 转化为十进制，计算方法为：

(1\text Z101)_{\text{balance3}}=1\times3^4+(-1)\times3^3+1\times3^2+0\times3^1+1\times3^0=64

从上面的计算流程中我们很容易看出，对于一个给定的十进制数字 n，只需要将其转化为平衡三进制，根据这个由 -1,0,1 构成的序列，就可以将其拆分为满足题意的正负 3 的幂次的组合。

由于平衡三进制不同于常规的三进制，其涉及到负数的数位，因此直接将十进制转化为平衡三进制可能有些困难，为此我们可以先将十进制转化为常规三进制，再转化为平衡三进制。

2. 十进制转化为常规三进制

十进制转化为普通三进制，只需要重复“模 3 然后整除 3”的流程, 将给定的整数转化为一串由数字 0,1,2 构成的序列即可，参考代码如下：

int tp[100];
void dec2base3(long long t) //将十进制转化为普通三进制, 使用数组存储每一位, 下标小的表示低位, 下标大的表示高位
{
    int index = 0;//当前的数位
    while (t)
    {
        tp[index] = t % 3;
        t /= 3;
        index += 1;
    }
    return;
}

3. 常规三进制转化为平衡三进制

由于 3-1=2，因此将常规三进制转化为平衡三进制时，需要将三进制上为 2 的位变成 -1，然后进位。如果这个进位导致前一位变成 3，也需要进位，以此类推，参考代码如下：

void base2balance3()//将普通三进制转化为平衡三进制, 平衡三进制的每一位由-1, 0或1构成
{
    for (int i = 0; i <= 99; i += 1)
    {
        if (tp[i] == 2)//如果某一位是2, 这一位就变成-1, 然后高位增加1
        {
            tp[i] = -1;
            tp[i + 1] += 1;
        }
        if (tp[i] == 3)//如果某一位是3, 和普通三进制一样, 要进位
        {
            tp[i] = 0;
            tp[i + 1] += 1;
        }
    }

}

4. 输出

按照平衡三进制的序列，输出 1 或 -1 乘以 3 的幂次即可。需要注意的是如果平衡三进制的某一位为 0，答案中不能输出 0，直接跳过。由于输出的第一行是个数，因此需要统计平衡三进制中不为零的数位个数。

参考代码：

for (index = 99; index >= 0; index -= 1) if (tp[index]) break;//找到第一个不为零的数位
for (int i = index; i >= 0; i -= 1) if (tp[i]) tot += 1;/*平衡三进制如果某一位是0, 就不输出, 所以要判断总共要输出多少位!*/
printf("%d\n", tot);
for (int i = index; i >= 0; i -= 1) if(tp[i]) printf("%.0Lf ", powl(3.L, i) * tp[i]);

5. 完整代码

#pragma warning(disable:4996)
#include <cstdio>
#include <algorithm>
#include <cmath>
long long n, index, tot = 0;
int tp[100];
void dec2base3(long long t) //将十进制转化为普通三进制, 使用数组存储每一位, 下标小的表示低位, 下标大的表示高位
{
    int index = 0;//当前的数位
    while (t)
    {
        tp[index] = t % 3;
        t /= 3;
        index += 1;
    }
    return;
}
void base2balance3()//将普通三进制转化为平衡三进制, 平衡三进制的每一位由-1, 0或1构成
{
    for (int i = 0; i <= 99; i += 1)
    {
        if (tp[i] == 2)//如果某一位是2, 这一位就变成-1, 然后高位增加1
        {
            tp[i] = -1;
            tp[i + 1] += 1;
        }
        if (tp[i] == 3)//如果某一位是3, 和普通三进制一样, 要进位
        {
            tp[i] = 0;
            tp[i + 1] += 1;
        }
    }

}
int main()
{
    scanf("%lld", &n);
    dec2base3(n);
    base2balance3();
    /*调试用代码块 - 一般用Z表示-1, 倒序输出即可得到输入整数的平衡三进制的序列
    for (int i = 99; i >= 0; i -= 1)
    {
        if (tp[i] == 0) putchar('0');
        if (tp[i] == -1) putchar('Z');
        if (tp[i] == 1) putchar('1');
    }
    */
    for (index = 99; index >= 0; index -= 1) if (tp[index]) break;
    for (int i = index; i >= 0; i -= 1) if (tp[i]) tot += 1;/*平衡三进制如果某一位是0, 就不输出, 所以要判断总共要输出多少位!*/
    printf("%d\n", tot);
    for (int i = index; i >= 0; i -= 1) if(tp[i]) printf("%.0Lf ", powl(3.L, i) * tp[i]);
}