题解：P11825 [TOIP2024] 6174

GEN_KASOUHA · 2025-03-02 11:25:52 · 题解

问题分析

1. 四位数的黑洞数6174

对于任意一个不完全相同的四位数，通过以下步骤可以得到6174：

将数字按降序排列形成最大数。 将数字按升序排列形成最小数。 用最大数减去最小数，得到新的数字。 重复上述步骤，直到结果为6174或进入循环。 例如：

从2024开始：

此时进入循环，6174 → 7641 - 1467 = 6174

这一过程最多需要7次迭代

2. 三位数的黑洞数495

对于任意一个不完全相同的三位数，通过类似的操作，最终会进入循环495或直接到达495

3.更高位数的情况

对于更高位数的数字，Kaprekar过程可能进入更复杂的循环，但最终都会收敛到某个固定点或循环

解题思路

根据题目要求，需要对给定的n个d位数分别进行Kaprekar操作，直到进入循环时的第一个数字。具体步骤如下：

1.对每个输入的d位数，按照降序和升序排列数字

2.计算差值，并重复上述步骤

3.记录第一次进入循环时的数字

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