🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新饿了么近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

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

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

01.K小姐挑战数组相似

问题描述

K小姐正在设计一个全新的拼图游戏，她定义了一种"相似"的概念。她说两个数组是相似的，当且仅当两个数组的所有元素之和相等。

现在K小姐有两个长度分别为 $n$ 和 $m$ 的数组 $A$ 和 $B$。她想知道，最多有多少个数组 $A$ 中的元素 $A_i$，如果将其翻倍，就能使得数组 $A$ 和数组 $B$ 相似。

输入格式

第一行包含两个正整数 $n,m$，分别表示数组 $A$ 和 $B$ 的长度。

第二行共 $n$ 个用空格分开的整数 $A_1,A_2,...,A_n$，表示数组 $A$。

第三行共 $m$ 个用空格分开的整数 $B_1,B_2,...,B_m$，表示数组 $B$。

输出格式

输出一个整数，表示最多有多少个数组 $A$ 中的元素 $A_i$，如果将其翻倍，就能使得数组 $A$ 和数组 $B$ 相似。

样例输入

3 4
1 2 3
4 3 2 1

样例输出

2

数据范围

• $1\le n,m\le 10^5$
• $-10^9\le A_i,B_j\le 10^9$

题解

我们可以先计算出数组 $A$ 和 $B$ 的元素之和，分别记为 $sumA$ 和 $sumB$。如果存在某个 $A_i$ 满足 $sumA+A_i=sumB$，那么将 $A_i$ 翻倍后，数组 $A$ 和 $B$ 就相似了。

因此，我们只需要遍历数组 $A$，对于每个 $A_i$，判断是否有 $A_i=sumB-sumA$ 成立。如果成立，就将答案加一。最后输出答案即可。

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

参考代码

• 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 小姐有 $n$ 根绳子，从 $1$ 到 $n$ 编号，第 $i$ 根绳子的长度为 $a_i$。她希望通过切割操作，使所有绳子长度相等。每次切割操作可以选择一根长度为 $s$ 的绳子，将其切成长度分别为 $x$ 和 $y$ 的两段，其中 $x$ 和 $y$ 均为正整数且满足 $x+y=s$。K 小姐最多进行 $k$ 次切割操作。请你帮她判断是否可以通过不超过 $k$ 次切割操作，使所有绳子长度相等。

输入格式

输入包含多组测试数据。第一行包含一个正整数 $T$（$1\le T\le 10^4$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个正整数 $n$（$1\le n<10^5$）和 $k$（$0\le k\le 10^{14}$），分别表示绳子的数量和最多允许的切割操作次数。
• 第二行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n$（$1\le a_i\le 10^9$），表示每根绳子的初始长度。

保证所有测试数据中 $n$ 的总和不超过 $10^5$。

输出格式

对于每组测试数据，如果可以通过不超过 $k$ 次切割操作使所有绳子长度相等，则输出 YES，否则输出 NO。

样例输入

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

样例输出

YES
NO

数据范围

• $1\le T\le 10^4$
• $1\le n<10^5$
• $0\le k\le 10^{14}$
• $1\le a_i\le 10^9$
• 所有测试数据中 $n$ 的总和不超过 $10^5$

题解

本题可以使用最大公约数（GCD）来求解。我们可以发现，如果所有绳子最终长度相等，那么它们的长度一定是所有初始绳子长度的最大公约数的倍数。因此，我们可以先求出所有绳子长度的最大公约数，然后计算每根绳子需要切割的次数，看是否不超过 $k$ 即可。

具体步骤如下：

1. 求出所有绳子长度的最大公约数 $g$。
2. 对于每根绳子，计算它需要切割的次数，即 $a_i/g-1$。
3. 将所有绳子需要切割的次数相加，如果不超过 $k$，则输出 YES，否则输出 NO。

时间复杂度为 $O(n\log a_{\max })$，其中 $a_{\max }$ 为绳子长度的最大值。空间复杂度为 $O(1)$。

参考代码

• 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 a)
    print("YES" if cnt <= k else "NO")

• Java

import java.io.*;
import java.util.*;

public class Main {
    static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            long k = sc.nextLong();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            int g = a[0];
            for (int i = 1; i < n; i++) {
                g = gcd(g, a[i]);
            }
            long cnt = 0;
            for (int x : a) {
                cnt += x / g - 1;
            }
            System.out.println(cnt <= k ? "YES" : "NO");
        }
    }
}

• Cpp

#include <iostream>
using namespace std;

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n;
        long long k;
        cin >> n >> k;
        int g = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            g = i == 0 ? x : gcd(g, x);
        }
        long long cnt = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            cnt += x / g - 1;
        }
        cout << (cnt <= k ? "YES" : "NO") << '\n';
    }

    return 0;
}

03.卢小姐的魔法强化

问题描述

卢小姐是一位魔法少女，她拥有一把初始攻击力为 $0$ 的魔法棒。现在，她面前有 $n$ 块魔法石，每块魔法石都可以用于强化她的魔法棒。第 $i$ 块魔法石有一个强化上限 $a_i$。

当卢小姐使用第 $i$ 块魔法石强化她的魔法棒时，她需要选择一个不超过强化上限 $a_i$ 的非负整数 $x$ 作为强化系数。假设卢小姐当前的魔法棒攻击力为 $k$，那么强化后的攻击力将变为 $k\mid x$（其中 $\mid$ 表示按位或操作）。每块魔法石只能使用一次，用后即失效。

卢小姐想知道，利用这 $n$ 块魔法石，她的魔法棒最多能达到多大的攻击力。

输入格式

输入包含多组测试数据。

第一行输入一个正整数 $T$（$1\le T\le 10^4$），表示测试数据的组数。

接下来，对于每组测试数据：

• 第一行输入一个正整数 $n$（$1\le n\le 2\times 10^5$），表示魔法石的数量。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots ,a_n$（$0\le a_i\le 10^9$），表示每块魔法石的强化上限。

保证所有测试数据中 $n$ 的总和不超过 $2\times 10^5$。

输出格式

输出包含 $T$ 行，每行一个整数，表示对应测试数据中卢小姐的魔法棒能达到的最大攻击力。

样例输入

2
5
2 3 3 3 6
3
1 0 0

样例输出

7
1

数据范围

• $1\le T\le 10^4$
• $1\le n\le 2\times 10^5$
• $0\le a_i\le 10^9$
• 所有测试数据中 $n$ 的总和不超过 $2\times 10^5$

题解

我们可以用贪心的思想来解决这个问题。对于每一个二进制位，我们优先使用能够强化该位的魔法石。如果该位已经被强化，我们就不需要再使用其他能够强化该位的魔法石了。

具体步骤如下：

1. 统计每个二进制位上有多少块魔法石能够强化该位。
2. 从高位到低位遍历每个二进制位：
   • 如果当前位上有能够强化该位的魔法石，我们就使用其中一块，将答案的该位置为 $1$。
   • 如果当前位上还有剩余的能够强化该位的魔法石，我们可以使用它们来强化答案的低位。具体地，我们可以将答案的低位全部置为 $1$，然后退出遍历。

时间复杂度为 $O(n\log a_{\max })$，其中 $a_{\max }$ 为魔法石强化上限的最大值。空间复杂度为 $O(1)$。

参考代码

• Python

def solve():
    n = int(input())
    gem = list(map(int, input().split()))
    cnt = [0] * 31
    for x in gem:
        for bit in range(31):
            if (x >> bit) & 1:
                cnt[bit] += 1
    atk = 0        
    for pos in range(30, -1, -1):
        if cnt[pos] > 0:
            atk |= 1 << pos
            cnt[pos] -= 1
            if cnt[pos] > 0:
                atk |= (1 << pos) - 1
                break
    print(atk)

T = int(input())    
for case in range(T):
    solve()

• Java

import java.io.*;
import java.util.*;

public class MagicGirl {
    static void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] cnt = new int[31];
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            for (int bit = 0; bit < 31; bit++) {
                if (((x >> bit) & 1) == 1) {
                    cnt[bit]++;
                }
            }
        }
        int atk = 0;
        for (int pos = 30; pos >= 0; pos--) {
            if (cnt[pos] > 0) {
                atk |= 1 << pos;
                cnt[pos]--;
                if (cnt[pos] > 0) {
                    atk |= (1 << pos) - 1;
                    break;
                }
            }
        }
        System.out.println(atk);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int case = 0; case < T; case++) {
            solve(sc);
        }
    }
}

• Cpp

#include <iostream>
using namespace std;

void solve() {
    int n;
    cin >> n;
    int cnt[31] = {0};
    for (int i = 0; i < n; i++) {
        int x; 
        cin >> x;
        for (int bit = 0; bit < 31; bit++) {
            if ((x >> bit) & 1) {
                cnt[bit]++; 
            }
        }
    }
    int atk = 0;
    for (int pos = 30; pos >= 0; pos--) {
        if (cnt[pos] > 0) {
            atk |= 1 << pos;
            cnt[pos]--;
            if (cnt[pos] > 0) {
                atk |= (1 << pos) - 1;
                break;
            }
        }
    }
    cout << atk << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; 
    cin >> T;
    for (int case = 0; case < T; case++) {
        solve();
    }

    return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。