专栏文章

题解：P11825 [TOIP2024] 6174

GGEN_KASOUHA
P11825题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq39ail
此快照首次捕获于
2025/12/03 22:14
3 个月前
此快照最后确认于
2025/12/03 22:14
3 个月前
查看原文

问题分析

1. 四位数的黑洞数61746174
对于任意一个不完全相同的四位数，通过以下步骤可以得到61746174：
将数字按降序排列形成最大数。 将数字按升序排列形成最小数。 用最大数减去最小数，得到新的数字。 重复上述步骤，直到结果为61746174或进入循环。 例如：
从20242024开始：
2024→4220−0224=39962024 → 4220 - 0224 = 3996
3996→9963−3699=62643996 → 9963 - 3699 = 6264
6264→6642−2466=41766264 → 6642 - 2466 = 4176
4176→7641−1467=61744176 → 7641 - 1467 = 6174
此时进入循环，6174→7641−1467=61746174 → 7641 - 1467 = 6174
这一过程最多需要77次迭代
2. 三位数的黑洞数495495
对于任意一个不完全相同的三位数，通过类似的操作，最终会进入循环495495或直接到达495495
3.更高位数的情况
对于更高位数的数字，KaprekarKaprekar过程可能进入更复杂的循环，但最终都会收敛到某个固定点或循环

解题思路

根据题目要求，需要对给定的nn个dd位数分别进行KaprekarKaprekar操作，直到进入循环时的第一个数字。具体步骤如下：
1.对每个输入的d位数，按照降序和升序排列数字
2.计算差值，并重复上述步骤
3.记录第一次进入循环时的数字
CPP
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

// 计算卡布列克差值
int calculateDifference(int num, int d) {
    vector<int> digits;
    while (num > 0) {
        digits.push_back(num % 10);
        num /= 10;
    }
    sort(digits.begin(), digits.end(), greater<int>());
    int maxNum = 0;
    int minNum = 0;
    for (int i = 0; i < d; ++i) {
        maxNum = maxNum * 10 + digits[i];
        if (i > 0) {
            minNum = minNum * 10 + digits[d - 1 - i];
        }
    }
    return maxNum - minNum;
}

// 找到循环起点
int findCycleStart(int num, int d, unordered_set<int>& seen) {
    while (true) {
        int diff = calculateDifference(num, d);
        if (seen.find(diff) != seen.end()) {
            return diff; // 找到循环起点
        }
        seen.insert(num);
        num = diff;
    }
}

int main() {
    int n, d;
    cin >> n >> d;
    unordered_set<int> seen;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        seen.clear(); // 清空已记录的数字
        cout << findCycleStart(num, d, seen) << endl;
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...