2020西北工业大学编程之星程序设计挑战赛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

完整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;
}