题解思路

本题要求从一个由数字组成的字符串 M 中找到一个子串，与一个给定的数字 N 进行运算（加、减、乘），使得运算结果符合以下条件：

1. 结果的所有数位相同：即运算结果的每一位数都相同（例如 4444、77777 等）。
2. 选择最大值：若有多个符合条件的子串，则选择运算结果最大的一个子串作为最终答案。

运算规则要求子串长度在 3 到 12 之间，并且在乘法运算的情况下，子串最多 3 位，以防止结果过大。

详细步骤

1. 遍历子串：由于密码串的长度限制在 3 到 12 之间，因此我们可以枚举从 M 中提取不同长度的子串。以长度从 12 到 3 的顺序枚举，可以在找到符合要求的结果后提前结束遍历。

2. 计算运算结果：

   • 对每一个提取出的子串，根据运算符 k（加、减、乘），与密钥数字 N 进行计算，得到运算结果。
   • 运算结果需要满足所有位数相同。为此，检查结果的各位数，判断其是否符合条件。

3. 结果筛选：

   • 如果运算结果的各位数相同且比当前最大值大，则更新最终结果。
   • 若有多个符合条件的子串，则选择其中运算结果最大的子串。

4. 终止条件：如果在当前长度的子串中找到满足要求的最大值，则直接输出结果。否则，继续尝试较短的子串，直到找到符合条件的结果。

复杂度分析

• 时间复杂度：对于字符串长度 N，子串的长度上限为 12，因此枚举子串的复杂度约为 O(N * 12)。对于每个子串，进行一次运算和检测符合条件的操作，时间复杂度为常数级。因此，整体时间复杂度为 O(N)。
• 空间复杂度：仅需常数空间存储运算结果和遍历子串，不涉及额外的复杂数据结构，因此空间复杂度为 O(1)。

代码实现

Python代码

def is_uniform(num):
    """检查一个数字的所有位是否相同"""
    if num < 0:
        return False  # 负数不符合条件
    num_str = str(num)
    return all(digit == num_str[0] for digit in num_str)

def main():
    import sys

    # 读取输入
    M = sys.stdin.readline().strip()
    N_str = sys.stdin.readline().strip()
    k = sys.stdin.readline().strip()

    # 尝试将 N 转换为整数，并进行基本验证
    try:
        N = int(N_str)
    except ValueError:
        print(-1)
        return

    # 检查 N 是否在有效范围内
    if N < 0 or N > 9999999999:
        print(-1)
        return

    # 如果运算符是乘法，检查 N 是否不超过 999
    if k == '*':
        if N > 999:
            print(-1)
            return

    max_result = -1
    target_password = -1

    # 遍历子串长度从3到12
    for length in range(3, min(len(M), 12) + 1):
        for i in range(len(M) - length + 1):
            substring = M[i:i + length]
            
            # 跳过以0开头且长度大于1的子串
            if substring[0] == '0' and length > 1:
                continue

            x = int(substring)

            # 执行运算
            if k == '+':
                result = x + N
            elif k == '-':
                result = x - N
                if result < 0:
                    continue  # 结果为负数，不符合条件
            elif k == '*':
                result = x * N
            else:
                continue  # 无效的运算符，跳过

            # 检查结果是否所有位相同
            if is_uniform(result):
                if result > max_result:
                    max_result = result
                    target_password = substring

    # 输出结果
    print(target_password if target_password != -1 else -1)

if __name__ == "__main__":
    main()

C++代码

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

// 检查一个数字的所有位是否相同
bool is_uniform(long long num) {
    if (num < 0) return false; // 负数不符合条件
    string num_str = to_string(num);
    char first_digit = num_str[0];
    for(char c : num_str){
        if(c != first_digit){
            return false;
        }
    }
    return true;
}

int main(){
    string M;
    long long N;
    char k;
    cin >> M >> N >> k;

    // 检查秘钥数字 N 是否在有效范围内
    if(N < 0 || N > 9999999999){
        cout << "-1" << endl;
        return 0;
    }

    // 如果运算符是乘法，检查 N 是否不超过 999
    if(k == '*' && N > 999){
        cout << "-1" << endl;
        return 0;
    }

    string target_password = "-1"; // 默认输出为 -1
    long long max_result = -1; // 初始化最大结果为 -1
    int len = M.length();

    // 遍历所有可能的子串长度，从3到12
    for(int length = 3; length <= min(12, len); length++){
        for(int i = 0; i <= len - length; i++){
            string substring = M.substr(i, length);
            
            // 跳过以 '0' 开头且长度大于1的子串
            if(substring[0] == '0' && length > 1){
                continue;
            }

            long long x;
            try{
                x = stoll(substring);
            }
            catch(...){
                continue; // 如果转换失败，跳过该子串
            }

            long long result;
            if(k == '+'){
                result = x + N;
            }
            else if(k == '-'){
                result = x - N;
                if(result < 0){
                    continue; // 结果为负数，不符合条件
                }
            }
            else if(k == '*'){
                result = x * N;
            }
            else{
                continue; // 无效的运算符，跳过
            }

            // 检查运算结果是否所有位相同
            if(is_uniform(result)){
                if(result > max_result){
                    max_result = result;
                    target_password = substring;
                }
            }
        }
    }

    cout << target_password << endl; // 输出结果
    return 0;
}

Java代码

import java.util.Scanner;

public class Main {
    /**
     * 检查一个数字的所有位是否相同。
     * @param num 要检查的数字。
     * @return 如果所有位相同且非负，返回 true；否则返回 false。
     */
    public static boolean isUniform(long num) {
        if (num < 0) return false; // 负数不符合条件
        String numStr = Long.toString(num);
        char firstDigit = numStr.charAt(0);
        for(int i = 1; i < numStr.length(); i++) {
            if(numStr.charAt(i) != firstDigit){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String M = scanner.next();
        long N;
        try {
            N = scanner.nextLong();
        } catch(Exception e){
            System.out.println("-1");
            return;
        }
        String kStr = scanner.next();
        if(kStr.length() == 0){
            System.out.println("-1");
            return;
        }
        char k = kStr.charAt(0);

        // 检查秘钥数字 N 是否在有效范围内
        if(N < 0 || N > 9999999999L){
            System.out.println("-1");
            return;
        }

        // 如果运算符是乘法，检查 N 是否不超过 999
        if(k == '*' && N > 999){
            System.out.println("-1");
            return;
        }

        long maxResult = -1;
        String targetPassword = "-1";
        int len = M.length();

        // 遍历所有可能的子串长度，从3到12
        for(int length = 3; length <= Math.min(12, len); length++) {
            for(int i = 0; i <= len - length; i++) {
                String substring = M.substring(i, i + length);

                // 跳过以 '0' 开头且长度大于1的子串
                if(substring.charAt(0) == '0' && length > 1){
                    continue;
                }

                long x;
                try {
                    x = Long.parseLong(substring);
                } catch(NumberFormatException e){
                    continue; // 如果转换失败，跳过该子串
                }

                long result;
                if(k == '+'){
                    result = x + N;
                }
                else if(k == '-'){
                    result = x - N;
                    if(result < 0){
                        continue; // 结果为负数，不符合条件
                    }
                }
                else if(k == '*'){
                    result = x * N;
                }
                else{
                    continue; // 无效的运算符，跳过
                }

                // 检查运算结果是否所有位相同
                if(isUniform(result)){
                    if(result > maxResult){
                        maxResult = result;
                        targetPassword = substring;
                    }
                }
            }
        }

        System.out.println(targetPassword);
    }
}

javascript

const readline = require("readline");

const rl = readline.createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readLine = async () => (await iter.next()).value;

/**
 * 检查一个数字的所有位是否相同。
 * @param {number} num 要检查的数字。
 * @return {boolean} 如果所有位相同且非负，返回 true；否则返回 false。
 */
function isUniform(num) {
    if (num < 0) return false; // 负数不符合条件
    let numStr = num.toString();
    let firstDigit = numStr[0];
    return numStr.split("").every(digit => digit === firstDigit);
}

async function main() {
    let M = await readLine(); // 读取第一个字符串
    let N;
    
    try {
        N = BigInt(await readLine()); // 读取秘钥数字 N，使用 BigInt 以避免超出范围
    } catch (e) {
        console.log("-1");
        return;
    }

    let kStr = await readLine();
    if (kStr.length === 0) {
        console.log("-1");
        return;
    }
    let k = kStr[0]; // 获取运算符

    // 检查秘钥数字 N 是否在有效范围内
    if (N < 0 || N > 9999999999n) {
        console.log("-1");
        return;
    }

    // 如果运算符是乘法，检查 N 是否不超过 999
    if (k === '*' && N > 999n) {
        console.log("-1");
        return;
    }

    let maxResult = -1n;
    let targetPassword = "-1";
    let len = M.length;

    // 遍历所有可能的子串长度，从 3 到 12
    for (let length = 3; length <= Math.min(12, len); length++) {
        for (let i = 0; i <= len - length; i++) {
            let substring = M.substring(i, i + length);

            // 跳过以 '0' 开头且长度大于1的子串
            if (substring[0] === '0' && length > 1) {
                continue;
            }

            let x;
            try {
                x = BigInt(substring); // 使用 BigInt 处理大数
            } catch (e) {
                continue; // 如果转换失败，跳过该子串
            }

            let result;
            if (k === '+') {
                result = x + N;
            } else if (k === '-') {
                result = x - N;
                if (result < 0) {
                    continue; // 结果为负数，不符合条件
                }
            } else if (k === '*') {
                result = x * N;
            } else {
                continue; // 无效的运算符，跳过
            }

            // 检查运算结果是否所有位相同
            if (isUniform(result)) {
                if (result > maxResult) {
                    maxResult = result;
                    targetPassword = substring;
                }
            }
        }
    }

    console.log(targetPassword);
    rl.close();
}

// 运行主函数
main();

示例解释

对于输入示例：

1. 若 M = "6833023887793076998810418710", N = 2211, k = '-'：

   • 符合条件的子串有 8877 和 9988。 9988 - 2211 = 7777 是最大结果。

2. 若 M = "68846787793076946788418710", N = 4210, k = '+'：

   • 符合条件的子串为 884678，884678 + 4210 = 888888 是最大结果。

题目内容

在全球恐怖主义危机下，一组间谍团队接收到了来自地下工作者的一串神秘代码。这组代码可以帮助他们访问恐怖分子的服务器，但是他们需要先解密代码才能使用它。代码是由数字$0$ - $9$ 组成的字符串 $M$，而解密过程需要一个秘钥数字 $N$ 和一个运算符 $k$ (加减乘中的一个)。

解密过程分为三个步骤：

第一步，团队成员需要使用秘钥数字 $N$ 对 $M$ 进行一系列 $k$ 运算，并尝试截取其中的一段数字 $x$。如果 $x$ 和 $N$ 的运算结果是一个所有位数相同的数字，那么这段数字就有可能是真正的密码。例如，如果 $x$ 为 $111$，$N$ 为 $2$，$k$ 为乘法，那么计算结果是 $111 \times 2 = 222$，满足条件，因此 $111$ 就是所寻找的目标密码串之一。

第二步，如果存在多种满足第一点条件的情况，那么团队成员需要选择计算结果最大的一种作为真正的密码。

第三步，团队成员们需要在 $M$ （$M$的长度不超过100） 中找到长度为 $3$ 到 $12$ 位的密码串，并尝试使用秘钥数字 $N$ 和运算符 $k$ （$k$ 为 $+$ 或 $-$ 或 $*$的一种）进行解密。由于秘钥数字 $N$ 可能非常大，因此需要确保 $N$ 不大于 $9999999999$。另外，在乘法场景下，团队成员们约定乘数最大为 $3$ 位数，以避免数据过于庞大。 如果没有找到符合条件的密码串，则输出 $-1$，表示密码串不存在。

输入描述

输入第一行为加密后的字符串$M$

输入第二行为密钥数字$N$

输入第三行为运算符$k$

输出

满足计算结果所有位数相同，且计算结果最大的值。

样例1

输入

6833023887793076998810418710
2211
-

输出

9988

解释：通过计算， $8877$ - $2211$= $6666$ 而 $9988$ - $2211$ = $7777$，因为$7777$ > $6666$，则目标密码串为$9988$。

样例2

输入

68846787793076946788418710
4210
+

输出

884678

解释:通过计算，符合条件有两个，$884678$ + $4210$ = $888888$，$4678$ + $4210$ = $8888$。则目标密码串为$884678$。

样例3

输入

139804444677899222
2
*

输出

4444

解释:作为乘法场景，乘数最大值为 $3$ 位数，本用例乘数为 $2$ 。按要求，$4444$ * $2$ = $8888$， $222$ * $2$ = $444$，均符合基本条件，从中选择结果最大值则目标密码串是$4444$。