AcWing 3695. 扩充序列

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long LL;
int n;
LL k;
vector<LL> v{0};
int dfs(int r, LL k) {
    auto it = lower_bound(v.begin(), v.begin() + r, k);
    int idx = it - v.begin();
    if (*it == k) return idx;
    return dfs(idx, v[idx - 1] * 2 - k);
}
int main() {
    cin >> n >> k;
    for (int i = 0; i <= n; ++i) v.emplace_back(pow(2, i));
    int ans = dfs(n + 1, k);
    cout << ans << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long LL;
int n;
LL k;
int dfs(int n, LL k) {
    LL mid = 1ll << n - 1;
    if (k == mid) return n;
    if (k < mid) return dfs(n - 1, k);
    return dfs(n - 1, k - mid);
}
int main() {
    cin >> n >> k;
    cout << dfs(n, k) << endl;
}