【秋招突围】2024届秋招笔试-科大讯飞笔试题-02-三语言题解(Java/Cpp/Python)

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

✨ 本系计划跟新各公司春秋招的笔试题

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注CSDN同名公主号领取，会在飞书进行同步的跟新。

🍄 01.A先生的餐厅评级

问题描述

A先生经营着一家餐厅,该餐厅共有 $n$ 个分店。每个分店的顾客满意度评分分别记为 $s_1,s_2,...,s_n$,分店编号依次为 $1,2,...,n$。

餐厅被评为优质餐厅的条件是满足以下三个条件之一:

1. 这 $n$ 个分店的顾客满意度评分的中位数不低于 $a$。中位数是将评分排序后处于最中间的数,当 $n$ 为偶数时,规定中位数为两个中间数的平均值(向下取整)。
2. 顾客满意度评分的平均值(取整后)不低于 $b$,即 $\lfloor \frac{{\sum }_{i=1}^n{s}_i}{n}\rfloor \ge b$。
3. 去除评分最高和最低的两个分店后,剩余分店的平均评分(取整后)不低于 $c$,即 $\lfloor \frac{{\sum }_{i=1}^n{s}_i-x-y}{n-2}\rfloor \ge c$。其中 $x$ 和 $y$ 分别为最高分和最低分。

只要满足以上三个条件中的任意一个,A先生的餐厅就可被评为优质餐厅。

输入格式

第一行输入一个正整数 $T(1\le T\le 1000)$,表示测试数据的组数。

对于每组测试数据:

• 第一行输入一个正整数 $n(3\le n\le 100)$,表示餐厅分店数量。
• 第二行输入 $n$ 个整数 $s_1,s_2,...,s_n(0\le s_i\le 100)$,表示每个分店的顾客满意度评分。
• 第三行输入三个整数 $a,b,c(0\le a,b,c\le 100)$,分别表示优质餐厅需要满足的三个评分标准。

输出格式

对于每组测试数据,如果餐厅可以被评为优质餐厅,则输出 Yes,否则输出 No。

样例输入

3
3
66 66 66
99 70 60
4
99 10 60 25
43 49 43
6
46 64 0 100 60 88
62 88 77

样例输出

Yes
No
Yes

数据范围

• $1\le T\le 1000$
• $3\le n\le 100$
• $0\le s_i\le 100$
• $0\le a,b,c\le 100$

题解

本题可以按照给定的三个条件依次进行判断。

1. 计算中位数:将顾客满意度评分排序,如果 $n$ 为奇数,中位数为 $s_{\lfloor \frac{n}{2}\rfloor }$;如果 $n$ 为偶数,中位数为 $\lfloor \frac{s_{\frac{n}{2}-1}+s_{\frac{n}{2}}}{2}\rfloor$。判断中位数是否不低于 $a$。

2. 计算平均值:求出所有分店评分的总和 ${\sum }_{i=1}^n{s}_i$,然后除以分店数量 $n$,取整后判断是否不低于 $b$。

3. 去除最高最低分:求出评分的最大值 $x$ 和最小值 $y$,将总和减去 $x$ 和 $y$,然后除以 $(n-2)$,取整后判断是否不低于 $c$。

如果以上三个条件中任意一个满足,则餐厅可以被评为优质餐厅。

时间复杂度:$O(T\times n\log n)$,其中排序的时间复杂度为 $O(n\log n)$。
空间复杂度:$O(n)$。

参考代码

• Java

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int numOfCases = scanner.nextInt();for (int i = 0; i < numOfCases; i++) {int numOfStudents = scanner.nextInt();int[] studentScores = new int[numOfStudents];for (int j = 0; j < numOfStudents; j++) {studentScores[j] = scanner.nextInt();}int thresholdA = scanner.nextInt();int thresholdB = scanner.nextInt();int thresholdC = scanner.nextInt();Arrays.sort(studentScores);int length = studentScores.length;int result = 0;if (((length & 1) == 1 && studentScores[length / 2] < thresholdA) || ((length & 1) == 0 && (studentScores[length / 2] + studentScores[length / 2 - 1]) / 2 < thresholdA)) {result++;}int sum = Arrays.stream(studentScores).sum();if (sum / length < thresholdB) {result++;}if ((sum - studentScores[0] - studentScores[length - 1]) / (length - 2) < thresholdC) {result++;}System.out.println(result < 3 ? "Yes" : "No");}scanner.close();}
}

02.LYA的农场探险

问题描述

LYA在她的农场里埋藏了许多宝藏，农场由 $n\times m$ 个方格组成。现在她想探索整个农场，要求从某个方格出发，经过每个方格恰好一次，最后回到出发点。

请你帮助 LYA设计一条探险路线，输出探险的起点坐标以及路线上每一步的方向。

输入格式

输入包含两个正整数 $n$ 和 $m$，分别表示农场的行数和列数，满足 $1\le n,m\le 1000$，且 $n$ 和 $m$ 不同时为 $1$。

输出格式

第一行输出两个正整数 $x$ 和 $y$，表示探险的起点坐标，其中 $x$ 表示行号，$y$ 表示列号，均从 $1$ 开始计数。

第二行输出一个长度为 $nm-1$ 的字符串，表示探险的路线，其中：

• W 表示向上走；
• S 表示向下走；
• A 表示向左走；
• D 表示向右走。

如果存在多条可行的探险路线，输出任意一条即可。

样例输入

3 3

样例输出

1 1
DDSSAAWW

数据范围

• $1\le n,m\le 1000$
• $n$ 和 $m$ 不同时为 $1$

题解

本题可以按照以下思路设计探险路线：

1. 从农场的左上角 $(1,1)$ 出发。
2. 在每一行中，从左向右遍历每个方格，到达最右侧后向下移动到下一行。
3. 在下一行中，从右向左遍历每个方格，到达最左侧后向下移动到再下一行。
4. 重复步骤 2 和步骤 3，直到遍历完所有方格。

根据上述思路，可以得到以下探险路线：

• 从 $(1,1)$ 出发，初始方向为向右。
• 对于每一行：
  • 如果是奇数行（行号为奇数），则向右走 $m-1$ 步。
  • 如果是偶数行（行号为偶数），则向左走 $m-1$ 步。
  • 如果还没到达最后一行，则向下走一步。

时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$。

参考代码

• Python

n, m = map(int, input().split())
print("1 1")path = []
for i in range(n):if i % 2 == 0:path.extend(['D'] * (m - 1))else:path.extend(['A'] * (m - 1))if i != n - 1:path.append('S')print(''.join(path))

• 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 m = sc.nextInt();System.out.println("1 1");StringBuilder path = new StringBuilder();for (int i = 0; i < n; i++) {if (i % 2 == 0) {path.append("D".repeat(m - 1));} else {path.append("A".repeat(m - 1));}if (i != n - 1) {path.append("S");}}System.out.println(path.toString());}
}

• Cpp

#include <iostream>
#include <string>using namespace std;int main() {int n, m;cin >> n >> m;cout << "1 1\n";string path;for (int i = 0; i < n; i++) {if (i % 2 == 0) {path += string(m - 1, 'D');} else {path += string(m - 1, 'A');}if (i != n - 1) {path += 'S';}}cout << path << '\n';return 0;
}

03.卢小姐的项链设计

问题描述

卢小姐是一位珠宝设计师，她打算设计一条新的项链。这条项链由若干珍珠串联而成，每颗珍珠都用一个小写字母表示。为了让项链更加独特，卢小姐希望通过剪断若干位置，将原项链分割成多条"完美项链"。

一条"完美项链"必须满足以下条件：

1. 长度不小于 $2$。
2. 项链的首尾字母相同。

现在给定原项链的珍珠排列，请帮助卢小姐计算，最多能将原项链分割成多少条完美项链。

输入格式

输入一个仅包含小写字母的字符串 $s$，表示原项链的珍珠排列。字符串长度不超过 $2\times 10^5$。

输出格式

如果无法分割出任何完美项链，且原项链本身也不是完美项链，则输出 $-1$。
否则，输出一个整数，表示最多能分割出的完美项链数量。

样例输入

arcaea

样例输出

1

数据范围

• $1\le |s|\le 2\times 10^5$

题解

本题可以使用动态规划来解决。设 $dp[i]$ 表示前 $i$ 个字符能够分割出的最多完美项链数量。那么对于第 $i$ 个字符，有两种情况可以转移到 $dp[i]$：

1. 如果 $s[i]=s[1]$，即第 $i$ 个字符与第一个字符相同，那么可以单独形成一条完美项链，此时 $dp[i]=1$。
2. 设 $pre[c]$ 表示字符 $c$ 上一次出现的下标，如果 $pre[s[i]]>0$，那么可以将 $pre[s[i]]$ 到 $i$ 的这一段作为一条完美项链，此时 $dp[i]=dp[pre[s[i]]]+1$。

最后，$dp[n]$ 即为答案，其中 $n$ 为字符串 $s$ 的长度。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

参考代码

• Python

s = input()
n = len(s)
dp = [-1] * (n + 1)pre = [-1] * 26
for i in range(2, n + 1):if s[i - 1] == s[0]:dp[i] = 1idx = ord(s[i - 1]) - ord('a')if pre[idx] > 0:dp[i] = max(dp[i], dp[pre[idx]] + 1)if dp[i - 1] > 0:pre[idx] = i - 1print(dp[n])

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.next();int n = s.length();int[] dp = new int[n + 1];Arrays.fill(dp, -1);int[] pre = new int[26];Arrays.fill(pre, -1);for (int i = 2; i <= n; i++) {if (s.charAt(i - 1) == s.charAt(0)) {dp[i] = 1;}int idx = s.charAt(i - 1) - 'a';if (pre[idx] > 0) {dp[i] = Math.max(dp[i], dp[pre[idx]] + 1);}if (dp[i - 1] > 0) {pre[idx] = i - 1;}}System.out.println(dp[n]);}
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;int main() {string s;cin >> s;int n = s.size();vector<int> dp(n + 1, -1);vector<int> pre(26, -1);for (int i = 2; i <= n; i++) {if (s[i - 1] == s[0]) {dp[i] = 1;}int idx = s[i - 1] - 'a';if (pre[idx] > 0) {dp[i] = max(dp[i], dp[pre[idx]] + 1);}if (dp[i - 1] > 0) {pre[idx] = i - 1;}}cout << dp[n] << endl;return 0;
}