【第16题】一道好题,让我精进了很多很多[CSP-S2019] 格雷码
本题难度:普及-
,看似简单,实则让我深入学会了很多知识。
long long
还见祖宗时,就开unsigned long long
详细看下面题解的各种做法。
题目原文请移步下面的链接
模拟
、位运算
、递归
普及-
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
void coder_solution();
void best_solution();
int main() {
// 小码匠
coder_solution();
// 最优解
//best_solution();
return 0;
}
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
long long n, k;
scanf("%lld%lld", &n, &k);
vector<long long> v(k + 4);
long long t = 1;
long long l = 0;
if (k == 0) {
for (int i = 0; i < n; ++i) {
printf("%d", 0);
}
return;
}
for (long long i = 1; i <= k;) {
long long a = i;
++l;
for (long long j = a - 1; j >= 0 && i <= k; --j, ++i) {
v[i] = v[j] + t;
}
t *= 10;
}
for (int i = 0; i < n - l; ++i) {
printf("%d", 0);
}
printf("%lld", v[k]);
}
void best_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
long long
-> unsigned long long
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
void coder_solution();
void best_solution();
int main() {
// 小码匠
coder_solution();
// 最优解
//best_solution();
return 0;
}
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
unsigned long long n, k;
scanf("%llu%llu", &n, &k);
vector<unsigned long long> v(k + 4);
unsigned long long t = 1;
long long l = 0;
if (k == 0) {
for (int i = 0; i < n; ++i) {
printf("%d", 0);
}
return;
}
for (long long i = 1; i <= k;) {
long long a = i;
++l;
for (long long j = a - 1; j >= 0 && i <= k; --j, ++i) {
v[i] = v[j] + t;
}
t *= 10;
}
for (int i = 0; i < n - l; ++i) {
printf("%d", 0);
}
printf("%llu", v[k]);
}
void best_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
void coder_solution();
void best_solution();
int main() {
// 小码匠
coder_solution();
// 最优解
//best_solution();
return 0;
}
unsigned long long p(unsigned long long n) {
unsigned long long a = 1;
if (n == 64) {
for (unsigned long long i = 0; i < 63; ++i) {
a *= 2;
}
unsigned long long t = a;
--a;
a += t;
return a;
}
for (unsigned long long i = 0; i < n; ++i) {
a *= 2;
}
return a - 1;
}
void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
unsigned long long n, k;
scanf("%llu%llu", &n, &k);
unsigned long long t = p(n);
while(n > 0) {
--n;
unsigned long long m = (t >> 1) + 1;
if(m > k) {
printf("%d", 0);
} else {
printf("%d", 1);
k = t - k;
}
t -= m;
}
}
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
void coder_solution();
void best_solution();
int main() {
// 小码匠
// coder_solution();
// 最优解
best_solution();
return 0;
}
void best_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
unsigned long long n, k;
scanf("%llu%llu", &n, &k);
k ^= (k / 2);
while (n > 0) {
--n;
printf("%llu", k >> n & 1);
}
}
END