【第16题】一道不简单的好题，让我精进了很多很多[CSP-S2019] 格雷码

小码匠

发布于 2023-08-31 14:05:45

2280

发布于 2023-08-31 14:05:45

文章被收录于专栏：小码匠和老码农小码匠和老码农

【第16题】一道好题，让我精进了很多很多[CSP-S2019] 格雷码

下阶段需要精进

减少数据或空间被爆问题在此发生
测试数据（样例、大数据量、边界数据）等自测
OI真理：模拟猜题意，骗分过样例。暴力出奇迹，打表出省一。

一道好题

本题难度：普及-，看似简单，实则让我深入学会了很多知识。

当开了long long还见祖宗时，就开unsigned long long
完爆空间
对位运算深入实践
测试数据

详细看下面题解的各种做法。

题目：[CSP-S2019] 格雷码

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P5662
- 参考题解：https://www.luogu.com.cn/problem/solution/P5662
标签：模拟、位运算、递归
难度：普及-

题解

思路

直接按照题目给的方法打的纯模拟，但是由于k的数据量相当毒瘤所以空间百分百爆了
不开unsigned long long所以卡了5分

题解1：完爆空间（65分做法）

代码

#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);
}

题解2：完爆空间（70分做法）

和题解1的区别继续卡数据范围，提高5分 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);
}

题解3：二分

因为格雷码是不断的倒序和前置位补1所以同一位上前一半是0，后一半是1
因此若k在前一半，则开头是0，反之开头是1
然后输出1后要将k变为它上一轮的值
- 因为当这一位首位为1时k就必然比中间值大
- 递推式：k = t - k
每一轮t都要除以2，然后一共走n轮，接着挨个模拟就好

AC代码

#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;
    }
}

题解4：位运算

本质上就是找规律，只需手打几行表，然后找找正常二进制码排列和格雷码排列进行二进制运算后的值即可
- 从题解区看到了个小技巧，考场做题时可以通过题目里反复出现的词并联系一下后面的题做法找找正解方向

AC代码

#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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除

cin