[jzoj 1273] 袁绍的刁难 {推理}

题目

Description
　　黄巾之乱后，郭嘉到了袁绍的统辖地区，结果袁绍想给我们的郭嘉大大一个下马威，且正值他招募将领的时候，于是乎，袁绍就让郭嘉大大去替他招募将领。
　　这时候有很多很多的将领到袁绍处报到（别人家底厚，四世三公哪~~），每个将领的编号依次为1、2、3……N，第i个将领的武力值为3^(i-1)。
　　袁绍需要我们的郭嘉大大招纳任意个将领，而郭嘉选中的将领有一个“总武力值”为各个将领的武力值之和。例如：郭嘉这一次招募了第一个将领和第三个将领，那么“总武力值”为1+9=10。
　　袁绍想知道，他可以获得的第k大的“总武力值”是多少，请你帮助我们的郭嘉大大告诉袁绍这个第k大的“总武力值”。
　　从文件中读入k，输出郭嘉能够获得的，第k大的“总武力值”。

Input
　数据包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。

Output
　输出包含n行，每行输出一个对应的结果。

---

解题思路

可以推一下样例。
然后很自然地想到：
$k=a[i]+b数列之前的一个数$k=a[i]+b数列之前的一个数
递归查找即可。

---

代码

#include<cstdio>
#include<algorithm>
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define ll long long
using namespace std;
const int N=35,M=45; 
int n; ll k,a[N+4]={1,1},b[M+4]={1,1}; 
ll dfs(ll x){
	int l=upper_bound(b+1,b+M+1,x)-b; l-=1; 
	if (x==b[l]) return a[l]; else return a[l]+dfs(x-b[l]); 
}
int main(){
//	fre(recruitment); 
	for (int i=2;i<=N;i++) a[i]=a[i-1]*3; 
	for (int i=2;i<=M;i++) b[i]=b[i-1]*2; 
	scanf("%d",&n); 
	while(n--){
		scanf("%lld",&k); 
		dfs(k); 
		printf("%lld\n",dfs(k)); 
	}
}