平衡三进制学习总结
讲解
平衡三进制(Balanced ternary)
挺细的一个知识点，还挺简单的。
简单来说就是一个用标准三进制表示的数进行一个转换。
e p : 64 = ( 02101 ) 3 ep: 64=(02101)_3 ep:64=(02101)3
原本用
(
0
,
1
,
2
)
(0,1,2)
(0,1,2)来表示的数，我们尝试用
(
−
1
,
0
,
1
)
(-1,0,1)
(−1,0,1)表示。
为方便，记
−
1
=
Z
-1=Z
−1=Z
所以有：
64
=
(
1
Z
101
)
3
64=(1Z101)_3
64=(1Z101)3
转换方法：当该位为
0
,
1
0,1
0,1满足直接跳过。
否则当该位为
2
2
2时该位变为
−
1
-1
−1，然后进位。
若该位为
3
3
3则该位变为0，然后进位。
为什么这样做呢？
一个很好理解的方式是：当我们要用到2个 3 k 3^k 3k时，我们可以转换为 3 × 3 k + ( − 1 ) × 3 k = 1 × 3 k + 1 + ( − 1 ) × 3 k 3\times 3^k+(-1)\times 3^k=1\times 3^{k+1}+(-1)\times 3^k 3×3k+(−1)×3k=1×3k+1+(−1)×3k。
当该位为 3 3 3时， 3 × 3 k = 1 × 3 k + 1 3\times 3^k=1\times3^{k+1} 3×3k=1×3k+1。
这两种情况对应上面的两种转换方式！
一个定理：任意整数对应唯一的平衡三进制。
这个证明见 O I − W I K I OI-WIKI OI−WIKI，用反证法证明的。
习题
POJ 1702.Eva’s Balance
给定一个物品，和 3 x 3^x 3x的砝码，要求在左边放物品和若干砝码，右边放若干砝码，使天平平衡。
思路
将标准三进制转换为平衡三进制 { − 1 , 0 , 1 } \{-1,0,1\} {−1,0,1}，该位为-1放左边，为1放右边，为0不放。
代码
// Problem: Eva's Balance
// Contest: POJ - POJ Monthly--2004.07.18
// URL: http://poj.org/problem?id=1702
// Memory Limit: 10 MB
// Time Limit: 1000 ms
// Date: 2021-03-02 15:22:15
// --------by Herio--------
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
int T,c;
void solve(int n){
int a[25]={};
c=0;
while(n) a[++c]=n%3,n/=3;
/*printf("c=%d\n",c);
for(int i=1;i<=c;i++) printf("%d ",a[i]);*/
for(int i=1;i<=c;i++)
if(a[i]>1){
if(a[i]==2) a[i]=-1;
else a[i]=0;
a[i+1]++;
}
if(a[c+1]) c++;
ll s=1;
vector<ll>l,r;
for(int i=1;i<=c;i++,s*=3)
if(a[i]==-1) l.pb(s);
else if(a[i]==1) r.pb(s);
if(l.empty()) printf("empty");
else {
printf("%lld",l[0]);
for(int i=1;i<l.size();i++) printf(",%lld",l[i]);
}
printf(" ");
if(r.empty()) printf("empty");
else {
printf("%lld",r[0]);
for(int i=1;i<r.size();i++) printf(",%lld",r[i]);
}
printf("\n");
}
int main(){
scanf("%d",&T);while(T--){
int n;scanf("%d",&n);
solve(n);
}
return 0;
}
Power Of Three
题意
给定二维无限平面，从 ( 0 , 0 ) (0,0) (0,0)出发到 ( x , y ) (x,y) (x,y)每步只能往一个方向，从第 0 0 0步开始，第 i i i步只能走 3 i 3^i 3i的距离，不能跳步，问是否能到达 ( x , y ) (x,y) (x,y)。
思路
分别处理x,y。
转换平衡三进制，然后合并，要求从最小位到最大位，每个位恰好出现一次，否则无解！
代码
#include <bits/stdc++.h>
using namespace std;
class PowerOfThree
{
public:
string ableToGet(int x, int y)
{
x=abs(x),y=abs(y);
int a[25]={},b[25]={};
int c=0,d=0;
while(x){
a[++c]=x%3,x/=3;
}
while(y){
b[++d]=y%3,y/=3;
}
for(int i=1;i<=c;i++)
if(a[i]>1){
if(a[i]==2) a[i]=-1;
else a[i]=0;
a[i+1]++;
}
if(a[c+1]) c++;
for(int i=1;i<=d;i++)
if(b[i]>1){
if(b[i]==2) b[i]=-1;
else b[i]=0;
b[i+1]++;
}
if(b[d+1]) d++;
int ok=1;
//for(int i=1;i<=c;i++) printf("%d ",a[i]);printf("\n");
// for(int i=1;i<=d;i++) printf("%d ",b[i]);printf("\n");
for(int i=1;i<=max(c,d);i++){
//printf("%d %d\n",a[i],b[i]);
if(abs(a[i])+abs(b[i])!=1){
ok=0;break;
}
}
return ok?"Possible":"Impossible";
}
}A;