【携程笔试题汇总】2024-03-28-携程春招笔试题-三语言题解(CPP/Python/Java)

本文主要是介绍【携程笔试题汇总】2024-03-28-携程春招笔试题-三语言题解(CPP/Python/Java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

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

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

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

01.K小姐的回文游戏

问题描述

K小姐想玩一个有趣的回文游戏。给定一个正整数 $n$，她希望你能输出一个由 $n$ 个 “you” 组成的字符串，其中第一个 “you” 正序输出，第二个倒序输出，第三个再正序，以此类推。你能帮帮她吗？

输入格式

输入只有一行，包含一个正整数 $n$，表示需要输出的 “you” 的个数。

输出格式

输出一个字符串，表示由 $n$ 个 “you” 组成的字符串，奇数位置的 “you” 正序输出，偶数位置的 “you” 倒序输出。

样例输入

5

样例输出

youuoyyouuoyyou

数据范围

$1\le n\le 10^5$

题解

这是一个简单的字符串构造问题。我们可以先定义两个字符串 “you” 和 “uoy”，然后根据 $n$ 的奇偶性，交替输出这两个字符串即可。

具体步骤如下：

1. 定义两个字符串 $s_1$ 和 $s_2$，分别表示正序的 “you” 和倒序的 “uoy”。
2. 循环 $n$ 次，如果当前循环变量 $i$ 为偶数，就输出 $s_1$，否则输出 $s_2$。
3. 最后输出构造好的字符串即可。

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

参考代码

• Python

s1 = "you"
s2 = "uoy"
n = int(input())
res = ""
for i in range(n):if i % 2 == 0:res += s1else:res += s2
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();String s1 = "you", s2 = "uoy";StringBuilder res = new StringBuilder();for (int i = 0; i < n; i++) {if (i % 2 == 0) {res.append(s1);} else {res.append(s2);}}System.out.println(res);}
}

• Cpp

#include <iostream>
using namespace std;int main() {int n;cin >> n;string s1 = "you", s2 = "uoy", res = "";for (int i = 0; i < n; i++) {if (i % 2 == 0) {res += s1;} else {res += s2;}}cout << res << endl;return 0;
}

02.K小姐的花园修剪

问题描述

K小姐有一个 $n\times m$ 的花园，每个位置上都种植了一株植物。然而，有些植物长得太茂盛了，需要修剪。K小姐可以选择一个 $1\times 2$ 的区域（即连续的两株植物），将它们修剪整齐。现在，K小姐想知道，最少需要多少次修剪，才能让整个花园看起来整齐有序呢？

花园中的每一株植物可以用 0 或 1 来表示，0 表示植物长得刚刚好，不需要修剪，1 表示植物长得太茂盛，需要修剪。

输入格式

第一行包含两个正整数 $n$ 和 $m$，表示花园的行数和列数，中间用空格隔开。

接下来 $n$ 行，每行包含 $m$ 个字符，表示花园中植物的状态，0 表示不需要修剪，1 表示需要修剪。

输出格式

输出一个整数，表示最少需要的修剪次数。

样例输入

2 4
1010
1000

样例输出

4

数据范围

$2\le n,m\le 1000$

题解

这道题可以用贪心的思路来解决。我们可以遍历整个花园，每次找到一个需要修剪的植物，然后将它和它右边的一株植物一起修剪（如果右边还有植物的话）。这样，我们可以保证每次修剪都是最优的选择，因为如果我们选择修剪一株不需要修剪的植物，那么总的修剪次数只会更多。

具体实现时，我们可以用一个双重循环来遍历花园，每次找到一个为 1 的位置，就将它修剪为 0，并且将它右边的位置也修剪为 0（如果右边的位置还在花园内），同时将修剪次数加 1。最后输出总的修剪次数即可。

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

参考代码

• Python

n, m = map(int, input().split())
garden = [input() for _ in range(n)]cnt = 0
for i in range(n):for j in range(m):if garden[i][j] == '1':cnt += 1if j + 1 < m:garden[i] = garden[i][:j+1] + '0' + garden[i][j+2:]else:garden[i] = garden[i][:j] + '0'print(cnt)

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();char[][] garden = new char[n][m];for (int i = 0; i < n; i++) {garden[i] = sc.next().toCharArray();}int cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (garden[i][j] == '1') {cnt++;if (j + 1 < m) {garden[i][j + 1] = '0';}}}}System.out.println(cnt);}
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;int main() {int n, m;cin >> n >> m;vector<string> garden(n);for (int i = 0; i < n; i++) {cin >> garden[i];}int cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (garden[i][j] == '1') {cnt++;if (j + 1 < m) {garden[i][j + 1] = '0';}}}}cout << cnt << endl;return 0;
}

03.K小姐的农场优化问题

问题描述

K小姐拥有一个农场，农场中种植了一排果树，共有 $n$ 棵。每棵果树都有一个对应的收益值 $a_i$，可正可负。

现在，K小姐最多可以进行一次优化操作：选择一个由偶数棵果树组成的连续区间，将这个区间内所有果树的收益都减半。

请你帮助K小姐进行最佳决策，使得优化后整个果园的总收益最大。

输入格式

第一行包含一个正整数 $n$，表示果树的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$，分别表示每棵果树的收益值。

输出格式

输出一个整数，表示优化后果园的最大总收益。

样例输入

5
8 -4 2 -6 -5

样例输出

-1

数据范围

• $1\le n\le 10^5$
• $-10^9\le a_i\le 10^9$

题解

本题可以使用区间求和的思想来解决。我们可以枚举每一个由偶数棵果树组成的连续区间，计算该区间内果树收益的总和。如果该区间收益总和小于 $0$，那么我们就可以考虑将该区间内所有果树的收益都减半，这样可以提高整个果园的总收益。

具体步骤如下：

1. 初始化答案为原始果园的总收益。
2. 从左到右遍历每棵果树，找到每一个由偶数棵果树组成的连续区间。
3. 对于每个偶数棵果树组成的连续区间，计算该区间内果树收益的总和。
4. 如果该区间收益总和小于 $0$，则尝试将该区间内所有果树的收益都减半，更新答案为减半后的果园总收益与当前答案的较大值。
5. 继续遍历下一个偶数棵果树组成的连续区间，重复步骤 3-4。
6. 返回最终得到的最大总收益即为答案。

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

参考代码

• Python

def maxProfit(n, profits):total = sum(profits)left, right = 0, 0ans = totalwhile left < n:while left < n and profits[left] % 2 != 0:left += 1if left < n:right = leftwhile right < n and profits[right] % 2 == 0:right += 1currSum = 0while left < right:currSum += profits[left]if currSum < 0:ans = max(ans, total - currSum // 2)else:currSum = 0left += 1return ansn = int(input())
profits = list(map(int, input().split()))
print(maxProfit(n, profits))

• Java

import java.util.Scanner;public class Solution {public static int maxProfit(int n, int[] profits) {int total = 0;for (int profit : profits) {total += profit;}int left = 0, right = 0;int ans = total;while (left < n) {while (left < n && profits[left] % 2 != 0) {left++;}if (left < n) {right = left;while (right < n && profits[right] % 2 == 0) {right++;}int currSum = 0;while (left < right) {currSum += profits[left];if (currSum < 0) {ans = Math.max(ans, total - currSum / 2);} else {currSum = 0;}left++;}}}return ans;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] profits = new int[n];for (int i = 0; i < n; i++) {profits[i] = scanner.nextInt();}System.out.println(maxProfit(n, profits));}
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;int maxProfit(int n, const vector<int>& profits) {int total = 0;for (int profit : profits) {total += profit;}int left = 0, right = 0;int ans = total;while (left < n) {while (left < n && profits[left] % 2 != 0) {left++;}if (left < n) {right = left;while (right < n && profits[right] % 2 == 0) {right++;}int currSum = 0;while (left < right) {currSum += profits[left];if (currSum < 0) {ans = max(ans, total - currSum / 2);} else {currSum = 0;}left++;}}}return ans;
}int main() {int n;cin >> n;vector<int> profits(n);for (int i = 0; i < n; i++) {cin >> profits[i];}cout << maxProfit(n, profits) << endl;return 0;
}

04.K小姐的蛋糕订单

问题描述

K小姐是一位蛋糕店的老板，她最近收到了 $n$ 个蛋糕订单。每个订单需要制作一定数量的蛋糕，这些数量分别记录在数组 $a$ 中。由于每个蛋糕都有多种装饰方式，K小姐想知道，对于每个订单，有多少种不同的装饰方式。为了方便计算，她希望你能帮她求出所有订单装饰方式数量的乘积。但是这个乘积可能会非常大，所以请对 $10^9+7$ 取模后再输出答案。

输入格式

第一行输入一个正整数 $n$，表示订单的数量。

第二行输入 $n$ 个正整数 $a_1,a_2,\dots ,a_n$，表示每个订单需要制作的蛋糕数量，数与数之间用空格隔开。

输出格式

输出一个整数，表示所有订单装饰方式数量的乘积对 $10^9+7$ 取模后的结果。

样例输入

3
1 2 3

样例输出

12

数据范围

$1\le n\le 2\times 10^5$
$1\le a_i\le 10^6$

题解

本题可以使用数论中的莫比乌斯反演和欧拉筛法来解决。

首先，我们可以知道，对于一个数 $x$，它的阶乘 $x!$ 中质因子 $p$ 的次数为 $\lfloor \frac{x}{p}\rfloor +\lfloor \frac{x}{p^2}\rfloor +\lfloor \frac{x}{p^3}\rfloor +\cdots$。

假设数组 $a$ 中所有数的乘积为 $S$，那么 $S$ 的因子个数就等于 $S$ 中每个质因子的次数加 $1$ 的乘积。而 $S$ 中每个质因子 $p$ 的次数等于 ${\sum }_{i=1}^n(\lfloor \frac{a_i}{p}\rfloor +\lfloor \frac{a_i}{p^2}\rfloor +\lfloor \frac{a_i}{p^3}\rfloor +\cdots )$。

我们可以使用莫比乌斯反演来计算每个质因子的次数。设 $f(n)={\sum }_{i=1}^n\lfloor \frac{a_i}{n}\rfloor$，那么 $S$ 中质因子 $p$ 的次数就等于 ${\sum }_{i=1}^{\infty }f(p^i)$。根据莫比乌斯反演，$f(n)={\sum }_{d|n}\mu (d)g(\frac{n}{d})$，其中 $g(n)={\sum }_{i=1}^n[a_i=n]$，$\mu$ 为莫比乌斯函数。

因此，我们可以先用欧拉筛法预处理出每个数的莫比乌斯函数值，然后计算出 $g$ 数组，再利用莫比乌斯反演计算出每个质因子的次数，最后把所有质因子的次数加 $1$ 后相乘即可得到答案。

时间复杂度为 $O(n+{\sum }_{i=1}^n{a}_i)$，空间复杂度为 $O(n+\max (a_i))$。

参考代码

• Cpp

#include <iostream>
#include <vector>
using namespace std;const int MOD = 1e9 + 7;
const int N = 1e6 + 5;int mu[N];
vector<int> prime;
bool vis[N];
int f[N];
int g[N];void init() {mu[1] = 1;for (int i = 2; i < N; i++) {if (!vis[i]) {prime.push_back(i);mu[i] = -1;}for (int p : prime) {if (i * p >= N) {break;}vis[i * p] = true;if (i % p == 0) {mu[i * p] = 0;break;}mu[i * p] = -mu[i];}}
}void solve() {int n;cin >> n;for (int i = 0; i < n; i++) {int x;cin >> x;g[x]++;}for (int i = 1; i < N; i++) {for (int j = i; j < N; j += i) {f[i] += g[j];}}long long res = 1;for (int i = 2; i < N; i++) {if (mu[i]) {long long cnt = 0;for (int j = i; j < N; j += i) {cnt += 1LL * mu[j / i] * f[j];}res = res * (cnt + 1) % MOD;}}cout << res << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);init();solve();return 0;
}

• Java

import java.io.*;
import java.util.*;public class Main {static final int MOD = (int)1e9 + 7;static final int N = (int)1e6 + 5;static int[] mu = new int[N];static List<Integer> prime = new ArrayList<>();static boolean[] vis = new boolean[N];static int[] f = new int[N];static int[] g = new int[N];static void init() {mu[1] = 1;for (int i = 2; i < N; i++) {if (!vis[i]) {prime.add(i);mu[i] = -1;}for (int p : prime) {if (i * p >= N) {break;}vis[i * p] = true;if (i % p == 0) {mu[i * p] = 0;break;}mu[i * p] = -mu[i];}}}static void solve() throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());String[] s = br.readLine().split(" ");for (String x : s) {g[Integer.parseInt(x)]++;}for (int i = 1; i < N; i++) {for (int j = i; j < N; j += i) {f[i] += g[j];}}long res = 1;for (int i = 2; i < N; i++) {if (mu[i] != 0) {long cnt = 0;for (int j = i; j < N; j += i) {cnt += (long)mu[j / i] * f[j];}res = res * (cnt + 1) % MOD;}}System.out.println(res);}public static void main(String[] args) throws IOException {init();solve();}
}

• Python

MOD = 10 ** 9 + 7
N = 10 ** 6 + 5mu = [0] * N
prime = []
vis = [False] * N
f = [0] * N
g = [0] * Ndef init():mu[1] = 1for i in range(2, N):if not vis[i]:prime.append(i)mu[i] = -1for p in prime:if i * p >= N:breakvis[i * p] = Trueif i % p == 0:mu[i * p] = 0breakmu[i * p] = -mu[i]def solve():n = int(input())a = list(map(int, input().split()))for x in a:g[x] += 1for i in range(1, N):for j in range(i, N, i):f[i] += g[j]res = 1for i in range(2, N):if mu[i]:cnt = 0for j in range(i, N, i):cnt += mu[j // i] * f[j]res = res * (cnt + 1) % MODprint(res)init()
solve()

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取～

这篇关于【携程笔试题汇总】2024-03-28-携程春招笔试题-三语言题解(CPP/Python/Java)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---