【秋招笔试】24-07-27-OPPO-秋招笔试题(后端卷)
大家好这里是清隆学长 ，一枚热爱算法的程序员
ACM金牌团队️ | 多次AK大厂笔试 ｜ 编程一对一辅导
✨ 本系列打算持续跟新
秋招笔试题感谢大家的订阅➕ 和 喜欢 和 手里的小花花
✨ 笔试合集传送们 -> 春秋招笔试合集
01.二进制反转游戏
问题描述
K小姐有一个长度为 的正整数数组 。她现在想要选择其中一个数字进行"二进制翻转"操作，她想知道有多少种方式可以使得反转后的数组总和比原数组总和更大。
所谓"二进制翻转"，是指将一个数 的二进制表示翻转（例如 翻转后变为 ），然后去掉前导零得到翻转后的数。
例如，，翻转后得到 。
输入格式
第一行输入一个正整数 ()，表示数组 的长度。
第二行输入 个正整数 ()，表示数组 的元素。
输出格式
输出一个整数，表示可以使得反转后数组总和比原数组总和更大的操作方式数量。
样例输入
2
12 11
样例输出
1
数据范围
题解
我们可以枚举数组中的每个数，计算将其二进制翻转后的结果，然后比较翻转前后数组的总和大小。
设原数组总和为 ，当前枚举的数为 ，翻转后的数为 。如果 ，说明翻转 可以使得数组总和变大，答案加一。
时间复杂度 ，其中 为数组元素的最大值。
参考代码
- Python
# 读入数组长度 n
n = int(input())
# 读入数组 a
a = list(map(int, input().split()))
# 计算原数组总和
sum_a = sum(a)
ans = 0
# 枚举每个数
for x in a:
# 计算二进制翻转后的数
y = int(bin(x)[2:][::-1], 2)
# 如果翻转后数组总和更大，答案加一
if sum_a - x + y > sum_a:
ans += 1
# 输出答案
print(ans)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读入数组长度 n
int n = sc.nextInt();
// 读入数组 a
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 计算原数组总和
long sumA = 0;
for (int x : a) {
sumA += x;
}
int ans = 0;
// 枚举每个数
for (int x : a) {
// 计算二进制翻转后的数
int y = Integer.parseInt(new StringBuilder(Integer.toBinaryString(x)).reverse().toString(), 2);
// 如果翻转后数组总和更大，答案加一
if (sumA - x + y > sumA) {
ans++;
}
}
// 输出答案
System.out.println(ans);
}
}
- Cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 计算二进制翻转后的数
int reverseBits(int x) {
int y = 0;
while (x > 0) {
y = y * 2 + x % 2;
x /= 2;
}
return y;
}
int main() {
// 读入数组长度 n
int n;
cin >> n;
// 读入数组 a
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 计算原数组总和
long long sumA = 0;
for (int x : a) {
sumA += x;
}
int ans = 0;
// 枚举每个数
for (int x : a) {
// 计算二进制翻转后的数
int y = reverseBits(x);
// 如果翻转后数组总和更大，答案加一
if (sumA - x + y > sumA) {
ans++;
}
}
// 输出答案
cout << ans << endl;
return 0;
}
02.魔法方阵
问题描述
LYA 是一位魔法师，她有两个 的 01 方阵 和 。她希望用最少的魔法操作次数将 变成 。每次魔法操作可以选择 的一行或一列，将其中所有数字进行反转（0 变 1，1 变 0）。
LYA 想知道最少需要多少次魔法操作可以完成变换，如果无法做到，请告诉她。
输入格式
第一行输入一个整数 ，表示测试数据的组数。
对于每组测试数据：
第一行输入一个整数 ()，表示方阵的大小。
接下来 行，每行输入 个整数（0 或 1），表示方阵 。
再接下来 行，每行输入 个整数（0 或 1），表示方阵 。
输出格式
对于每组测试数据，输出一行一个整数，表示最少的魔法操作次数。如果无法完成变换，输出 。
样例输入
1
3
1 1 1
0 0 0
1 1 1
1 1 1
1 1 1
1 1 1
样例输出
1
数据范围
题解
由于 的范围很小（），我们可以直接枚举所有的翻转方案。对于每一行和每一列，都有翻转和不翻转两种选择，因此总共有 种翻转方案。
对于每种翻转方案，我们先将方阵 复制一份，然后根据翻转方案进行翻转操作，再判断翻转后的方阵是否与方阵 相同。如果相同，就更新答案为当前的翻转次数。
如果枚举完所有翻转方案后，还没有找到可行的方案，就说明无法通过翻转操作将 变成 ，此时输出 。
时间复杂度 ，空间复杂度 。
参考代码
- Python
# 读入测试数据组数
t = int(input())
for _ in range(t):
# 读入方阵大小 n
n = int(input())
# 读入方阵 A
a = [list(map(int, input().split())) for _ in range(n)]
# 读入方阵 B
b = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')
# 枚举所有的翻转方案
for mask in range(1 << (2 * n)):
# 复制方阵 A
c = [row[:] for row in a]
# 统计翻转次数
cnt = 0
# 根据翻转方案进行翻转操作
for i in range(n):
if mask >> i & 1:
cnt += 1
for j in range(n):
c[i][j] ^= 1
for j in range(n):
if mask >> (n + j) & 1:
cnt += 1
for i in range(n):
c[i][j] ^= 1
# 判断翻转后的方阵是否与 B 相同
if c == b:
ans = min(ans, cnt)
# 输出答案
print(ans if ans != float('inf') else -1)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读入测试数据组数
int t = sc.nextInt();
while (t-- > 0) {
// 读入方阵大小 n
int n = sc.nextInt();
// 读入方阵 A
int[][] a = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
// 读入方阵 B
int[][] b = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b[i][j] = sc.nextInt();
}
}
int ans = Integer.MAX_VALUE;
// 枚举所有的翻转方案
for (int mask = 0; mask < (1 << (2 * n)); mask++) {
// 复制方阵 A
int[][] c = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = a[i][j];
}
}
// 统计翻转次数
int cnt = 0;
// 根据翻转方案进行翻转操作
for (int i = 0; i < n; i++) {
if (((mask >> i) & 1) != 0) {
cnt++;
for (int j = 0; j < n; j++) {
c[i][j] ^= 1;
}
}
}
for (int j = 0; j < n; j++) {
if (((mask >> (n + j)) & 1) != 0) {
cnt++;
for (int i = 0; i < n; i++) {
c[i][j] ^= 1;
}
}
}
// 判断翻转后的方阵是否与 B 相同
boolean ok = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (c[i][j] != b[i][j]) {
ok = false;
break;
}
}
if (!ok) {
break;
}
}
if (ok) {
ans = Math.min(ans, cnt);
}
}
// 输出答案
System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
}
}
}
- Cpp
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
// 读入测试数据组数
int t;
cin >> t;
while (t--) {
// 读入方阵大小 n
int n;
cin >> n;
// 读入方阵 A
vector<vector<int>> a(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
// 读入方阵 B
vector<vector<int>> b(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> b[i][j];
}
}
int ans = INT_MAX;
// 枚举所有的翻转方案
for (int mask = 0; mask < (1 << (2 * n)); mask++) {
// 复制方阵 A
auto c = a;
// 统计翻转次数
int cnt = 0;
// 根据翻转方案进行翻转操作
for (int i = 0; i < n; i++) {
if (mask >> i & 1) {
cnt++;
for (int j = 0; j < n; j++) {
c[i][j] ^= 1;
}
}
}
for (int j = 0; j < n; j++) {
if (mask >> (n + j) & 1) {
cnt++;
for (int i = 0; i < n; i++) {
c[i][j] ^= 1;
}
}
}
// 判断翻转后的方阵是否与 B 相同
bool ok = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (c[i][j] != b[i][j]) {
ok = false;
break;
}
}
if (!ok) {
break;
}
}
if (ok) {
ans = min(ans, cnt);
}
}
// 输出答案
cout << (ans == INT_MAX ? -1 : ans) << endl;
}
return 0;
}
03.LYA的树林探险
问题描述
LYA是一位热爱探险的生物学家。她最近发现了一片神秘的树林，这片树林由 棵树组成，形成了一个奇特的树状结构。每两棵相邻的树之间都有一条小径，每条小径上都生长着一种稀有的植物，这些植物的研究价值用一个正整数 来表示。
LYA决定从1号树开始探索这片树林。她制定了以下探索规则：
- 当一条小径被经过一次后，其上的植物就会被采集完毕，不能再获得研究价值。
- 每棵树最多只能到达两次。
LYA想知道，按照这些规则，她最多能获得多少研究价值的植物样本。
输入格式
第一行输入一个整数 ，表示树林中树的数量。
接下来的 行，每行输入三个整数 、 和 ，表示 号树和 号树之间有一条研究价值为 的小径。
输出格式
输出一个整数，表示LYA最多能获得的植物样本研究价值总和。
样例输入
4
1 2 1
2 3 2
2 4 3
样例输出
6
数据范围
题解
这是一道典型的树形动态规划问题。我们可以使用 DFS 来遍历树，并在遍历过程中维护两个状态：
- ：从节点 出发，不返回节点 的最大研究价值。
- ：从节点 出发，最后返回节点 的最大研究价值。
对于每个节点，需要考虑以下情况：
- 不返回当前节点：选择一个子节点，走到该子节点后不返回。
- 返回当前节点：选择一个子节点，走到该子节点后返回，然后可能再选择另一个子节点继续探索。
在DFS过程中，我们需要维护两个最大值，分别对应于上述两种情况。最终，根节点的 就是我们要求的答案。
时间复杂度：O(n)，其中 n 是树中节点的数量。 空间复杂度：O(n)，用于存储动态规划数组和邻接表。
参考代码
- Python
# 导入必要的库
import sys
sys.setrecursionlimit(10**6) # 设置递归深度限制
def main():
# 读取输入
n = int(input())
graph = [[] for _ in range(n + 1)]
# 构建邻接表
for _ in range(n - 1):
u, v, w = map(int, input().split())
graph[u].append((v, w))
graph[v].append((u, w))
# 初始化动态规划数组
dp = [[0, 0] for _ in range(n + 1)]
# 深度优先搜索函数
def dfs(node, parent):
max_values = [0, 0] # 存储两个最大值
for child, weight in graph[node]:
if child == parent:
continue
dfs(child, node)
# 更新不返回的最大值
child_value = dp[child][0] + weight
if child_value >= max_values[1]:
max_values[0], max_values[1] = max_values[1], child_value
elif child_value > max_values[0]:
max_values[0] = child_value
# 更新当前节点的dp值
dp[node][0] = max_values[1]
dp[node][1] = max(dp[child][1] + weight + (max_values[0] if dp[child][0] + weight == max_values[1] else max_values[1])
for child, weight in graph[node] if child != parent)
# 从根节点开始DFS
dfs(1, 0)
# 输出结果
print(dp[1][1])
if __name__ == "__main__":
main()
- Java
import java.util.*;
import java.io.*;
public class Main {
static List<List<int[]>> graph;
static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 初始化图和动态规划数组
graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
dp = new long[n + 1][2];
// 读取输入并构建图
for (int i = 0; i < n - 1; i++) {
String[] line = br.readLine().split(" ");
int u = Integer.parseInt(line[0]);
int v = Integer.parseInt(line[1]);
int w = Integer.parseInt(line[2]);
graph.get(u).add(new int[]{v, w});
graph.get(v).add(new int[]{u, w});
}
// 从根节点开始DFS
dfs(1, 0);
// 输出结果
System.out.println(dp[1][1]);
}
// 深度优先搜索函数
static void dfs(int node, int parent) {
long[] maxValues = new long[2]; // 存储两个最大值
for (int[] edge : graph.get(node)) {
int child = edge[0], weight = edge[1];
if (child == parent) continue;
dfs(child, node);
// 更新不返回的最大值
long childValue = dp[child][0] + weight;
if (childValue >= maxValues[1]) {
maxValues[0] = maxValues[1];
maxValues[1] = childValue;
} else if (childValue > maxValues[0]) {
maxValues[0] = childValue;
}
}
// 更新当前节点的dp值
dp[node][0] = maxValues[1];
for (int[] edge : graph.get(node)) {
int child = edge[0], weight = edge[1];
if (child == parent) continue;
dp[node][1] = Math.max(dp[node][1],
dp[child][1] + weight + (dp[child][0] + weight == maxValues[1] ? maxValues[0] : maxValues[1]));
}
}
}
- Cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义边的结构
struct Edge {
int to, weight;
};
// 全局变量
vector<vector<Edge>> graph;
vector<vector<long long>> dp;
// 深度优先搜索函数
void dfs(int node, int parent) {
vector<long long> maxValues(2, 0); // 存储两个最大值
for (const auto& edge : graph[node]) {
int child = edge.to;
int weight = edge.weight;
if (child == parent) continue;
dfs(child, node);
// 更新不返回的最大值
long long childValue = dp[child][0] + weight;
if (childValue >= maxValues[1]) {
maxValues[0] = maxValues[1];
maxValues[1] = childValue;
} else if (childValue > maxValues[0]) {
maxValues[0] = childValue;
}
}
// 更新当前节点的dp值
dp[node][0] = maxValues[1];
for (const auto& edge : graph[node]) {
int child = edge.to;
int weight = edge.weight;
if (child == parent) continue;
dp[node][1] = max(dp[node][1],
dp[child][1] + weight + (dp[child][0] + weight == maxValues[1] ? maxValues[0] : maxValues[1]));
}
}
int main() {
int n;
cin >> n;
// 初始化图和动态规划数组
graph.resize(n + 1);
dp.assign(n + 1, vector<long long>(2, 0));
// 读取输入并构建图
for (int i = 0; i < n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
// 从根节点开始DFS
dfs(1, 0);
// 输出结果
cout << dp[1][1] << endl;
return 0;
}
类似资料：