方法思路

这道题目要求找出与模板串匹配的第k小正整数。关键点如下：

1. 模板串中的"?"可以替换为任意数字字符(0-9)
2. 匹配的正整数不能有前导零
3. 需要找出第k小的匹配正整数

解题思路：

1. 计算模板串能匹配的正整数总数
2. 判断k是否超出了匹配数量范围
3. 如果k有效，构造第k小的匹配正整数

具体算法：

• 如果模板串第一位是"?"，则可以填1-9（不能有前导零）
• 其他位置的"?"可以填0-9
• 计算总匹配数：对于第一位是"?"的情况，有9种选择；其他位置的每个"?"有10种选择
• 如果k超过总匹配数，返回-1
• 否则，按照从小到大的顺序构造第k小的匹配正整数

代码实现

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        
        for (int i = 0; i < t; i++) {
            String template = scanner.nextLine();
            long k = scanner.nextLong();
            scanner.nextLine(); // 消耗换行符
            
            System.out.println(findKthMatch(template, k));
        }
    }
    
    public static String findKthMatch(String template, long k) {
        // 计算匹配的正整数总数
        long totalMatches = countMatches(template);
        
        // 如果k超过了总匹配数，返回-1
        if (k > totalMatches) {
            return "-1";
        }
        
        // 构造第k小的匹配正整数
        StringBuilder result = new StringBuilder();
        char[] chars = template.toCharArray();
        
        // 处理第一位
        if (chars[0] == '?') {
            // 第一位是"?"，可以填1-9
            long firstDigitOptions = 9;
            long remainingOptions = totalMatches / firstDigitOptions;
            
            if (k <= remainingOptions) {
                // 第k小的数字以1开头
                result.append('1');
                k = k;
            } else {
                // 计算第一位应该填什么
                int firstDigit = 1;
                while (k > remainingOptions) {
                    k -= remainingOptions;
                    firstDigit++;
                }
                result.append(firstDigit);
            }
        } else {
            // 第一位是数字，直接添加
            result.append(chars[0]);
        }
        
        // 处理剩余位置
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == '?') {
                // 这个位置是"?"，可以填0-9
                long options = (long) Math.pow(10, countQuestionMarks(template, i + 1));
                int digit = 0;
                while (k > options) {
                    k -= options;
                    digit++;
                }
                result.append(digit);
            } else {
                // 这个位置是数字，直接添加
                result.append(chars[i]);
            }
        }
        
        return result.toString();
    }
    
    public static long countMatches(String template) {
        int questionMarks = 0;
        for (char c : template.toCharArray()) {
            if (c == '?') {
                questionMarks++;
            }
        }
        
        if (questionMarks == 0) {
            // 如果没有"?"，只有一种匹配
            // 但需要检查是否有前导零
            if (template.charAt(0) == '0') {
                return 0;
            }
            return 1;
        }
        
        // 计算匹配数
        long matches = 1;
        if (template.charAt(0) == '?') {
            // 第一位是"?"，可以填1-9
            matches *= 9;
            questionMarks--;
        } else if (template.charAt(0) == '0' && template.length() > 1) {
            // 如果第一位是0且长度大于1，则不是有效的正整数
            return 0;
        }
        
        // 其他位置的"?"可以填0-9
        for (int i = 0; i < questionMarks; i++) {
            matches *= 10;
            if (matches > 1_000_000_000) {
                // 防止溢出，如果已经超过10^9，可以直接返回
                return matches;
            }
        }
        
        return matches;
    }
    
    public static int countQuestionMarks(String template, int startIndex) {
        int count = 0;
        for (int i = startIndex; i < template.length(); i++) {
            if (template.charAt(i) == '?') {
                count++;
            }
        }
        return count;
    }
}

Python

def count_matches(template):
    question_marks = template.count('?')
    
    if question_marks == 0:
        # 如果没有"?"，只有一种匹配
        # 但需要检查是否有前导零
        if template[0] == '0':
            return 0
        return 1
    
    # 计算匹配数
    matches = 1
    if template[0] == '?':
        # 第一位是"?"，可以填1-9
        matches *= 9
        question_marks -= 1
    elif template[0] == '0' and len(template) > 1:
        # 如果第一位是0且长度大于1，则不是有效的正整数
        return 0
    
    # 其他位置的"?"可以填0-9
    matches *= 10 ** question_marks
    
    return matches

def find_kth_match(template, k):
    # 计算匹配的正整数总数
    total_matches = count_matches(template)
    
    # 如果k超过了总匹配数，返回-1
    if k > total_matches:
        return "-1"
    
    # 构造第k小的匹配正整数
    result = []
    
    # 处理第一位
    if template[0] == '?':
        # 第一位是"?"，可以填1-9
        first_digit_options = 9
        remaining_options = total_matches // first_digit_options
        
        first_digit = 1
        while k > remaining_options:
            k -= remaining_options
            first_digit += 1
        
        result.append(str(first_digit))
    else:
        # 第一位是数字，直接添加
        result.append(template[0])
    
    # 处理剩余位置
    for i in range(1, len(template)):
        if template[i] == '?':
            # 这个位置是"?"，可以填0-9
            options = 10 ** template[i+1:].count('?')
            digit = 0
            while k > options:
                k -= options
                digit += 1
            
            result.append(str(digit))
        else:
            # 这个位置是数字，直接添加
            result.append(template[i])
    
    return ''.join(result)

t = int(input())
for _ in range(t):
    template = input()
    k = int(input())
    print(find_kth_match(template, k))

C++

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

long long countMatches(const string& template_str) {
    int question_marks = 0;
    for (char c : template_str) {
        if (c == '?') {
            question_marks++;
        }
    }
    
    if (question_marks == 0) {
        // 如果没有"?"，只有一种匹配
        // 但需要检查是否有前导零
        if (template_str[0] == '0') {
            return 0;
        }
        return 1;
    }
    
    // 计算匹配数
    long long matches = 1;
    if (template_str[0] == '?') {
        // 第一位是"?"，可以填1-9
        matches *= 9;
        question_marks--;
    } else if (template_str[0] == '0' && template_str.length() > 1) {
        // 如果第一位是0且长度大于1，则不是有效的正整数
        return 0;
    }
    
    // 其他位置的"?"可以填0-9
    for (int i = 0; i < question_marks; i++) {
        matches *= 10;
        if (matches > 1000000000) {
            // 防止溢出，如果已经超过10^9，可以直接返回
            return matches;
        }
    }
    
    return matches;
}

int countQuestionMarks(const string& template_str, int start_index) {
    int count = 0;
    for (int i = start_index; i < template_str.length(); i++) {
        if (template_str[i] == '?') {
            count++;
        }
    }
    return count;
}

string findKthMatch(const string& template_str, long long k) {
    // 计算匹配的正整数总数
    long long total_matches = countMatches(template_str);
    
    // 如果k超过了总匹配数，返回-1
    if (k > total_matches) {
        return "-1";
    }
    
    // 构造第k小的匹配正整数
    string result;
    
    // 处理第一位
    if (template_str[0] == '?') {
        // 第一位是"?"，可以填1-9
        long long first_digit_options = 9;
        long long remaining_options = total_matches / first_digit_options;
        
        int first_digit = 1;
        while (k > remaining_options) {
            k -= remaining_options;
            first_digit++;
        }
        
        result.push_back('0' + first_digit);
    } else {
        // 第一位是数字，直接添加
        result.push_back(template_str[0]);
    }
    
    // 处理剩余位置
    for (int i = 1; i < template_str.length(); i++) {
        if (template_str[i] == '?') {
            // 这个位置是"?"，可以填0-9
            long long options = pow(10, countQuestionMarks(template_str, i + 1));
            int digit = 0;
            while (k > options) {
                k -= options;
                digit++;
            }
            
            result.push_back('0' + digit);
        } else {
            // 这个位置是数字，直接添加
            result.push_back(template_str[i]);
        }
    }
    
    return result;
}

int main() {
    int t;
    cin >> t;
    
    for (int i = 0; i < t; i++) {
        string template_str;
        long long k;
        cin >> template_str >> k;
        
        cout << findKthMatch(template_str, k) << endl;
    }
    
    return 0;
}