在线评测链接:P1307

题目内容

在全球恐怖主义危机下，一组间谍团队接收到了来自地下工作者的一串神秘代码。这组代码可以帮助他们访问恐怖分子的服务器，但是他们需要先解密代码才能使用它。代码是由数字 $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
-

输出

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

样例2

输入

68846787793076946788418710
4210
+

输出

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

样例3

输入

139804444677899222
2
*

输出

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

思路：模拟+枚举

我们现在有一串数字字符串 $M$ ，同时还有另一串数字字符串 $N$ 以及一个运算符 $k\in\left\{'+','-','*'\right\}$ ，我们需要找到 $M$ 中是否有一串数字(长度为3-12)组成的整数，该整数与 $N$ 组成的整数进行字符 $k$ 代表的运算后，能使得运算结果的所有数位都是同一个数字，比如6666。

和该日华为第一题一样，直接按照题意模拟即可。

由于规定密码串的长度为3~12位，且要求计算结果最大。因此我们可以从大到小枚举密码串的长度，也即我们从数字字符串 $M$ 中取出的连续数字字符的个数。用这些数字字符构成一个整数后，与数字串 $N$ 进行运算，并判断运算结果是否符合要求即可。

比如字符串 $M$ 为 $12345678987654321$ ，而我们枚举到的密码串长度是12，于是我们先取出数字 $123456789876$ 进行判断。判断结束后，再取出数字 $234567898765$ 继续判断。循环往复，如果12的长度不存在答案，那么就继续往下枚举密码串长度11，直到找到符合要求的数字串为止。

时间复杂度为枚举与运算的时间复杂度，枚举密码串长度次数为 $k = min (N, 12)$ ，判断密码串是否符合要求同样也需要约 $O (k)$ 的时间复杂度。其中， $N$ 为字符串 $M$ 的长度，需要遍历一遍字符串，因此时间复杂度为 $O(k^2N)$

类似题目推荐

代码

C++

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long longll N;
ll ans=-1;
int len;
char s[105];
char op;bool check(ll x,char op){if(op=='-') x-=N;else if(op=='*') x*=N;else if(op=='+') x+=N;int number = x%10;while(x){if(x%10!=number) return false;x/=10;}return true;
}int main(){scanf("%s",s+1);// 读入字符串 len=strlen(s+1);scanf("%lld",&N);// 读入密钥数字 scanf("%c",&op);// 读入运算符k// 滤去多余字符如'\n'等，保证运算符为+-* while(op!='+'&&op!='-'&&op!='*') scanf("%c",&op);// 最长12位，但是字符串可能不足12，取小 int m=min(len,12);ll mod,tmp;for(int i=m;i>=3;--i){mod=pow(10,i-1);tmp=0;for(int j=1;j<i;++j){tmp=tmp*10+s[j]-'0';}for(int j=i;j<=len;++j){tmp=tmp*10+s[j]-'0';//循环运算，每次取模去掉最高位，再*10 加上当前位为当前数字 if(check(tmp,op)){// 判断答案ans=max(ans,tmp);}tmp%=mod;}}printf("%lld",ans);return 0;
}

python

import mathN = 0
ans = -1
len = 0
s = ''
op = ''def check(x, op):global Nif op == '-':x -= Nelif op == '*':x *= Nelif op == '+':x += Nnumber = x % 10while x:if x % 10 != number:return Falsex //= 10return Trues = input()  # 读入字符串
len = len(s)
N = int(input())  # 读入密钥数字
op = input()  # 读入运算符
# 滤去多余字符如'\n'等，保证运算符为+-*
while op != '+' and op != '-' and op != '*':op = input()# 最长12位，但是字符串可能不足12，取小
m = min(len, 12)
mod = 0
tmp = 0
for i in range(m, 2, -1):mod = math.pow(10, i - 1)tmp = 0for j in range(1, i):tmp = tmp * 10 + int(s[j])for j in range(i, len + 1):tmp = tmp * 10 + int(s[j])  # 循环运算，每次取模去掉最高位，再*10加上当前位为当前数字if check(tmp, op):  # 判断答案ans = max(ans, tmp)tmp %= modprint(ans)

Java

import java.util.Scanner;public class Main {static long N;static long ans = -1;static int len;static char[] s;static char op;static boolean check(long x, char op) {if (op == '-') x -= N;else if (op == '*') x *= N;else if (op == '+') x += N;int number = (int)(x % 10);while (x != 0) {if (x % 10 != number) return false;x /= 10;}return true;}public static void main(String[] args) {Scanner input = new Scanner(System.in);s = input.next().toCharArray(); // 读入字符串len = s.length;N = input.nextLong(); // 读入密钥数字op = input.next().charAt(0); // 读入运算符// 滤去多余字符如'\n'等，保证运算符为+-*while (op != '+' && op != '-' && op != '*') op = input.next().charAt(0);// 最长12位，但是字符串可能不足12，取小int m = Math.min(len, 12);long mod, tmp;for (int i = m; i >= 3; i--) {mod = (long)Math.pow(10, i - 1);tmp = 0;for (int j = 1; j < i; j++) {tmp = tmp * 10 + (s[j] - '0');}for (int j = i; j <= len; j++) {tmp = tmp * 10 + (s[j] - '0'); // 循环运算，每次取模去掉最高位，再*10加上当前位为当前数字if (check(tmp, op)) { // 判断答案ans = Math.max(ans, tmp);}tmp %= mod;}}System.out.println(ans);}
}

Go

package mainimport ("fmt""math"
)var (N   int64 = 0ans int64 = -1len ints   stringop  byte
)func check(x int64, op byte) bool {if op == '-' {x -= N} else if op == '*' {x *= N} else if op == '+' {x += N}number := x % 10for x != 0 {if x%10 != number {return false}x /= 10}return true
}func main() {fmt.Scan(&s)            // 读入字符串len = len(s)fmt.Scan(&N)            // 读入密钥数字fmt.Scanf("%c", &op)    // 读入运算符// 滤去多余字符如'\n'等，保证运算符为+-*for op != '+' && op != '-' && op != '*' {fmt.Scanf("%c", &op)}// 最长12位，但是字符串可能不足12，取小m := int(math.Min(float64(len), 12))var mod, tmp int64for i := m; i >= 3; i-- {mod = int64(math.Pow10(i - 1))tmp = 0for j := 1; j < i; j++ {tmp = tmp*10 + int64(s[j]-'0')}for j := i; j <= len; j++ {tmp = tmp*10 + int64(s[j]-'0') // 循环运算，每次取模去掉最高位，再*10加上当前位为当前数字if check(tmp, op) {            // 判断答案ans = int64(math.Max(float64(ans), float64(tmp)))}tmp %= mod}}fmt.Println(ans)
}

Js

const readline = require('readline');function check(x, op) {if (op === '-') x -= N;else if (op === '*') x *= N;else if (op === '+') x += N;const number = x % 10;while (x !== 0) {if (x % 10 !== number) return false;x = Math.floor(x / 10);}return true;
}async function main() {const rl = readline.createInterface({input: process.stdin,output: process.stdout});let N = 0;let ans = -1;let len = 0;let s = '';let op = '';s = await new Promise(resolve => {rl.question('', resolve);}); // 读入字符串len = s.length;N = Number(await new Promise(resolve => {rl.question('', resolve);})); // 读入密钥数字op = await new Promise(resolve => {rl.question('', resolve);}); // 读入运算符// 滤去多余字符如'\n'等，保证运算符为+-*while (op !== '+' && op !== '-' && op !== '*') {op = await new Promise(resolve => {rl.question('', resolve);});}// 最长12位，但是字符串可能不足12，取小const m = Math.min(len, 12);let mod, tmp;for (let i = m; i >= 3; i--) {mod = Math.pow(10, i - 1);tmp = 0;for (let j = 1; j < i; j++) {tmp = tmp * 10 + parseInt(s[j]);}for (let j = i; j <= len; j++) {tmp = tmp * 10 + parseInt(s[j]); // 循环运算，每次取模去掉最高位，再*10加上当前位为当前数字if (check(tmp, op)) { // 判断答案ans = Math.max(ans, tmp);}tmp %= mod;}}console.log(ans);rl.close();
}main();