【春招笔试】2024-05-12-OPPO-三语言题解

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新OPPO近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

⌚️ 01.K小姐的密码生成

题目描述

K小姐在一家网络安全公司工作,最近她接到一个任务,要为公司的系统设计一套密码生成规则。

公司的系统有两套预置的字符串 和 ,每次生成密码时,都会从这两个字符串中挑选字符。具体来说,对于密码的每一位,可以从 和 相同位置的字符中任意选择一个。

现在,K小姐已经想好了理想的目标密码 ,她想知道能否通过上述规则生成出这个密码。

输入格式

第一行包含一个正整数 ,表示字符串 、 和 的长度。

第二行包含一个长度为 的字符串 。

第三行包含一个长度为 的字符串 。

第四行包含一个长度为 的字符串 。

输出格式

如果可以生成出目标密码 ,输出 Yes,否则输出 No。

样例输入

3
abc
bad
aac

样例输出

Yes

数据范围

题解

可以遍历目标密码 的每一位,检查它是否能够从 和 的对应位置取得。如果 的每一位都能取到,那么就可以生成出目标密码;否则,无法生成目标密码。

时间复杂度为 ,空间复杂度为 。

参考代码

• Python

n = int(input())
s = input()
t = input()
p = input()

for i in range(n):
    if p[i] != s[i] and p[i] != t[i]:
        print("No")
        exit()
        
print("Yes")

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        String t = sc.next();
        String p = sc.next();
        
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) != s.charAt(i) && p.charAt(i) != t.charAt(i)) {
                System.out.println("No");
                return;
            }
        }
        
        System.out.println("Yes");
    }
}

• Cpp

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

int main() {
    int n;
    string s, t, p;
    cin >> n >> s >> t >> p;
    
    for (int i = 0; i < n; i++) {
        if (p[i] != s[i] && p[i] != t[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

🖱 02.历练之路

题目描述

LYA 正在玩一款角色扮演游戏。在游戏中,他需要操控角色在 个关卡中战斗,每个关卡都有一个 boss。

游戏的战斗机制如下:

1. 每个回合 LYA 先手攻击 boss,然后 boss 会反击。
2. 如果 LYA 在该回合成功闪避,则不会受到 boss 的伤害。
3. LYA 造成的伤害为 ,其中 为基础攻击力, 为连击加成,而 为连击数。
4. 每次攻击后,LYA 的连击数 会加 ,但当 LYA 受到 boss 的攻击时,连击数会重置为 。

LYA 想知道,在通过这 个关卡后,他总共对 boss 们造成了多少伤害。

输入格式

第一行输入三个正整数 ,分别代表关卡数,LYA 的基础攻击力和连击加成。

第二行输入一个长度为 的字符串,字符串仅由 o 和 x 组成,其中 o 代表本回合闪避成功,x 代表本回合闪避失败。

输出格式

一个正整数,代表 LYA 造成的总伤害。

样例输入

3 5 2
oxo

样例输出

17

数据范围

题解

我们可以模拟整个战斗过程。用变量 记录当前的连击数,用变量 记录总伤害。

对于每一回合:

1. 先将 LYA 造成的伤害 累加到 上。
2. 如果本回合闪避失败(即字符为 x),则将连击数 重置为 ;否则,将连击数 加 。

最终,变量 的值即为 LYA 造成的总伤害。

时间复杂度 ,空间复杂度 。

参考代码

• Python

n, a, b = map(int, input().split())
s = input()

c = res = 0
for ch in s:
    res += a + b * c
    if ch == 'x':
        c = 0
    else:
        c += 1
        
print(res)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long a = sc.nextLong();
        long b = sc.nextLong();
        String s = sc.next();
        
        long c = 0, res = 0;
        for (int i = 0; i < n; i++) {
            res += a + c * b;
            if (s.charAt(i) == 'x') {
                c = 0;
            } else {
                c++;
            }
        }
        System.out.println(res);
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int n;
    long long a, b;
    string s;
    cin >> n >> a >> b >> s;
    
    long long c = 0, res = 0;
    for (char ch : s) {
        res += a + c * b;
        if (ch == 'x') {
            c = 0;
        } else {
            c++;
        }
    }
    cout << res << endl;
    
    return 0;
}

🎚 03.寻找神秘信号

问题描述

K小姐在一次偶然的机会中，获得了一串神秘的数字信号。这些信号隐藏着一个秘密，只有当选取的连续信号段中所有数字的乘积在二进制表示下末尾至少有 个零时，才能解锁。K小姐希望找到满足条件的最短信号段，以尽快揭开秘密。

输入格式

第一行包含两个正整数 和 ，分别表示信号的长度和乘积二进制表示末尾至少需要的零的个数。
第二行包含 个正整数，表示这串神秘的数字信号。

输出格式

输出一个整数，代表满足条件的最短信号段的长度。如果不存在这样的信号段，输出 。

样例输入

6 3
1 2 3 4 5 6

样例输出

3

数据范围

题解

为了找到满足条件的最短信号段，可以利用滑动窗口的方法。首先，将每个数字转换为其包含的 的因子个数，因为只有 的因子个数会影响乘积的二进制表示末尾零的个数。然后，通过滑动窗口来累加这些因子个数，直到累加和达到或超过 ，此时尝试缩小窗口以寻找最短的满足条件的信号段。

参考代码

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] signals = new int[n];
        for (int i = 0; i < n; i++) {
            int signal = scanner.nextInt();
            int count = 0;
            while (signal % 2 == 0) {
                signal >>= 1;
                count++;
            }
            signals[i] = count;
        }
        int left = 0, sum = 0, minLength = Integer.MAX_VALUE;
        for (int right = 0; right < n; right++) {
            sum += signals[right];
            while (sum >= k) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= signals[left++];
            }
        }
        System.out.println(minLength == Integer.MAX_VALUE ? -1 : minLength);
    }
}

• Python

n, k = map(int, input().split())
signals = list(map(int, input().split()))

for i in range(n):
    count = 0
    while signals[i] % 2 == 0:
        signals[i] //= 2
        count += 1
    signals[i] = count

left, sum, minLength = 0, 0, float('inf')
for right in range(n):
    sum += signals[right]
    while sum >= k:
        minLength = min(minLength, right - left + 1)
        sum -= signals[left]
        left += 1

print(minLength if minLength != float('inf') else -1)

• Cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> signals(n);
    for (int i = 0; i < n; ++i) {
        cin >> signals[i];
        int count = 0;
        while (signals[i] % 2 == 0) {
            signals[i] /= 2;
            count++;
        }
        signals[i] = count;
    }
    int left = 0, sum = 0, minLength = 1e9;
    for (int right = 0; right < n; ++right) {
        sum += signals[right];
        while (sum >= k) {
            minLength = min(minLength, right - left + 1);
            sum -= signals[left++];
        }
    }
    cout << (minLength == 1e9 ? -1 : minLength) << endl;
    return 0;
}