扩充序列

扩充序列

AcWing 3695
https://www.acwing.com/problem/content/3698/

最简单的思路：递归

代码

递归

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

ll n,k;

ll dfs(ll n,ll k)
{
    if (k == (1ll << n - 1)) return n;
    if (k < (1ll << n - 1)) return dfs(n - 1,k);
    else return dfs(n - 1,k - (1ll << n - 1));
}

int main()
{
    cin >> n >> k;
    
    cout << dfs(n,k);
    
    return 0;
}

找规律
这个规律说实话不好找。
任意数第一、二、三次出现的下标如下规律：

若k不能被2整除，则他就是1.
对于除过1以外的任意一个k，它若能被整除 2，那么它就是一个“扩充得来的数”。
以2为例，其第一二三次出现下标分别为2、6、10，他们都只能被2除1次就变为奇数。

即找k被2除几次变为奇数。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL n,k;

int main()
{
    cin >> n >> k;
    int res = 1; //初始值为1
    while(k % 2 == 0) k /= 2, res++;
    cout << res << endl;
    
    return 0;
}

扩充序列

原文：https://www.cnblogs.com/lijiaji/p/14905147.html