第一次写 s 组题解 qwq

废话

如果我说。。。

这个是 找规律的模拟题。

你会震惊嘛（）

怎么想到思路的

假如 $n = 3$ ，可以打个表。

仔细发现，1分布的位置成块状分布，如第一位的0全在 $0 \sim 3$ 之间，1全在 $4 \sim 7$ 之间，而 $k = 3$ 时正好是一半的位置！！！

这难道就是规律？！

读读题昂。。

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

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

请注意第三点中的“逆序”，否则你20分（。。比没开 long long 的还要惨。。）

所以。。思路是

一共有 $n$ 位，所以 $n$ 次循环。

从 $n$ 循环到 $1$ ，第 $i$ 次时判断 $k$ 在中间数的前边还是后边。若是前边那就输出0，否则输出1，记得做逆序处理。

满分了？

#include <iostream>
#include <cmath>
#include <string>

int n, k; // 1 input
std:: string ans; // 2 output
long long tmp;

int main () {
	std:: cin >> n >> k; // 1 input
	for (int i = n; i >= 1; i--) {
		long long tmp = std:: pow (2, i - 1) - 1; // 3 middle number
		if (k <= tmp) {
			ans = ans + "0";
		} // if
		else {
			ans = ans + "1";
			k = std:: pow (2, i) - 1 - k; // 4 res' order
		} // else
	} // for
	std:: cout << ans << "\n";
	return 0;
}

85分。。好吧

看看范围哈 $1 \leq n \leq 64$ , $0 \leq k \lt 2^n$

你会发现 $k$ 的范围到了 $2^n$ 啊啊啊啊啊啊

long long 显然还不够大诶。。

unsigned long long，启动！

全对了！吗？

#include <iostream>
#include <cmath>
#include <string>

unsigned long long n, k; // 1 input
std:: string ans; // 2 output
unsigned long long tmp; // 3 middle number

int main () {
	std:: cin >> n >> k; // 1
	for (int i = n; i >= 1; i--) {
		tmp = std:: pow (2, i - 1) - 1; // 3
		if (k <= tmp) {
			ans = ans + "0";
		} // if
		else {
			ans = ans + "1";
			k = std:: pow (2, i) - 1 - k; // 4 res' order
		} // else
	} // for
	std:: cout << ans << "\n";
	return 0;
}

这不是开了unsigned long long 嘛！！！！！！

其实是 cmath 的 pow() 爆掉了啊啊啊啊啊啊

pow() 似乎达不到 unsigned long long 那么大哦。。。

打表叭

尊的 $AC$ 了

#include <iostream>
#include <string>

unsigned long long n, k; // 1 input
std:: string ans; // 2 output
unsigned long long tmp; // 3 middle number

unsigned long long pow[70]= {1,2,4,8,16,32,64,
           128,256,512,1024,2048,4096,
           8192,16384,32768,65536,131072,262144,
           524288,1048576,2097152,4194304,8388608,16777216,
           33554432,67108864,134217728,268435456,536870912,1073741824,
           2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,
           137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,
           8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,
           562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,
           36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,
           2305843009213693952,4611686018427387904,9223372036854775808
          }; // 4 pow

int main () {
	std:: cin >> n >> k; // 1
	for (int i = n; i >= 1; i--) {
		tmp = pow[i - 1] - 1; // 3
		if (k <= tmp) {
			ans = ans + "0";
		} // if
		else {
			ans = ans + "1";
			k = pow[i] - 1 - k; // 5 res' order
		} // else
	} // for
	std:: cout << ans << "\n";
	return 0;
}

虽然unsigned long long只能存到 $2^{64} - 1$，但可以通过反溢出的“逆天操作”用bug解决bug。

所以。。

满昏！！！！！！！！！！