深圳网站建设高端,济南网站建设是什么,北京的互联网公司,做网站卖东西为了更好的阅读体检#xff0c;可以查看我的算法学习博客
在线评测链接:P1307
题目内容
在全球恐怖主义危机下#xff0c;一组间谍团队接收到了来自地下工作者的一串神秘代码。这组代码可以帮助他们访问恐怖分子的服务器#xff0c;但是他们需要先解密代码才能使用它。代…为了更好的阅读体检可以查看我的算法学习博客
在线评测链接:P1307
题目内容
在全球恐怖主义危机下一组间谍团队接收到了来自地下工作者的一串神秘代码。这组代码可以帮助他们访问恐怖分子的服务器但是他们需要先解密代码才能使用它。代码是由数字 0 0 0 - 9 9 9 组成的字符串 M M M而解密过程需要一个秘钥数字 N N N 和一个运算符 k k k (加减乘中的一个)。
解密过程分为三个步骤
第一步团队成员需要使用秘钥数字 N N N 对 M M M 进行一系列 k k k 运算并尝试截取其中的一段数字 x x x。如果 x x x 和 N N N 的运算结果是一个所有位数相同的数字那么这段数字就有可能是真正的密码。例如如果 x x x 为 111 111 111 N N N 为 2 2 2 k k k 为乘法那么计算结果是 111 × 2 222 111 \times 2 222 111×2222满足条件因此 111 111 111 就是所寻找的目标密码串之一。
第二步如果存在多种满足第一点条件的情况那么团队成员需要选择计算结果最大的一种作为真正的密码。
第三步团队成员们需要在 M M M M M M的长度不超过100 中找到长度为 3 3 3 到 12 12 12 位的密码串并尝试使用秘钥数字 N N N 和运算符 k k k k k k 为 或 − - − 或 ∗ * ∗的一种进行解密。由于秘钥数字 N N N 可能非常大因此需要确保 N N N 不大于 9999999999 9999999999 9999999999。另外在乘法场景下团队成员们约定乘数最大为 3 3 3 位数以避免数据过于庞大。 如果没有找到符合条件的密码串则输出 − 1 -1 −1表示密码串不存在。
输入描述
输入第一行为加密后的字符串 M M M
输入第二行为密钥数字 N N N
输入第三行为运算符 k k k
输出
满足计算结果所有位数相同且计算结果最大的值。
样例1
输入
6833023887793076998810418710
2211
-输出
9988解释通过计算 8877 8877 8877 - 2211 2211 2211 6666 6666 6666 而 9988 9988 9988 - 2211 2211 2211 7777 7777 7777因为 7777 7777 7777 6666 6666 6666则目标密码串为 9988 9988 9988。
样例2
输入
68846787793076946788418710
4210输出
884678解释:通过计算符合条件有两个 884678 884678 884678 4210 4210 4210 888888 888888 888888 4678 4678 4678 4210 4210 4210 8888 8888 8888。则目标密码串为 884678 884678 884678。
样例3
输入
139804444677899222
2
*输出
4444解释:作为乘法场景乘数最大值为 3 3 3 位数本用例乘数为 2 2 2 。按要求 4444 4444 4444 * 2 2 2 8888 8888 8888 222 222 222 * 2 2 2 444 444 444均符合基本条件从中选择结果最大值则目标密码串是 4444 4444 4444。
思路模拟枚举
我们现在有一串数字字符串 M M M 同时还有另一串数字字符串 N N N 以及一个运算符 k ∈ { ′ ′ , ′ − ′ , ′ ∗ ′ } k\in\left\{,-,*\right\} k∈{′′,′−′,′∗′}我们需要找到 M M M 中是否有一串数字(长度为3-12)组成的整数该整数与 N N N 组成的整数进行字符 k k k 代表的运算后能使得运算结果的所有数位都是同一个数字比如6666。
和该日华为第一题一样直接按照题意模拟即可。
由于规定密码串的长度为3~12位且要求计算结果最大。因此我们可以从大到小枚举密码串的长度也即我们从数字字符串 M M M 中取出的连续数字字符的个数。用这些数字字符构成一个整数后与数字串 N N N 进行运算并判断运算结果是否符合要求即可。
比如字符串 M M M 为 12345678987654321 12345678987654321 12345678987654321而我们枚举到的密码串长度是12于是我们先取出数字 123456789876 123456789876 123456789876 进行判断。判断结束后再取出数字 234567898765 234567898765 234567898765 继续判断。循环往复如果12的长度不存在答案那么就继续往下枚举密码串长度11直到找到符合要求的数字串为止。
时间复杂度为枚举与运算的时间复杂度枚举密码串长度次数为 k m i n ( N , 12 ) kmin(N,12) kmin(N,12)判断密码串是否符合要求同样也需要约 O ( k ) O(k) O(k)的时间复杂度。其中 N N N 为字符串 M M M 的长度需要遍历一遍字符串因此时间复杂度为 O ( k 2 N ) O(k^2N) O(k2N)
类似题目推荐
代码
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) xN;int number x%10;while(x){if(x%10!number) return false;x/10;}return true;
}int main(){scanf(%s,s1);// 读入字符串 lenstrlen(s1);scanf(%lld,N);// 读入密钥数字 scanf(%c,op);// 读入运算符k// 滤去多余字符如\n等保证运算符为-* while(op!op!-op!*) scanf(%c,op);// 最长12位但是字符串可能不足12取小 int mmin(len,12);ll mod,tmp;for(int im;i3;--i){modpow(10,i-1);tmp0;for(int j1;ji;j){tmptmp*10s[j]-0;}for(int ji;jlen;j){tmptmp*10s[j]-0;//循环运算每次取模去掉最高位再*10 加上当前位为当前数字 if(check(tmp,op)){// 判断答案ansmax(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 (fmtmath
)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();
题目内容均收集自互联网如如若此项内容侵犯了原著者的合法权益可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除。
