💻 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）来求解。我们可以发现，如果所有绳子最终长度相等，那么它们的长度一定是所有初始绳子长度的最大公约数的倍数。因此，我们可以先求出所有绳子长度的最大公约数，然后计算每根绳子需要切割的次数，看是否不超过 即可。

具体步骤如下：

1. 求出所有绳子长度的最大公约数 。
2. 对于每根绳子，计算它需要切割的次数，即 。
3. 将所有绳子需要切割的次数相加，如果不超过 ，则输出 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