【进制】JZOJ_1273 袁绍的刁难

题意

有很多个东西，编号为$1\sim N$1∼N，选一个编号为$i$i的东西可获得$3^{i-1}$3i−1的价值。

有多次询问，每次询问求能获得的第$k$k小的价值。

思路

我们把三进制中为$0$0的位看成这个编号的东西不选，$1$1的位看成选。

由于三进制中存在$2$2，所以我们用二进制来处理第$k$k小的选取数列，然后用三进制求答案。

代码

#include<cstdio>
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout)

int n, k;
int a[32];
long long pow3[31];

void solve(int x) {
	int num = 0;
	long long ans = 0;
	for (; x; x /= 2)
		a[++num] = x % 2;
	for (int i = num; i >= 1; i--)
		ans += a[i] * pow3[i - 1];
	printf("%lld\n", ans); 
}

int main() {
	file(recruitment);
	pow3[0] = 1;
	for (int i = 1; i <= 30; i++)
		pow3[i] = pow3[i - 1] * 3;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &k);
		solve(k);
	}
}