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

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

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

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

🎀 01.K小姐的快速库存管理系统

问题描述

K小姐经营着一家小商店,最近她想开发一个快速库存管理系统。商店中有 $n$ 种商品,每种商品的初始数量记录在数组 $a$ 中。

接下来的 $k$ 天中,每天都会有一些商品的数量发生变化。第 $i$ 天会有一条形如 $(u,v)$ 的操作,表示将第 $u$ 种商品的数量变为 $v$。

为了实时监控库存状况,K小姐希望在每次操作后快速得到当前所有商品数量的总和。你能帮助她完成这个库存管理系统吗?

输入格式

第一行包含两个正整数 $n$ 和 $k$,表示商品种类数和操作天数。

第二行包含 $n$ 个正整数,第 $i$ 个数表示初始时第 $i$ 种商品的数量 $a_i$。

接下来 $k$ 行,每行包含两个正整数 $u$ 和 $v$,表示第 $u$ 种商品的数量变为 $v$。

输出格式

输出共 $k$ 行,每行一个整数,表示每次操作后所有商品数量的总和。

样例输入

5 4
1 2 3 4 5
1 2
3 2
4 2
5 2

样例输出

16
15
13
10

数据范围

• $3\le n\le 10^6$
• $1\le k\le 10^6$
• $1\le a_i\le 10^9$
• $1\le u\le n$
• $1\le v\le 10^9$

题解

本题可以使用前缀和的思想来解决。我们可以先预处理出初始时所有商品数量的总和 $sum$,然后在每次操作时,先将 $sum$ 减去被修改商品的原数量,再加上修改后的数量,即可得到操作后的商品总数量。

具体步骤如下:

1. 读入商品种类数 $n$ 和操作天数 $k$。

2. 读入初始商品数量数组 $a$,并计算初始商品总数量 $sum$。

3. 对于每次操作 $(u,v)$:

   • 将 $sum$ 减去第 $u$ 种商品的原数量 $a[u]$。
   • 将第 $u$ 种商品的数量修改为 $v$,即 $a[u]=v$。
   • 将 $sum$ 加上修改后的数量 $a[u]$。
   • 输出当前的商品总数量 $sum$。

时间复杂度为 $O(n+k)$,空间复杂度为 $O(n)$。

参考代码

• Python

n, k = map(int, input().split())
a = list(map(int, input().split()))
sum = 0
for i in range(n):sum += a[i]for i in range(k):u, v = map(int, input().split())u -= 1sum -= a[u]a[u] = vsum += a[u]print(sum)

• 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 k = sc.nextInt();long[] a = new long[n];long sum = 0;for (int i = 0; i < n; i++) {a[i] = sc.nextLong();sum += a[i];}for (int i = 0; i < k; i++) {int u = sc.nextInt() - 1;long v = sc.nextLong();sum -= a[u];a[u] = v;sum += a[u];System.out.println(sum);}}
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;vector<long long> a(n);long long sum = 0;for (int i = 0; i < n; i++) {cin >> a[i];sum += a[i];}for (int i = 0; i < k; i++) {int u;long long v;cin >> u >> v;u--;sum -= a[u];a[u] = v;sum += a[u];cout << sum << "\n";}return 0;
}

📝 02.LYA的圆形喷水器

问题描述

LYA在他的花园中安装了一个矩形喷水器，喷水器的边分别与花园的长和宽平行。为了确保花园的每个角落都能被浇灌到，LYA决定在花园中的某个位置 $P(x,y)$ 安装一个圆形喷水器，使其能够完全覆盖矩形喷水器所在的区域。

给定矩形喷水器的对角线坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，以及圆形喷水器的安装位置 $P(x,y)$，请你计算圆形喷水器的最小面积。

输入格式

第一行包含四个实数 $x_1$、$y_1$、$x_2$、$y_2$，分别表示矩形喷水器对角线上两个点的坐标。

第二行包含两个实数 $x$、$y$，表示圆形喷水器的安装位置坐标。

输入坐标的绝对值均小于 $10^5$。

输出格式

输出一个实数 $S$，表示覆盖矩形喷水器所需的最小圆形喷水器面积。如果答案的绝对或相对误差不超过 $10^{-6}$，则视为正确。

样例输入

1 1 2 2
0 0

样例输出

25.1327412287

数据范围

输入坐标的绝对值均小于 $10^5$。

题解

本题可以通过以下步骤求解：

1. 根据矩形喷水器的对角线坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，计算出矩形喷水器的另外两个顶点坐标 $(x_3,y_3)$ 和 $(x_4,y_4)$。
2. 计算圆形喷水器中心点 $P(x,y)$ 到矩形喷水器四个顶点的距离，取其中的最大值作为圆形喷水器的半径 $r$。
3. 根据公式 $S=\pi r^2$ 计算圆形喷水器的面积。

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

参考代码

• Python

from math import pix1, y1, x2, y2 = map(float, input().split())
x, y = map(float, input().split())x3, y3 = x1, y2
x4, y4 = x2, y1r = max((x1 - x) ** 2 + (y1 - y) ** 2,(x2 - x) ** 2 + (y2 - y) ** 2,(x3 - x) ** 2 + (y3 - y) ** 2,(x4 - x) ** 2 + (y4 - y) ** 2
) ** 0.5area = pi * r ** 2
print(f"{area:.10f}")

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);double x1 = sc.nextDouble(), y1 = sc.nextDouble();double x2 = sc.nextDouble(), y2 = sc.nextDouble();double x = sc.nextDouble(), y = sc.nextDouble();double x3 = x1, y3 = y2;double x4 = x2, y4 = y1;double r = Math.max(Math.max(Math.pow(x1 - x, 2) + Math.pow(y1 - y, 2),Math.pow(x2 - x, 2) + Math.pow(y2 - y, 2)),Math.max(Math.pow(x3 - x, 2) + Math.pow(y3 - y, 2),Math.pow(x4 - x, 2) + Math.pow(y4 - y, 2)));double area = Math.PI * r;System.out.printf("%.10f", area);}
}

• Cpp

#include <iostream>
#include <cmath>
#include <algorithm>using namespace std;int main() {double x1, y1, x2, y2, x, y;cin >> x1 >> y1 >> x2 >> y2 >> x >> y;double x3 = x1, y3 = y2;double x4 = x2, y4 = y1;double r = max(max(pow(x1 - x, 2) + pow(y1 - y, 2),pow(x2 - x, 2) + pow(y2 - y, 2)),max(pow(x3 - x, 2) + pow(y3 - y, 2),pow(x4 - x, 2) + pow(y4 - y, 2)));double area = M_PI * r;printf("%.10f\n", area);return 0;
}

💡 03.最短K0子串

问题描述

LYA是一名软件工程师,她正在研究一种特殊的字符串,称为K0串。一个字符串如果它的所有字符的ASCII码值乘积转换为二进制后,末尾至少有 $k$ 个连续的0,则称该字符串为K0串。

现在给定一个长度为 $n$ 的字符串 $s$,请你帮助LYA找出 $s$ 的所有子串中,最短的K0子串的长度。

输入格式

第一行包含两个正整数 $n$ 和 $k$,分别表示字符串 $s$ 的长度和要求的末尾连续0的个数。

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

输出格式

输出一个整数,表示最短K0子串的长度。如果不存在K0子串,则输出 $-1$。

样例输入

7 3
abcdefg

样例输出

3

数据范围

$3\le n\le 10^5$
$1\le k\le 10^5$
字符串 $s$ 仅包含小写字母。

题解

本题可以使用双指针+前缀和的思想来解决。我们可以用一个数组 $count$ 来维护以每个字符结尾的子串中,二进制末尾连续0的个数。

具体地,我们从左到右遍历字符串 $s$,对于每个位置 $i$,我们计算以 $s[i]$ 结尾的子串的 $count$ 值,即 $count[i]=count[i-1]+trailing\_zeros(s[i])$,其中 $trailing\_zeros(x)$ 表示 $x$ 的二进制表示中末尾连续0的个数。

然后我们使用双指针 $left$ 和 $right$ 来枚举所有的子串。初始时 $left=right=0$,我们不断地右移 $right$,并更新 $count[right]$ 的值。当 $count[right]-count[left-1]\ge k$ 时,说明子串 $s[left,right]$ 是一个K0串,我们更新答案,并右移 $left$,直到上述不等式不成立。然后继续右移 $right$,直到遍历完整个字符串。

最后,如果没有找到K0子串,则输出 $-1$,否则输出最短K0子串的长度。

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

参考代码

• Python

n, k = map(int, input().split())
s = input()def trailing_zeros(x):cnt = 0while x > 0 and (x & 1) == 0:cnt += 1x >>= 1return cntcount = [0] * (n + 1)
for i in range(1, n + 1):count[i] = count[i - 1] + trailing_zeros(ord(s[i - 1]))left = right = 0
min_len = float('inf')
while right < n:while right < n and count[right + 1] - count[left] < k:right += 1if right == n or count[right + 1] - count[left] >= k:min_len = min(min_len, right - left + 1)left += 1print(min_len if min_len != 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 n = sc.nextInt();int k = sc.nextInt();String s = sc.next();int[] count = new int[n + 1];for (int i = 1; i <= n; i++) {count[i] = count[i - 1] + trailingZeros(s.charAt(i - 1));}int left = 0, right = 0;int minLen = Integer.MAX_VALUE;while (right < n) {while (right < n && count[right + 1] - count[left] < k) {right++;}if (count[right + 1] - count[left] >= k) {minLen = Math.min(minLen, right - left + 1);}left++;}System.out.println(minLen == Integer.MAX_VALUE ? -1 : minLen);}private static int trailingZeros(char c) {int x = (int) c;int cnt = 0;while (x > 0 && (x & 1) == 0) {cnt++;x >>= 1;}return cnt;}
}

• Cpp

#include <iostream>
#include <vector>
#include <string>
using namespace std;int trailingZeros(char c) {int x = (int) c;int cnt = 0;while (x > 0 && (x & 1) == 0) {cnt++;x >>= 1;}return cnt;
}int main() {int n, k;string s;cin >> n >> k >> s;vector<int> count(n + 1);for (int i = 1; i <= n; i++) {count[i] = count[i - 1] + trailingZeros(s[i - 1]);}int left = 0, right = 0;int minLen = INT_MAX;while (right < n) {while (right < n && count[right + 1] - count[left] < k) {right++;}if (count[right + 1] - count[left] >= k) {minLen = min(minLen, right - left + 1);}left++;}cout << (minLen == INT_MAX ? -1 : minLen) << endl;return 0;
}