题解：P7608 [THUPC 2021] 挑战图灵奖

mc2djwh · 2025-12-03 21:00:05 · 题解

问题：

判断对于给定的 n, k, x，图 C(n, k) 的色数 \alpha 是否等于 x。

图 C(n, k) 的定义为：n 个点排成一个环，每个点与它前后最多 k 个点相连（在模 n 意义下）。

经过分析，我们得到色数 \alpha 的计算公式：

• 如果 n \le k，则图是完全图 K_n，\alpha = n。
• 如果 n > k，令 m = k+1，q = \lfloor n/m \rfloor，则 \alpha = \lceil n / q \rceil。

考虑到数据范围中 n 要么不超过 10^5，要么至少 10^{100}，且 k \le 100，我们可以针对两种情况分别处理：

1. 当 n 较小时（字符串长度不超过 6），直接将其转换为整数计算 \alpha。
2. 当 n 很大时（字符串长度大于 6），由于 n 极大，q = \lfloor n/m \rfloor 也极大，此时 \alpha 只可能是 m 或 m+1。具体来说，计算 r = n \bmod m：
   • 若 r = 0，则 \alpha = m；
   • 若 r > 0，则 \alpha = m+1。

计算出 \alpha 后，将其转换为字符串与输入的 x 字符串比较：

• 若相等，输出正确信息。
• 若不相等，输出错误信息，并指出 x 偏大（输出 1）或偏小（输出 0）。

代码实现：

#include <bits/stdc++.h>
using namespace std;

// 计算大整数 num 模 m 的余数（m 很小）
int js(const string& num, int m) {
    int fh = 0;
    for (char i : num) {
        fh = (fh * 10 + (i - '0')) % m;
    }
    return fh;
}

// 比较两个数字字符串的大小
int cmp(const string& a, const string& b) {
    if (a.length() != b.length())
        return a.length() < b.length() ? -1 : 1;
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}

int main() {
    string n_str, x_str;
    int k;
    cin >> n_str >> k >> x_str;

    int ss; // 色数
    // 根据 n 的长度分情况计算
    if (n_str.length() <= 6) {
        // n 较小，转换为整数计算
        long long n_int = stoll(n_str);
        if (n_int <= k) {
            ss = n_int;
        } else {
            int m = k + 1;
            long long q = n_int / m; // floor(n/m)
            ss = (n_int + q - 1) / q; // ceil(n/q)
        }
    } else {
        // n 极大（n > k 必然成立）
        int m = k + 1;
        int r = js(n_str, m);
        if (r == 0) {
            ss = m;
        } else {
            ss = m + 1;
        }
    }

    string ans = to_string(ss);
    int cmp = cmp(x_str, ans);

    if (cmp == 0) {
        cout << "Correct, but it doesn't necessarily mean that you can win the Turing Award.\n";
    } else {
        cout << "Wrong, don't cheat me, you are too far away from the Turing Award.\n";
        cout << (cmp > 0 ? "1\n" : "0\n");
    }

    return 0;
}

感谢deepseek提供的思路