题解：P10510 进制

· · 题解

题目大意

给定十进制整数 V 和 Q 次操作，先将 V 转化为 3 进制数字串 s，再输出每次操作后 s 对应的十进制整数的值。

前置知识

如何实现进制转换

思路分析

对一个 3 进制的数字串的其中一位做改变，就是将这一位上的基数改变，最终的改变值就是该位上的改变数量 \times 该位上的位权。

这样做的时间复杂度为 O(\log_{3}{V}+Q)。

代码如下（详见注释）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int h[40],s[40],v,q,opt,i,ans;//经计算，log(3)1e18 大约在 40 左右，所以数组容量只用 40 
const int cs[4][3]={{},{1,2,0},{2,0,1},{0,2,1}};//打表，注意 opt 从 1 计数 
void cvs(int n,int k)//功能：将 n 转换成 3 进制并按低位到高位的顺序存进 h 数组
{
    if(n>=3){
        h[k]=n%3;
        cvs(n/3,k+1);
        return;
    }
    h[k]=n;
    return;
}
void init()//在 s 数组中存入 3 的次方。之前我用 pow 不行，有神犇知道为什么吗？ 
{
    s[0]=1;
    for(int p=1;p<40;p++)
        s[p]=s[p-1]*3;
}
signed main(){
    scanf("%lld%lld",&v,&q);
    cvs(v,0);init();ans=v;//给 ans 赋初值
    while(q--)
    {
        scanf("%lld%lld",&opt,&i);
        ans=ans+s[i]*(cs[opt][h[i]]-h[i]);//将 ans 加上第 i 位位权 * 改变数量 
        h[i]=cs[opt][h[i]];//做修改，因为之后可能还会对这位进行修改 
        printf("%lld\n",ans);
    }
    return 0;
}