💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

✨ 01.LYA 的魔法方阵

问题描述

LYA 是一位魔法学徒，她掌握了一种神奇的魔法阵，可以快速计算 方阵的行列式的值。然而，LYA 的导师认为仅仅计算行列式的值还不够有趣，他希望 LYA 能够直接构造出行列式等于给定值 的 方阵。

现在，LYA 想要尝试改进她的魔法阵，使其能够满足导师的要求。你能帮助 LYA 完成这个任务吗？

输入格式

输入仅一行，包含一个正整数 ，表示目标行列式的值。

输出格式

输出一个 的方阵，使其行列式的值等于 。方阵中的元素必须是非负整数且不超过 。如果存在多个满足条件的方阵，输出任意一个即可。

样例输入

5

样例输出

1 1
1 6

数据范围

题解

本题可以通过枚举的方式来解决。我们可以枚举方阵中的四个元素 , , , ，使得 。由于元素的取值范围为 ，因此我们可以使用四重循环来枚举所有可能的组合。

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

参考代码

• Python

x = int(input())

for a in range(21):
    for b in range(21):
        for c in range(21):
            for d in range(21):
                if a * d - b * c == x:
                    print(a, b)
                    print(c, d)
                    exit(0)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();

        for (int a = 0; a <= 20; a++) {
            for (int b = 0; b <= 20; b++) {
                for (int c = 0; c <= 20; c++) {
                    for (int d = 0; d <= 20; d++) {
                        if (a * d - b * c == x) {
                            System.out.println(a + " " + b);
                            System.out.println(c + " " + d);
                            return;
                        }
                    }
                }
            }
        }
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int x;
    cin >> x;

    for (int a = 0; a <= 20; a++) {
        for (int b = 0; b <= 20; b++) {
            for (int c = 0; c <= 20; c++) {
                for (int d = 0; d <= 20; d++) {
                    if (a * d - b * c == x) {
                        cout << a << " " << b << endl;
                        cout << c << " " << d << endl;
                        return 0;
                    }
                }
            }
        }
    }

    return 0;
}

🌸 02.卢小姐的舞蹈连击

问题描述

卢小姐是一名热爱跳舞的女孩,她最喜欢的一款舞蹈游戏叫做"舞动青春"。

游戏中卢小姐可以在音乐的节奏下按照屏幕上的舞步提示进行跳舞。每跳对一个舞步就可以获得分数,而"连击"更是这个游戏的亮点:连续跳对舞步可以积攒"连击点",获得的分数为 ( 为基础得分, 为连击加分, 为连击次数)。

卢小姐每次连击成功,都会持续获得更高的分数。但是如果某个舞步跳错,虽然依然可以得到基础分,但是连击数会清零。

现在卢小姐想让你帮忙计算一局游戏中她的总得分。

输入格式

第一行输入三个正整数 ,分别代表本局游戏的总舞步数、基础得分和连击加分。()

第二行输入一个长度为 的字符串,仅包含字符 o 和 x,其中 o 表示这个舞步跳对,x 表示这个舞步跳错。

输出格式

输出一个正整数,表示卢小姐本局游戏的总得分。

样例输入

5 2 1
oxoox

样例输出

14

数据范围

题解

这道题可以用一个变量 来记录当前的连击次数,初始值为0。遍历输入的字符串,对于每一个字符:

• 如果是 o,说明这个舞步跳对,可以获得 的分数,并且连击次数 加1。
• 如果是 x,说明这个舞步跳错,只能获得基础分 ,并且连击次数 要重置为0。

遍历结束后,累加的分数就是总得分。

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

参考代码

• Python

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

score = 0
combo = 0

for step in steps:
    score += a + b * combo
    
    if step == 'o':
        combo += 1
    else:
        combo = 0

print(score)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        String steps = sc.next();
        
        long score = 0;
        int combo = 0;
        
        for (char step : steps.toCharArray()) {
            score += a + (long) b * combo;
            
            if (step == 'o') {
                combo++;
            } else {
                combo = 0;
            }
        }
        
        System.out.println(score);
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    
    string steps;
    cin >> steps;
    
    long long score = 0;
    int combo = 0;
    
    for (char step : steps) {
        score