钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

2020西北工业大学编程之星程序设计挑战赛F题【反复读密码锁】题解

题面

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

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

如果s为空,那么s=”0”.

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

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

细节

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

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

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

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

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

传送门

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

完整AC代码