F题【反复读密码锁】题解

题面

https://ac.nowcoder.com/acm/contest/11290/F

从S的生成过程研究递推关系

如果s为空，那么s="0".

如果s不为空，就在ss后面再添加s这个序列。s表示将s序列中的0变为1，1变为0.

很显然，当我们已知 1 ~ 2ⁿ 的序列时, 我们可以通过取反获得 (2ⁿ + 1) ~ 2ⁿ⁺¹ 的序列, 也就是说第 2ⁿ + k 项实际上可以通过对第 k 项取反得到.
于是我们就得到了递推关系, 那么我们需要做什么呢?
假设我们需要求第 p 项, 而 p = 2ⁿ + k , 我们需要做的就是求第 k 项并取反, 对 k 重复上述步骤.
于是递归就写出来了, 下面考虑递归的边界条件, 很显然, 只要考虑第一项和第二项就可以了(不会求就去吟诗啊, 苟...).

细节

首先上述的递推是对第 n 项求的, 而题目问的是第 n 次操作后的下一个密码, 所以实际上是求第 n + 1 项.

如何构建由 p 到 k 的转移呢? 很显然, 涉及二进制, 当然是用位运算啦, 一番搜索,获得如下代码:
https://blog.csdn.net/qq_41709801/article/details/88371152

这份代码是将最高的为1的二进制位之后全部置1, 那么略作修改就可以求出 p = 2ⁿ + k 中的 2ⁿ 了.

我们知道, 2ⁿ - 1 的二进制形式就是全为1, 我们把这个1给加回去就可以得到 2ⁿ 了, 需要注意是如果直接加1, 得到的会是 2^{n + 1} , 所以我们需要进行移位操作(我就是喜欢先移位, 略略略).

那么问题来了, 如果 k = 0 会发生什么? 很显然, 此时会出现bug, 此时的 p 实际对应的是 2^{n - 1} ,而不是0, 所以我们需要加上一个判断来处理这种情况.

传送门

队友写也写了这题的题解, 既然他画了图, 那我就不画了.
https://blog.csdn.net/qq_52140965/article/details/112723289

原文发布在个人博客, 链接如下:
https://jiafeimiao.top/2021/01/16/2020%E8%A5%BF%E5%8C%97%E5%B7%A5%E4%B8%9A%E5%A4%A7%E5%AD%A6%E7%BC%96%E7%A8%8B%E4%B9%8B%E6%98%9F%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E6%8C%91%E6%88%98%E8%B5%9BF%E9%A2%98%E3%80%90%E5%8F%8D%E5%A4%8D%E8%AF%BB%E5%AF%86%E7%A0%81%E9%94%81%E3%80%91%E9%A2%98%E8%A7%A3/

完整AC代码

#include<cstdio>
using namespace std;
typedef long long ll;
ll high_bit(ll x){ 
    x >>= 1;
    x = x|(x>>1);
    x = x|(x>>2);
    x = x|(x>>4);
    x = x|(x>>8);
    x = x|(x>>16);
    x = x|(x>>32);
    x++;
    return x;
} 
int find(ll n){
    if (n == 1)    return 0;
    if (n == 2)    return 1;
    ll temp = high_bit(n);
    if (temp == n)    n >>= 1;
    else    n -= temp;
    return !find(n);
}
int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        ll n;
        scanf("%lld", &n);
        printf("%d\n", find(n + 1));
    }
    return 0;
}