06-29 09:56 已编辑北京理工大学算法工程师发布于浙江

关注

【春招笔试】2024-04-23-招商银行-三语言题解

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

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

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

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

alt

🏳️ 难难难！！！本次招商银行的笔试算是今年春招最难的场次之一了

🍭 第一题需要大家找出题目的规律才能顺利AC。

😮‍💨 第二题和第三题都比较难写（不过据说暴力能骗不少分？）

☀️ 01.公司数据一致性问题

题目描述

K小姐所在的公司有 $N$ 个部门，编号从 $1$ 到 $N$ 。由于公司网络系统比较老旧，对于同一个数据 $d$ ，不同部门记录的值可能不同。数据 $d$ 在各部门被记录为 $d_1, d_2, ..., d_N$ 。

公司提出可以通过会议来实现数据的一致性。每次会议会让相邻编号范围内的所有部门一起参加，如果有超过半数的部门能够对数据 $d$ 的值达成共识，那么在此次会议后，参与会议的所有部门会将数据更新为本次达成共识的值。如果会议内无法达成共识，相关部门均不会更新数据。

例如，如果有 $8$ 个部门参与了会议，那么需要有至少 $5$ 个部门达成共识，才能成功更新其他部门的数据。K小姐想知道有哪些数据值可能通过会议被所有部门接受，她一次只能组织一次会议，但是可通过任意多次组织会议来达成所有部门的数据一致性。

输入格式

第一行包含整数 $T$ $(1 \leq T \leq 20)$ ，为测试用例的数量。

每一个测试用例的第一行包含整数 $N$ 。

第二行包含 $N$ 个整数，为每个部门记录的数据 $d$ 。

输入保证所有的测试用例的 $N$ 之和不超过 $3 \times 10^5$ 。

输出格式

输出 $T$ 行，对于每个测试用例输出一行。

如果可能实现所有部门的数据一致，则以升序输出所有可能的数据的值，否则输出 $-1$ 。在同一行内输出数字时，相邻的值用空格分隔，需确保行末没有多余空格。

样例输入

7
5
1 2 2 2 3
6
1 9 0 1 9 0
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 1 1 2 2 2
3
3 2 3
2
2 1

样例输出

数据范围

$1 \leq T \leq 20$
$N$ 的总和不超过 $3 \times 10^5$

题解

本题的思路是找出所有可能达成一致的数据值。我们可以发现，如果相邻的两个部门或者相隔一个部门的两个部门记录的数据值相同，那么这个数据值就有可能通过会议达成一致。

因此，我们可以遍历整个数组，统计所有相邻部门或者相隔一个部门的部门记录的相同数据值，将其加入到一个集合中。最后，如果集合为空，说明无法达成一致，输出 $-1$ ；否则将集合中的元素升序输出即可。

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

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n = int(input())
    data = list(map(int, input().split()))
    values = set()
    
    for i in range(n - 1):
        if data[i] == data[i + 1]:
            values.add(data[i])
    
    for i in range(n - 2):
        if data[i] == data[i + 2]:
            values.add(data[i])
    
    if not values:
        print(-1)
    else:
        print(*sorted(values))

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(new OutputStreamWriter(System.out));

    static int[] readArray(int n) throws IOException {
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        return arr;
    }

    static void solve() throws IOException {
        int n = Integer.parseInt(in.readLine());
        int[] data = readArray(n);
        Set<Integer> values = new HashSet<>();

        for (int i = 0; i < n - 1; i++) {
            if (data[i] == data[i + 1]) {
                values.add(data[i]);
            }
        }

        for (int i = 0; i < n - 2; i++) {
            if (data[i] == data[i + 2]) {
                values.add(data[i]);
            }
        }

        if (values.isEmpty()) {
            out.println(-1);
        } else {
            List<Integer> result = new ArrayList<>(values);
            Collections.sort(result);
            for (int val : result) {
                out.print(val + " ");
            }
            out.println();
        }
    }

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(in.readLine());
        while (T-- > 0) {
            solve();
        }
        out.close();
    }
}

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    
    set<int> values;
    for (int i = 0; i < n - 1; i++) {
        if (data[i] == data[i + 1]) {
            values.insert(data[i]);
        }
    }
    
    for (int i = 0; i < n - 2; i++) {
        if (data[i] == data[i + 2]) {
            values.insert(data[i]);
        }
    }
    
    if (values.empty()) {
        cout << -1 << endl;
    } else {
        for (int val : values) {
            cout << val << " ";
        }
        cout << endl;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

🌤 02.勇敢的K小姐

题目描述

K小姐是一位勇敢的冒险家，她来到了一个神秘的岛屿探险。这个岛屿上有许多关卡，每个关卡都有一个守关者。守关者会提出一个挑战，如果K小姐通过了挑战，就可以获得相应的积分；如果失败了，就会失去相应的积分。如果积分不足，K小姐就会被淘汰出局。

游戏开始时，守关者会确定一个正整数 $A$ ，K小姐需要猜测 $A$ 是奇数还是偶数。如果猜对了，就能获得数量为 $A$ 的积分；如果猜错了，则会失去数量为 $A$ 的积分（如果剩余的积分不足 $A$ ，就输掉所有积分，并被淘汰出局）。

在这个岛屿上，守关者只会给出 $K$ 种不同的正整数 $A$ （ $1 \leq K \leq 4$ ）。

冒险进行了一段时间后，K小姐的积分为 $N$ （ $1 \leq N \leq 10^9$ ），距离游戏结束只剩 $M$ 回合了（ $1 \leq M \leq 3 \times 10^5$ ），她不想被淘汰出局。

请你帮助K小姐，求出一个字典序最小的行动序列，不管守关者如何给出 $A$ ，她都能不被淘汰出局。

输入格式

第一行包含整数 $T$ （ $1 \leq T \leq 10$ ），为测试用例的数量。对于每一个测试用例：

第一行包含三个整数 $N$ ， $M$ 和 $K$ ，分别表示K小姐目前的积分，剩余回合数和守关者可能会做出的选择数。

接下来的 $M$ 行，第 $i$ 行包含了 $K$ 个不同的空格分隔的整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,K}$ （ $1 \leq a_{i,j} \leq 10^3$ ），表示守关者在回合 $i$ 可能会选择的积分。

输入保证所有测试用例的 $M$ 之和不超过 $3 \times 10^5$ 。

输出格式

对于每一个测试用例，输出K小姐保证不被淘汰出局的字典序最小的行动序列，如果无法保证不被淘汰则输出 $-1$ 。行动序列输出在同一行，包含 $M$ 个被空格分隔的单词，每个单词为 Even（偶数）或 Odd（奇数）。

样例输入

样例输出

Even Even Odd
-1

数据范围

$1 \leq T \leq 10$
$1 \leq N \leq 10^9$
$1 \leq M \leq 3 \times 10^5$
$1 \leq K \leq 4$
$1 \leq a_{i,j} \leq 10^3$
输入保证所有测试用例的 $M$ 之和不超过 $3 \times 10^5$

题解

本题可以使用贪心策略来解决。对于每一回合，我们可以预测K小姐的最优得分策略，即选择猜测奇数或偶数中的最大值。然后根据预测的最优得分策略，计算K小姐在游戏结束时的最低积分。

如果K小姐在某一回合的积分低于游戏结束时的最低积分，那么她必须选择猜测奇数或偶数中的最小值，以尽量减少积分损失。否则，她可以选择最优得分策略中的任意一个。

具体实现时，我们可以从最后一个回合开始，倒序计算每个回合的最低积分，并根据当前积分和最低积分的关系来确定K小姐的选择。如果在某一回合的积分不足以支持接下来的最低积分，则说明无法保证不被淘汰，输出 $-1$ 。

时间复杂度为 $O(T \times M \times K)$ ，空间复杂度为 $O(M)$ 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n, m, k = map(int, input().split())
    res = []
    t = ['Even', 'Odd']
    z = []
    for _ in range(m):
        a = list(map(int, input().split()))
        z.append(a)
    
    total_ned = [0] * (m + 1)
    for i, a in enumerate(z[::-1]):
        lmax = rmax = 0
        lmin = rmin = float('inf')
        for val in a:
            if val % 2 == 0:
                rmax = max(val, rmax)
                rmin = min(val, rmin)
            else:
                lmax = max(lmax, val)
                lmin = min(val, lmin)
        
        if lmax == 0 or rmax == 0:
            if lmax == 0:
                total_ned[i + 1] = total_ned[i] - rmin
            else:
                total_ned[i + 1] = total_ned[i] - lmin
        else:
            total_ned[i + 1] = total_ned[i] + min(rmax, lmax)
    
    total_ned = total_ned[::-1]
    for i in range(m):
        a = z[i] 
        lmax = rmax = 0
        lmin = rmin = float('inf')
        for val in a:
            if val % 2 == 0:
                rmax = max(val, rmax)
                rmin = min(val, rmin)
            else:
                lmax = max(lmax, val)
                lmin = min(val, lmin)
        
        if lmax == 0:
            n += rmin 
            res.append(t[0])
        else:
            if n >= total_ned[i + 1] and n >= lmax:
                n -= lmax
                res.append(t[0])
            else:
                if rmax == 0:
                    n += lmin
                    res.append(t[1])
                else:
                    n -= rmin
                    if n < 0:
                        break
                    res.append(t[1])
    
    if len(res) < m:
        print(-1)
    else:
        print(*res)

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

Java

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

public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter writer = new PrintWriter(System.out);
    
    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(reader.readLine());
        for (int t = 0; t < T; t++) {
            solve();
        }
        writer.close();
    }
    
    static void solve() throws IOException {
        String[] nmk = reader.readLine().split(" ");
        int n = Integer.parseInt(nmk[0]);
        int m = Integer.parseInt(nmk[1]);

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

学长刷题笔记文章被收录于专栏

这里收集了超全的刷题笔记，欢迎大家的订阅，会持续跟新的