题解思路

本题要求从一个由数字组成的字符串 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代码

import math

def is_uniform(num):
    """检查一个数字的所有位是否相同"""
    digit = num % 10
    while num:
        if num % 10 != digit:
            return False
        num //= 10
    return True

# 输入
M = input().strip()
N = int(input().strip())
k = input().strip()

max_result = -1
target_password = -1

# 遍历子串长度从12到3，按从长到短顺序枚举
for length in range(min(len(M), 12), 2, -1):
    for i in range(len(M) - length + 1):
        substring = M[i:i + length]
        x = int(substring)

        # 运算操作
        if k == '+':
            result = x + N
        elif k == '-':
            result = x - N
        elif k == '*' and length <= 3:
            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)

C++代码

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

bool is_uniform(long long num) {
    int digit = num % 10;
    while (num) {
        if (num % 10 != digit) return false;
        num /= 10;
    }
    return true;
}

int main() {
    string M;
    long long N, max_result = -1;
    char k;
    cin >> M >> N >> k;

    string target_password = "-1";
    int len = M.length();

    // 从最长的12位到最短的3位逐一遍历
    for (int length = min(len, 12); length >= 3; --length) {
        for (int i = 0; i <= len - length; ++i) {
            string substring = M.substr(i, length);
            long long x = stoll(substring);

            // 运算符判断
            long long result;
            if (k == '+') {
                result = x + N;
            } else if (k == '-') {
                result = x - N;
            } else if (k == '*' && length <= 3) {
                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 {
    public static boolean isUniform(long num) {
        int digit = (int)(num % 10);
        while (num != 0) {
            if (num % 10 != digit) return false;
            num /= 10;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String M = scanner.next();
        long N = scanner.nextLong();
        char k = scanner.next().charAt(0);

        long maxResult = -1;
        String targetPassword = "-1";

        int len = M.length();

        // 从长度12到3逐一遍历
        for (int length = Math.min(len, 12); length >= 3; length--) {
            for (int i = 0; i <= len - length; i++) {
                String substring = M.substring(i, i + length);
                long x = Long.parseLong(substring);

                // 根据运算符进行计算
                long result = 0;
                if (k == '+') {
                    result = x + N;
                } else if (k == '-') {
                    result = x - N;
                } else if (k == '*' && length <= 3) {
                    result = x * N;
                } else {
                    continue;
                }

                // 符合条件检查
                if (isUniform(result)) {
                    if (result > maxResult) {
                        maxResult = result;
                        targetPassword = substring;
                    }
                }
            }
        }

        System.out.println(targetPassword);
    }
}

示例解释

对于输入示例：

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$。