Gravatar
llbc1234
积分:20
提交:7 / 30

Pro3289  [CSP 2019S]格雷码

题目大意

按照格雷码的生成方式,输出 n 位格雷码的第 k 号二进制串。(从 0 开始编号)

思路

填完第 k 个 n 位格雷码的第 1 位后,把它转化成某一个 n−1 位格雷码继续填这个 n−1 位格雷码的第 1 位,以此类推。

如何确定转化成第几个 n−1 位格雷码:

当 k<2n−1,因为这个 n 位格雷码的前 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码正序排列而成的,所以 k 保持不变。

当 k≥2n−1,因为这个 n 位格雷码的后 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码逆序排列而成的,所以 k 要先减去 2n−1,变成 n−1 位格雷码,再翻转才能保证是逆序的,即 k=r-k+l



2025-09-25 21:06:01    
我有话要说
Gravatar
hsl_beat
积分:213
提交:33 / 51
%%%%%%%%%%%%%%%%%%%%%%%%%%%

2025-09-25 21:17:17    
Gravatar
PigFlies
积分:24
提交:19 / 52

思路清晰,太厉害了


2025-09-25 21:18:34    
Gravatar
llbc1234
积分:20
提交:7 / 30

回复@hsl_beat : ばんしょう てんびき


2025-09-25 21:18:55