题面描述

给定一个由连续正整数组成的序列，首先将这些数字拼接成一个字符串，然后将字符串中的部分字符打乱顺序。现给定打乱后的字符串和序列的长度，要求还原出原始的连续正整数序列，并输出序列中最小的数字。

思路

1. 理解打乱规则：题目中提到“打乱一部分字符”，但从示例来看，实际上字符串的所有字符都可能被重新排列。因此，可以将其视为字符串的全排列（即字母异位词）。

2. 还原序列：

   • 需要找到一个起始数字 start，使得从 start 开始的 k 个连续正整数拼接成的字符串，与给定的打乱字符串的字符组成相同。
   • 由于输入保证唯一解，可以从较小的数字开始尝试，直到找到符合条件的起始数字。

3. 实现步骤：

   • 字符计数：统计给定字符串中各个数字字符的出现次数。
   • 枚举起始数字：从 1 开始，依次尝试不同的起始数字。
     • 对于每个起始数字，拼接 k 个连续的正整数，形成一个新字符串。
     • 统计新字符串中各个数字字符的出现次数。
     • 比较新字符串的字符计数与给定字符串的字符计数是否相同。
     • 如果相同，当前起始数字即为所求，输出并结束。
   • 范围限制：由于字符串长度不超过 200，且每个数字最多 4 位（因为数字不超过 1000），因此可以将起始数字的范围限定在合理范围内（如 1 到 100000）。

4. 优化：

   • 使用字符计数数组（长度 10）来快速比较两个字符串的字符组成。
   • 一旦找到符合条件的起始数字，即可停止搜索，因为题目保证唯一解。

代码分析

• 函数 count_digits：接收一个字符串，返回一个长度为 10 的数组，表示每个数字字符出现的次数。

• 主函数流程：

  1. 读取输入字符串 s 和序列长度 k。
  2. 计算输入字符串的字符计数。
  3. 从 1 开始，枚举可能的起始数字：
     • 对于每个起始数字，拼接 k 个连续数字形成字符串。
     • 如果拼接后的字符串长度与输入字符串长度不同，跳过当前起始数字。
     • 计算拼接字符串的字符计数，并与输入字符串的字符计数比较。
     • 如果相同，输出当前起始数字并结束程序。
  4. 由于输入保证有唯一解，不需要考虑无解的情况。

cpp

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

// 函数：统计字符串中每个数字字符的出现次数
vector<int> count_digits(const string &s) {
    vector<int> cnt(10, 0);
    for(char c : s) {
        if(isdigit(c)) {
            cnt[c - '0']++;
        }
    }
    return cnt;
}

int main(){
    string s;
    int k;
    cin >> s >> k;
    vector<int> target_cnt = count_digits(s);
    // 枚举起始数字，从1开始
    // 由于字符串长度不超过200，每个数字最多4位，因此起始数字不需要超过100000
    for(int start = 1; start <= 100000; start++){
        string concatenated = "";
        for(int i = 0; i < k; i++){
            concatenated += to_string(start + i);
            // 如果拼接后的长度已经超过输入字符串长度，提前停止
            if(concatenated.length() > s.length()) break;
        }
        // 如果长度不匹配，跳过
        if(concatenated.length() != s.length()) continue;
        // 统计拼接字符串的字符数
        vector<int> current_cnt = count_digits(concatenated);
        // 比较字符数是否相同
        if(current_cnt == target_cnt){
            cout << start;
            return 0;
        }
    }
    return 0;
}

python

from collections import Counter

def main():
    import sys
    s, k = sys.stdin.read().split()
    k = int(k)
    target_cnt = Counter(s)
    
    # 枚举起始数字，从1开始
    # 由于字符串长度不超过200，每个数字最多4位，因此起始数字不需要超过100000
    for start in range(1, 100000):
        concatenated = ''.join(str(start + i) for i in range(k))
        if len(concatenated) != len(s):
            continue
        current_cnt = Counter(concatenated)
        if current_cnt == target_cnt:
            print(start)
            return

if __name__ == "__main__":
    main()

java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    // 函数：统计字符串中每个数字字符的出现次数
    private static Map<Character, Integer> countDigits(String s) {
        Map<Character, Integer> countMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
        }
        return countMap;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int k = scanner.nextInt();
        
        Map<Character, Integer> targetCount = countDigits(s);
        
        // 枚举起始数字，从1开始
        // 由于字符串长度不超过200，每个数字最多4位，因此起始数字不需要超过100000
        for (int start = 1; start <= 100000; start++) {
            StringBuilder concatenated = new StringBuilder();
            for (int i = 0; i < k; i++) {
                concatenated.append(start + i);
            }
            // 如果拼接后的长度与输入字符串长度不同，跳过
            if (concatenated.length() != s.length()) {
                continue;
            }
            Map<Character, Integer> currentCount = countDigits(concatenated.toString());
            // 比较字符数是否相同
            if (currentCount.equals(targetCount)) {
                System.out.println(start);
                return; // 找到后结束程序
            }
        }
    }
}

题目内容

对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。

现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字。

输入描述

输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。

输出描述

输出一个数字，为序列中最小的数字。

示例1

输入

19801211 5

输出

8