24届-饿LM(改编题)
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 合集传送们 -> 🧷学长刷题笔记
🍒 本专栏已收集
140+
套题 🍄 题面描述等均已改编,如果和你实际看到的题面描述不一样请理解,做法和题目本质基本不变。🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🍚 01.K小姐挑战数组相似
问题描述
K小姐正在设计一个全新的拼图游戏,她定义了一种"相似"的概念。她说两个数组是相似的,当且仅当两个数组的所有元素之和相等。
现在K小姐有两个长度分别为 和
的数组
和
。她想知道,最多有多少个数组
中的元素
,如果将其翻倍,就能使得数组
和数组
相似。
输入格式
第一行包含两个正整数 ,分别表示数组
和
的长度。
第二行共 个用空格分开的整数
,表示数组
。
第三行共 个用空格分开的整数
,表示数组
。
输出格式
输出一个整数,表示最多有多少个数组 中的元素
,如果将其翻倍,就能使得数组
和数组
相似。
样例输入
3 3
1 1 1
1 2 1
样例输出
3
数据范围
题解
我们可以先计算出数组 和
的元素之和,分别记为
和
。如果存在某个
满足
,那么将
翻倍后,数组
和
就相似了。
因此,我们只需要遍历数组 ,对于每个
,判断是否有
成立。如果成立,就将答案加一。最后输出答案即可。
时间复杂度为 ,空间复杂度为
。
参考代码
- Python
def solution():
n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
sumA = sum(A)
sumB = sum(B)
ans = 0
for a in A:
if a == sumB - sumA:
ans += 1
print(ans)
if __name__ == "__main__":
solution()
- Java
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
long[] A = new long[n];
long[] B = new long[m];
long sumA = 0;
for (int i = 0; i < n; i++) {
A[i] = scanner.nextLong();
sumA += A[i];
}
long sumB = 0;
for (int i = 0; i < m; i++) {
B[i] = scanner.nextLong();
sumB += B[i];
}
int ans = 0;
for (long a : A) {
if (a == sumB - sumA) {
ans++;
}
}
System.out.println(ans);
}
}
- Cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<long long> A(n), B(m);
long long sumA = 0;
for (int i = 0; i < n; i++) {
cin >> A[i];
sumA += A[i];
}
long long sumB = 0;
for (int i = 0; i < m; i++) {
cin >> B[i];
sumB += B[i];
}
int ans = 0;
for (long long a : A) {
if (a == sumB - sumA) {
ans++;
}
}
cout << ans << endl;
return 0;
}
🪥 02.切绳子
问题描述
K 小姐有 根绳子,从
到
编号,第
根绳子的长度为
。她希望通过切割操作,使所有绳子长度相等。每次切割操作可以选择一根长度为
的绳子,将其切成长度分别为
和
的两段,其中
和
均为正整数且满足
。K 小姐最多进行
次切割操作。请你帮她判断是否可以通过不超过
次切割操作,使所有绳子长度相等。
输入格式
输入包含多组测试数据。第一行包含一个正整数 (
),表示测试数据的组数。
对于每组测试数据:
- 第一行包含两个正整数
(
)和
(
),分别表示绳子的数量和最多允许的切割操作次数。
- 第二行包含
个正整数
(
),表示每根绳子的初始长度。
保证所有测试数据中 的总和不超过
。
输出格式
对于每组测试数据,如果可以通过不超过 次切割操作使所有绳子长度相等,则输出
YES
,否则输出 NO
。
样例输入
2
3 4
1 3 2
4 1
2 2 2 3
样例输出
YES
NO
数据范围
- 所有测试数据中
的总和不超过
题解
本题可以使用最大公约数(GCD)来求解。我们可以发现,如果所有绳子最终长度相等,那么它们的长度一定是所有初始绳子长度的最大公约数的倍数。因此,我们可以先求出所有绳子长度的最大公约数,然后计算每根绳子需要切割的次数,看是否不超过 即可。
具体步骤如下:
- 求出所有绳子长度的最大公约数
。
- 对于每根绳子,计算它需要切割的次数,即
。
- 将所有绳子需要切割的次数相加,如果不超过
,则输出
YES
,否则输出NO
。
时间复杂度为 ,其中
为绳子长度的最大值。空间复杂度为
。
参考代码
- Python
def gcd(x, y):
return x if y == 0 else gcd(y, x % y)
T = int(input())
for _ in range(T):
n, k = map(int, input().split())
a = list(map(int, input().split()))
g = a[0]
for i in range(1, n):
g = gcd(g, a[i])
cnt = sum(x // g - 1 for x in
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏短期内不再更新,请勿继续订阅