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

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

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

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

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

🌱 01.K小姐爱音乐

问题描述

K小姐是一位热爱音乐的女孩，她有一个由 $n$ 个正整数组成的数组 $a$，每个数字代表一首歌曲的播放次数。现在她想从中选出 $k$ 首歌曲组成一个新的歌单，她希望新歌单中播放次数最多的歌曲尽可能多。

我们定义一个数组的权值为数组中出现次数最多的数字，现在请你帮助K小姐选出 $k$ 首歌曲，使得新歌单的权值最大。

输入格式

本题有多组测试数据。

第一行一个正整数 $T(1\le T\le 100)$，表示数据的组数。

接下来，对于每组测试数据，输入包含两行：

第一行两个正整数 $n,k(1\le k\le n\le 10^5)$，表示数组 $a$ 的长度和需要选择的歌曲数量。

第二行 $n$ 个正整数 $a_i(1\le a_i\le 10^9)$，表示数组的元素值，即每首歌曲的播放次数。

输出格式

输出包含 $T$ 行，对于每个测试数据：

每行一个正整数，表示选出 $k$ 首歌曲组成新歌单的最大权值。

样例输入

1
6 3
2 2 2 1 1 1

样例输出

2

数据范围

• $1\le T\le 100$
• $1\le k\le n\le 10^5$
• $1\le a_i\le 10^9$

题解

本题可以使用贪心的思想来解决。可以先统计每个播放次数出现的频率，然后按照频率从大到小排序。接下来从频率最大的数字开始选择，如果当前数字的频率加上之前选择的数字的总和大于等于 $k$，那么就可以选择当前数字作为新歌单的权值。如果无法选择当前数字，就继续考虑下一个频率最大的数字，直到找到满足条件的数字为止。

具体实现时，可以使用哈希表来统计每个数字出现的频率，然后将频率和对应的数字存入一个数组中，再对该数组按照频率从小到大排序。接下来从后往前遍历排序后的数组，用一个变量 $t$ 记录已经选择的数字的总和，如果当前数字的频率加上 $t$ 以及剩余数字的最大贡献（即剩余数字个数乘以当前数字的频率）大于等于 $k$，就可以选择当前数字更新答案。

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $a$ 的长度。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()
from collections import Counterdef solve():n, k = map(int, input().split())a = list(map(int, input().split()))freq = Counter(a)pairs = [(cnt, num) for num, cnt in freq.items()]pairs.sort()t = 0res = 0remain = len(pairs)for cnt, num in pairs:remain -= 1if cnt + t + remain * cnt >= k:res = max(res, num)t += cntprint(res)T = int(input())
for _ in range(T):solve()

• Java

import java.io.*;
import java.util.*;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(System.out);static int readInt() throws IOException {return Integer.parseInt(in.readLine());}static int[] readArray(int n) throws IOException {String[] s = in.readLine().split(" ");int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(s[i]);}return a;}static void solve() throws IOException {String[] s = in.readLine().split(" ");int n = Integer.parseInt(s[0]);int k = Integer.parseInt(s[1]);int[] a = readArray(n);Map<Integer, Integer> freq = new HashMap<>();for (int x : a) {freq.put(x, freq.getOrDefault(x, 0) + 1);}List<int[]> pairs = new ArrayList<>();for (int num : freq.keySet()) {pairs.add(new int[]{freq.get(num), num});}Collections.sort(pairs, (p1, p2) -> p1[0] - p2[0]);int t = 0;int res = 0;int remain = pairs.size();for (int[] p : pairs) {int cnt = p[0], num = p[1];remain--;if (cnt + t + remain * cnt >= k) {res = Math.max(res, num);}t += cnt;}out.println(res);}public static void main(String[] args) throws IOException {int T = readInt();while (T-- > 0) {solve();}out.close();}
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;void solve() {int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}unordered_map<int, int> freq;for (int x : a) {freq[x]++;}vector<pair<int, int>> pairs;for (auto p : freq) {pairs.emplace_back(p.second, p.first);}sort(pairs.begin(), pairs.end());int t = 0;int res = 0;int remain = pairs.size();for (auto [cnt, num] : pairs) {remain--;if (cnt + t + remain * cnt >= k) {res = max(res, num);}t += cnt;}cout << res << endl;
}int main() {int T;cin >> T;while (T--) {solve();}return 0;
}

☘️02.魔法项链

问题描述

小红有一条神奇的项链，这条项链由 $n$ 颗宝石组成，每颗宝石都有一个魔力值。我们用一个数组 $a$ 来表示这条项链，其中 $a_i$ 表示第 $i$ 颗宝石的魔力值。

这个数组有一个特殊的性质：最后一项 $a_n$ 的值为 $x$，其余项的值满足以下条件：

$$a_i=a_{i+1}\mathrm{mod}x(1\le i<n)$$

现在，小红想知道数组的第 $k$ 项的值是多少，你能帮助她计算出来吗？

输入格式

第一行输入一个整数 $T(1\le T\le 10^5)$，表示询问的次数。

接下来 $T$ 行，每行输入三个整数 $n(1\le n\le 10^9)$，$x(0\le x\le 10^9)$，$k(1\le k\le n+1)$，表示一次询问。

输出格式

对于每次询问，每行输出一个整数表示答案。

样例输入

2
1 1 1
5 1 4

样例输出

0
1

数据范围

• $1\le T\le 10^5$
• $1\le n\le 10^9$
• $0\le x\le 10^9$
• $1\le k\le n+1$

题解

根据题目描述，我们可以得到以下信息：

1. 数组 $a$ 的最后一项 $a_n$ 的值为 $x$。
2. 对于 $1\le i<n$，有 $a_i=a_{i+1}\mathrm{mod}x$。

我们可以分情况讨论：

1. 当 $x>n$ 时，数组 $a$ 的前 $n$ 项都等于 $x\mathrm{mod}n$，最后一项等于 $x$。

   • 如果 $k=1$，直接输出 $x$。
   • 如果 $2\le k\le n$，输出 $x\mathrm{mod}n$。
   • 如果 $k=n+1$，输出 $x$。

2. 当 $x\le n$ 时，数组 $a$ 的前 $x$ 项都等于 $0$，后面的项都等于 $x$。

   • 如果 $1\le k\le x$，输出 $0$。
   • 如果 $x<k\le n+1$，输出 $x$。

根据以上分析，我们可以得到题解代码。

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

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()def solve():n, x, k = map(int, input().split())if x > n:if k == 1:print(x)elif k <= n:print(x % n)else:print(x)else:if k <= x:print(0)else:print(x)T = int(input())
for _ in range(T):solve()

• Java

import java.io.*;
import java.util.*;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(System.out);static int readInt() throws IOException {return Integer.parseInt(in.readLine());}static void solve() throws IOException {String[] s = in.readLine().split(" ");long n = Long.parseLong(s[0]);long x = Long.parseLong(s[1]);long k = Long.parseLong(s[2]);if (x > n) {if (k == 1) {out.println(x);} else if (k <= n) {out.println(x % n);} else {out.println(x);}} else {if (k <= x) {out.println(0);} else {out.println(x);}}}public static void main(String[] args) throws IOException {int T = readInt();while (T-- > 0) {solve();}out.close();}
}

• Cpp

#include <iostream>
using namespace std;void solve() {long long n, x, k;cin >> n >> x >> k;if (x > n) {if (k == 1) {cout << x << endl;} else if (k <= n) {cout << x % n << endl;} else {cout << x << endl;}} else {if (k <= x) {cout << 0 << endl;} else {cout << x << endl;}}
}int main() {int T;cin >> T;while (T--) {solve();}return 0;
}

🍀 03.魔法森林

问题描述

在一片神奇的森林中，有 $n$ 个魔法节点。最初，这些节点之间没有任何连接。

小红是一位热爱探险的女孩，她想要在这片森林中建立一些魔法通道。每次，她会选择两个节点 $u$ 和 $v$，在它们之间建立一条无向边。

在每次建立连接后，小红都会问你一个问题：节点 $u$ 和节点 $v$ 所在的连通块是否形成了一棵基环树？

基环树的定义如下：

1. 包含 $n$ 个节点和 $n$ 条边。
2. 不包含重边和自环。
3. 是一个无向连通图。

你能帮助小红回答这些问题吗？

输入格式

第一行输入两个正整数 $n$ 和 $m$，分别代表魔法节点的数量和小红建立连接的次数。

接下来的 $m$ 行，每行输入两个正整数 $u$ 和 $v$，代表小红在节点 $u$ 和节点 $v$ 之间建立了一条无向边。

输出格式

输出 $m$ 行，每行输出对应操作后，节点 $u$ 和节点 $v$ 所在的连通块是否形成了一棵基环树。如果是，则输出 Yes，否则输出 No。

样例输入

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

样例输出

No
No
Yes
No
No

数据范围

• $1\le n,m\le 10^5$
• $1\le u,v\le n$
• $u\ne v$

题解

可以使用并查集来维护节点之间的连通关系，同时记录每个连通块的节点数和边数。

对于每次建立连接的操作，判断节点 $u$ 和节点 $v$ 是否已经连通：

• 如果已经连通，并且改连通块之前没有形成过基环树，说明在该连通块中添加这条边满足基环树的定义，输出 Yes。
• 如果不连通，则将 $u$ 和 $v$ 所在的连通块合并。

时间复杂度：$O(m\alpha (n))$，其中 $\alpha$ 是阿克曼函数的反函数，在实际应用中可以看作是常数。
空间复杂度：$O(n)$。

参考代码

• Python

from typing import Listp = []def find(x: int) -> int:if x == p[x]:return xp[x] = find(p[x])return p[x]def merge(x: int, y: int) -> None:if find(x) == find(y):returnfax, fay = find(x), find(y)p[fax] = faydef main():n, m = map(int, input().split())global pp = list(range(n + 1))used = set()edges = set()for _ in range(m):u, v = map(int, input().split())if (u, v) in edges or (v, u) in edges:print("No")continueif find(u) != find(v):print("No")merge(u, v)else:fa = find(u)if fa in used:print("No")else:print("Yes")merge(u, v)used.add(fa)edges.add((u, v))edges.add((v, u))if __name__ == "__main__":main()

• Java

import java.util.*;public class Main {static int[] p;static int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));}static void merge(int x, int y) {if (find(x) == find(y)) return;int fax = find(x), fay = find(y);p[fax] = fay;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();p = new int[n + 1];for (int i = 0; i <= n; i++) {p[i] = i;}Set<Integer> used = new HashSet<>();Map<Integer, Integer> edges = new HashMap<>();for (int i = 0; i < m; i++) {int u = sc.nextInt();int v = sc.nextInt();int key1 = u * 100000 + v;int key2 = v * 100000 + u;if (edges.containsKey(key1) || edges.containsKey(key2)) {System.out.println("No");continue;}if (find(u) != find(v)) {System.out.println("No");merge(u, v);} else {int fa = find(u);if (used.contains(fa))System.out.println("No");else {System.out.println("Yes");merge(u, v);used.add(fa);}}edges.put(key1, edges.getOrDefault(key1, 0) + 1);edges.put(key2, edges.getOrDefault(key2, 0) + 1);}}
}

• Cpp

#include <bits/stdc++.h>
using namespace std;vector<int> p;int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));
}void merge(int x, int y) {if (find(x) == find(y)) return;int fax = find(x), fay = find(y);p[fax] = fay;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int n, m;cin >> n >> m;vector<int>(n + 1).swap(p);iota(p.begin(), p.end(), 0);set<int> used;set<pair<int, int>> edges;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;if (edges.count({u, v}) || edges.count({v, u})) {cout << "No\n";continue;}if (find(u) != find(v)) {cout << "No\n";merge(u, v);} else {int fa = find(u);if (used.count(fa))cout << "No\n";else {cout << "Yes\n";merge(u, v);used.insert(fa);}}edges.insert({u, v});edges.insert({v, u});}return 0;
}

写在最后

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