题意
给定一段序列的生成方式,问第$n$个元素是多少。 $0<n<2^{63}$。
- $H(1) = 0$
- $H(n) = H(n-1)$中的每个元素$a_i$,那么每个元素就生成一个小子序列$0,0,0,0,0,a_i+1$其中$0$的个数是$a_i$。
- 除了第一个元素之外的所有元素都要进行这种变化
举个例子,
$H(1) = 0$
$H(2) =0,1$ //$0$变成了$0,1$
$H(4) = 0,1,0,2$ //$0$ 变成了$0,1$, $1$变成了$0,2$
$H(8) = 0,1,0,2,1,0,0,3$ //$0$ 变成了$0,1$, $1$变成了$0,2$ ,$2$变成了$0,0,3$
题解
找规律,我们可以发现每次都变化之后序列的长度都翻了一倍。所以我们单独把他增长的序列拿出来看。可以用心去发现这样一个规律。
- 定义增长的序列为$b_i$
- $b_i$是由$1$个$b_{i-1}$,$2$个$b_{i-2}$,$3$个$b_{i-3}$,$4$个$b_{i-4}$…$i$个$b_{0}$ ,再加上一个单独的数字$i$。以此类推出来的。
那么我们就可以从第$n$个元素表示在它属于的那次增长中,它排第几个递归到最初的那几个元素中去,要判断一下范围。
由于题目中的数据比较极限,所以能用unsigned long long 还是用unsigned long long 吧。
如果用unsigned long long。一般数据量输入很小 可以用cin很靠谱。但是要把endl换成’\n’还有输入
1 2
| std::ios::sync_with_stdio(false); cin.tie(0);
|
或者判断他是$2$的几次幂的时候可以这样子判断最高位的$1$在哪里。
1 2 3 4
| ll n; int dep=0; ll temp = n; while(temp) temp>>=1,dep++; dep--;
|
ac代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f;
ll n; ll lie[10][20] ={ {0}, {1}, {0,2}, {1,0,0,3},{0,2,1,1,0,0,0,4}}; ll solve(ll x,int dep){ if(dep<5){ return lie[dep][x]; } ll st = 0; rep(i,2,dep+1){ ll temp = pow(2,dep-i-1); if(i==dep) temp = 1; if(x<temp*(1ll*i-1ll)+st) return solve((x-st)%temp,dep-i); st += temp*(ll)(i-1); } return dep; } int main(){ #ifdef LOCAL freopen("4.in","r",stdin); #endif std::ios::sync_with_stdio(false); cin.tie(0); while(cin>>n && n){ int dep = 0;ll temp = 1; n--; ll tn = n; while(tn) tn/=2,dep++; temp<<=(dep-1); n = n - temp; cout<<solve(n,dep); cout<<'\n'; }
return 0; }
|