[CSP-S 2019]格雷码

题目大意：

格雷码（Gray Code）是一种特殊的 \(n\) 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。

\(n\) 位格雷码不止一种，下面给出其中一种格雷码的生成算法：

\(1\) 位格雷码由两个 \(1\) 位二进制串组成，顺序为：\(0\)，\(1\)。
\(n+1\) 位格雷码的前 \(2^n\) 个二进制串，可以由依此算法生成的 \(n\) 位格雷码（总共 \(2^n\) 个 \(n\) 位二进制串）按顺序排列，再在每个串前加一个前缀 \(0\) 构成。
\(n+1\) 位格雷码的后 \(2^n\) 个二进制串，可以由依此算法生成的 \(n\) 位格雷码（总共 \(2^n\) 个 \(n\) 位二进制串）按逆序排列，再在每个串前加一个前缀 \(1\) 构成。

综上，\(n + 1\) 位格雷码，由 \(n\) 位格雷码的 \(2^n\) 个二进制串按顺序排列再加前缀 \(0\)，和按逆序排列再加前缀 \(1\) 构成，共 \(2^{n+1}\) 个二进制串。另外，对于 \(n\) 位格雷码中的 \(2^n\) 个二进制串，我们按上述算法得到的排列顺序将它们从 \(0 \sim 2^n - 1\) 编号。

现在给出 \(n\)，\(k\)，请你求出按上述算法生成的 \(n\) 位格雷码中的 \(k\) 号二进制串。

\(1\le n\le 64, 0<k<2^n\)

思路：

从\(n-1\)到\(0\)确定每一位。若\(k\)的当前位为\(1\)，则对应的格雷码该位也为\(1\)，并将\(k\)剩下未处理的位取反；若\(k\)的当前位为\(1\)，则对应的各类吗改为也为\(0\)，不取反。

源代码：

#include<cstdio>

#include<cctype>

typedef unsigned long long uint64;

inline uint64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register uint64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

int main() {

	freopen("code.in","r",stdin);

	freopen("code.out","w",stdout);

	const int n=getint();

	uint64 k=getint();

	for(register int i=n-1;i>=0;i--) {

		const bool cur=(k>>i)&1;

		putchar(cur?'1':'0');

		if(cur) k=~k;

	}

	puts("");

	return 0;

}

巴特西

[CSP-S 2019]格雷码

[CSP-S 2019]格雷码

题目大意：

思路：

源代码：

最新文章

热门文章