Gravatar
llbc1234
积分:16
提交:5 / 15

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
积分:186
提交:22 / 31
%%%%%%%%%%%%%%%%%%%%%%%%%%%

2025-09-25 21:17:17    
Gravatar
PigFlies
积分:5
提交:6 / 15

思路清晰,太厉害了


2025-09-25 21:18:34    
Gravatar
llbc1234
积分:16
提交:5 / 15

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


2025-09-25 21:18:55