自动搬运

查看原文

来自洛谷，原作者为

	SilVeR__WolF 巅峰迎来虚伪的拥护，黄昏见证虔诚的信徒

搬运于2025-08-24 22:58:43，当前版本为作者最后更新于2024-05-19 17:36:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定十进制整数 $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;
}