Carry爱三进制题解

大致题意

两种情况：

1）给出一个十进制数$x$，求$x$对应的的平衡三进制的数

2）给出一个平衡三进制的字符串$s$，求$s$对应的十进制数

tag

• 进制转换
• 模拟

解题思路

1）对于第一种情况：

例如将64转换成平衡三进制。

首先我们将64转化成标准三进制：
$$
64_{10}=02101_3
$$
然后我们从最低位开始处理：

• 101 被跳过（因为在平衡三进制中允许 0 和 1）；
• 2 变成了 Z，它左边的数字加 1，得到 1Z101；
• 1 被跳过，得到 1Z101。

所以最后的结果是1Z101

2）对于第二种情况：

同上，若读入的是1Z101，那么我们可以通过普通进制转换的思想去扫一遍，我们有
$$
1Z101=1\times3^4+(-1)\times3^3+1\times3^2+0\times3^1+1\times3^0=64_{10}
$$
3）对于负数的情况，其实很简单，只需要将正数的数字倒转即可，即Z变成1，1变成Z。

4）对于唯一性的证明，详细请见平衡三进制 - OI Wiki (oi-wiki.org)