2023.05.10-暑期实习-第二题-解密

0

wangxuehui LV 9 @ 8 months ago

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <climits>
typedef long long LL;

using namespace std;

bool isallsame(LL val){
    //先得到个位数；
    int ge=val%10;
    while (val) {
        int re=val%10;
        if (ge!=re) {
          return false;
        }
        val= val/10;
    }
    return true;
}

int main() {
    string m;
    LL n;
    cin >> m >> n;  
    n=n%9999999999;
    char s;
    cin>>s;
    int lens=m.size();
    LL val=0;
    LL res=INT_MIN;
    LL pre=INT_MIN;
    for (int i=3; i<=12; i++) {//找到长度为 3 到 12 位的密码串
        for (int j=0; j<=lens-i; j++) {
            string subnum=m.substr(j,i);
            LL x=stoll(subnum);
            if (s=='-') {
                val=x-n;
            }else if (s=='+') {
                val=x+n;
            }else if (s=='*') {
                val=x*n;
            }
            if (isallsame(val)) {
                if (val>pre) { //需要选择计算结果最大的一种作为真正的密码。
                     res=x;
                     pre=val;
                }
            }
        }
    }
    if (res==INT_MIN) {
        cout << -1 << endl;  
        return 0;
    }
    cout << res << endl; 
    return 0;
}

0

riesling LV 6 @ 8 months ago

#include<bits/stdc++.h>
#include <string>
using namespace std;
#define LL long long 
// M < 100 len , N <=  9999999999
bool isvalid(LL val) {
    int digit = val % 10;
    while (val) {
        int re = val % 10;
        if (digit == re) {
            val /= 10;
        } else {
            return false;
        }
    }
    return true;
}
vector<pair<LL, LL>> getMatch(string s, long long N, char op) {
    vector<pair<LL, LL>> res;
    int n = s.size(); // 枚举每个字符串
    int real_len = (n >= 12) ? 12 : n;
    for (int len = 12; len >= 3; len--) {
        for (int i = 0; i + len + 1 < s.size(); i++) {
            LL val = stoll(s.substr(i, len)); // stoi 的问题
            LL ori = val;
            if (op == '+') {
                val += N;
            } else if (op == '-') {
                val -= N;
            } else if (op == '*') {
                val *= N;
            }
            if (isvalid(val)) { // 
                res.push_back({val, ori});
            }
        }
    }
    return res;
}

int main() {
    string M; cin >> M;
    long long N; cin >> N;
    N %= 9999999999;
    char op;
    cin >> op;
    auto res = getMatch(M, N, op);
    LL max_val = 0;
    LL fi = 0;
    if (res.size() == 0) {
        cout << "-1" << endl;
        return 0;
    } 
    else {
        for (auto i: res) {
            if (i.first > max_val) {
                fi = i.second;
                max_val = i.first;
            }
        }
        cout << fi << endl;
        return 0;
    }
}

0

TaZi SU @ 9 months ago

题解思路

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

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

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

详细步骤

遍历子串：由于密码串的长度限制在 3 到 12 之间，因此我们可以枚举从 M 中提取不同长度的子串。以长度从 12 到 3 的顺序枚举，可以在找到符合要求的结果后提前结束遍历。
计算运算结果：
- 对每一个提取出的子串，根据运算符 k（加、减、乘），与密钥数字 N 进行计算，得到运算结果。
- 运算结果需要满足所有位数相同。为此，检查结果的各位数，判断其是否符合条件。
结果筛选：
- 如果运算结果的各位数相同且比当前最大值大，则更新最终结果。
- 若有多个符合条件的子串，则选择其中运算结果最大的子串。
终止条件：如果在当前长度的子串中找到满足要求的最大值，则直接输出结果。否则，继续尝试较短的子串，直到找到符合条件的结果。

复杂度分析

时间复杂度：对于字符串长度 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);
    }
}

示例解释

对于输入示例：

若 M = "6833023887793076998810418710", N = 2211, k = '-'：
- 符合条件的子串有 8877 和 9988。 9988 - 2211 = 7777 是最大结果。
若 M = "68846787793076946788418710", N = 4210, k = '+'：
- 符合条件的子串为 884678，884678 + 4210 = 888888 是最大结果。

3 solutions

题解思路

详细步骤

复杂度分析

代码实现

Python代码

C++代码

Java代码

示例解释

Information

Status

Development

Support