24届-饿LM(改编题)

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编,如果和你实际看到的题面描述不一样请理解,做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞

alt

🍚 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

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

本专栏短期内不再更新,请勿继续订阅

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
评论
1
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务