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

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

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

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

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

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

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

• 🍭 第一题需要大家找出题目的规律才能顺利AC。
• 😮‍💨 第二题和第三题都比较难写（不过据说暴力能骗不少分？）

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

题目描述

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

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

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

输入格式

第一行包含整数 ，为测试用例的数量。

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

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

输入保证所有的测试用例的 之和不超过 。

输出格式

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

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

样例输入

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

样例输出

2
-1
2
-1
1 2
3
-1

数据范围

• 
• 的总和不超过

题解

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

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

时间复杂度为 ，空间复杂度为 。

参考代码

• 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();
    }
}

• Cpp

#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小姐就会被淘汰出局。

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

在这个岛屿上，守关者只会给出 种不同的正整数 （）。

冒险进行了一段时间后，K小姐的积分为 （），距离游戏结束只剩 回合了（），她不想被淘汰出局。

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

输入格式

第一行包含整数 （），为测试用例的数量。对于每一个测试用例：

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

接下来的 行，第 行包含了 个不同的空格分隔的整数 （），表示守关者在回合 可能会选择的积分。

输入保证所有测试用例的 之和不超过 。

输出格式

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

样例输入

2
10 3 2
2 5
1 3
1 3
10 3 3
2 7 5
8 3 4
2 5 6

样例输出

Even Even Odd
-1

数据范围

• 
• 
• 
• 
• 
• 输入保证所有测试用例的 之和不超过

题解

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

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

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

时间复杂度为 ，空间复杂度为 。

参考代码

• 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]);
        int k = Integer.parseInt(nmk[2]);
        
        String[] t = {"Even", "Odd"};
        List<String> res = new ArrayList<>();
        List<int[]> z = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            String[] aStr = reader.readLine().split(" ");
            int[] a = new int[k];
            for (int j = 0; j < k; j++) {
                a[j] = Integer.parseInt(aStr[j]);
            }
            z.add(a);
        }
        
        int[] totalNed = new int[m + 1];
        for (int i = m - 1; i >= 0; i--) {
            int[] a = z.get(i);
            int lmax = 0, rmax = 0;
            int lmin = Integer.MAX_VALUE, rmin = Integer.MAX_VALUE;
            for (int val : a) {
                if (val % 2 == 0) {
                    rmax = Math.max(val, rmax);
                    rmin = Math.min(val, rmin);
                } else {
                    lmax = Math.max(lmax, val);
                    lmin = Math.min(val, lmin);
                }
            }
            
            if (lmax == 0 || rmax == 0) {
                if (lmax == 0) {
                    totalNed[i] = totalNed[i + 1] - rmin;
                } else {
                    totalNed[i] = totalNed[i + 1] - lmin;
                }
            } else {
                totalNed[i] = totalNed[i + 1] + Math.min(rmax, lmax);
            }
        }
        
        for (int i = 0; i < m; i++) {
            int[] a = z.get(i);
            int lmax = 0, rmax = 0;
            int lmin = Integer.MAX_VALUE, rmin = Integer.MAX_VALUE;
            for (int val : a) {
                if (val % 2 == 0) {
                    rmax = Math.max(val, rmax);
                    rmin = Math.min(val, rmin);
                } else {
                    lmax = Math.max(lmax, val);
                    lmin = Math.min(val, lmin);
                }
            }
            
            if (lmax == 0) {
                n += rmin;
                res.add(t[0]);
            } else {
                if (n >= totalNed[i + 1] && n >= lmax) {
                    n -= lmax;
                    res.add(t[0]);
                } else {
                    if (rmax == 0) {
                        n += lmin;
                        res.add(t[1]);
                    } else {
                        n -= rmin;
                        if (n < 0) {
                            break;
                        }
                        res.add(t[1]);
                    }
                }
            }
        }
        
        if (res.size() < m) {
            writer.println(-1);
        } else {
            writer.println(String.join(" ", res));
        }
    }
}

• Cpp

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

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> res;
    vector<vector<int>> z(m, vector<int>(k));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) {
            cin >> z[i][j];
        }
    }

    vector<int> total_ned(m + 1, 0);
    for (int i = m - 1; i >= 0; i--) {
        int lmax = 0, rmax = 0, lmin = INT_MAX, rmin = INT_MAX;
        for (int val : z[i]) {
            if (val % 2 == 0) {
                rmax = max(val, rmax);
                rmin = min(val, rmin);
            } else {
                lmax = max(val, lmax);
                lmin = min(val, lmin);
            }
        }

        if (lmax == 0 || rmax == 0) {
            if (lmax == 0) {
                total_ned[i] = total_ned[i + 1] - rmin;
            } else {
                total_ned[i] = total_ned[i + 1] - lmin;
            }
        } else {
            total_ned[i] = total_ned[i + 1] + min(rmax, lmax);
        }
    }

    for (int i = 0; i < m; i++) {
        int lmax = 0, rmax = 0, lmin = INT_MAX, rmin = INT_MAX;
        for (int val : z[i]) {
            if (val % 2 == 0) {
                rmax = max(val, rmax);
                rmin = min(val, rmin);
            } else {
                lmax = max(val, lmax);
                lmin = min(val, lmin);
            }
        }

        if (lmax == 0) {
            n += rmin;
            res.push_back("Even");
        } else {
            if (n >= total_ned[i + 1] && n >= lmax) {
                n -= lmax;
                res.push_back("Even");
            } else {
                if (rmax == 0) {
                    n += lmin;
                    res.push_back("Odd");
                } else {
                    n -= rmin;
                    if (n < 0) {
                        break;
                    }
                    res.push_back("Odd");
                }
            }
        }
    }

    if (res.size() < m) {
        cout << -1 << endl;
    } else {
        for (const string& s : res) {
            cout << s << " ";
        }
        cout << endl;
    }
}

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

⛅️ 03.K小姐的牛奶传递

题目描述

K小姐的 （）头奶牛围成一个圈。第 头奶牛有一个容量为 （）升的桶，开始时每个桶都装满了牛奶。

每分钟，第 （）头奶牛会把自己桶里的所有牛奶倒入第 头奶牛的桶中，第 头奶牛会把牛奶倒给第 头奶牛。所有的传递同时发生（即如果一头奶牛的桶满了，送出 升牛奶的同时又收到 升，那么她桶中的牛奶量不变）。如果传递后有奶牛的桶中牛奶量超过了它的容量 ，多出的牛奶会洒掉。

请计算经过 分钟后，所有奶牛的桶中一共还剩下多少牛奶。

输入格式

第一行包含一个正整数 ，表示奶牛数量。

第二行包含 个空格分隔的正整数 ，表示每头奶牛桶的容量。

输出格式

输出 行，第 行一个整数，表示经过 分钟后所有奶牛桶中剩余的总牛奶量。

样例输入

6
2 2 2 1 2 1

样例输出

8
7
6
6
6
6

数据范围

• 
• 

题解

这道题可以转化为求长度为 的所有循环区间的最小值之和。我们可以考虑每个 对答案的贡献。

首先，用单调栈预处理出每个 左边第一个严格小于它的位置 ，以及右边第一个大于等于它的位置 （因为是循环数组，所以可以跨过首尾，但不能跨过上一次出现的位置）。这样可以保证每个区间只被计算一次。

然后分类讨论，设区间长度为 ：

1. 当 时， 的贡献为 （两边均无阻挡）。
2. 当 时， 的贡献为 （有一边阻挡）。
3. 当 时， 的贡献为 （两边均有阻挡）。
4. 当 时， 无贡献。

以上三种情况都相当于在答案数组上区间加等差数列。我们可以用差分数组优化，用 的时间完成区间加操作。最后再用前缀和还原出答案即可。

总时间复杂度 ，空间复杂度 。

参考代码

• Python

def add(l, r, x, y, p, s):
    if r < l:
        return
    p[l] += x
    p[r + 1] -= (y * (r - l) + x)
    s[l + 1] += y
    s[r + 1] -= y

def main():
    n = int(input())
    a = [0] * (3 * n + 1)
    l = [0] * (3 * n + 1)
    r = [0] * (3 * n + 1)
    q = [0] * (3 * n + 1)
    p = [0] * (3 * n + 1)
    s = [0] * (3 * n + 1)
    cnt = 0
    b = list(map(int, input().split()))
    
    for i in range(1, n + 1):
        a[i + n] = b[i - 1]
        a[i] = a[i + n * 2] = a[i + n]

    for i in range(1, n * 3 + 1):
        while cnt and a[q[cnt]] >= a[i]:
            cnt -= 1
        l[i] = q[cnt]
        q[cnt + 1] = i
        cnt += 1

    cnt = 0
    for i in range(n * 3, 0, -1):
        while cnt and a[q[cnt]] > a[i]:
            cnt -= 1
        if cnt:
            r[i] = q[cnt]
        q[cnt + 1] = i
        cnt += 1

    for i in range(1, n + 1):
        l[i] = max(l[i + n], i) - n
        r[i] = min(r[i + n], i + 2 * n) - n
        add(1, min(i - l[i], r[i] - i), a[i], a[i], p, s)
        add(min(i - l[i], r[i] - i) + 1, max(i - l[i], r[i] - i), (min(i - l[i], r[i] - i)) * a[i], 0, p, s)
        add(max(i - l[i], r[i] - i) + 1, r[i] - l[i] - 1, (min(i - l[i], r[i] - i)) * a[i] - a[i], -a[i], p, s)

    for i in range(1, n + 1):
        s[i] += s[i - 1]
        p[i] += s[i]

    for i in range(2, n + 1):
        p[i] += p[i - 1]
        print(p[i])
    print(p[n])

if __name__ == "__main__":
    main()

• Java

import java.util.*;

public class Main {
    static final int N = 500010;

    static void add(int l, int r, int x, int y, int[] p, int[] s) {
        if (r < l) {
            return;
        }
        p[l] += x;
        p[r + 1] -= (y * (r - l) + x);
        s[l + 1] += y;
        s[r + 1] -= y;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[3 * n + 1];
        int[] l = new int[3 * n + 1];
        int[] r = new int[3 * n + 1];
        int[] q = new int[3 * n + 1];
        int[] p = new int[3 * n + 1];
        int[] s = new int[3 * n + 1];
        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            a[i + n] = scanner.nextInt();
            a[i] = a[i + n * 2] = a[i + n];
            r[i] = 3 * n + 1;
        }

        for (int i = 1; i <= n * 3; i++) {
            while (cnt > 0 && a[q[cnt]] >= a[i]) {
                cnt--;
            }
            l[i] = q[cnt];
            q[++cnt] = i;
        }
        cnt = 0;
        for (int i = n * 3; i >= 1; i--) {
            while (cnt > 0 && a[q[cnt]] > a[i]) {
                cnt--;
            }
            if (cnt > 0) {
                r[i] = q[cnt];
            }
            q[++cnt] = i;
        }

        for (int i = 1; i <= n; i++) {
            l[i] = Math.max(l[i + n], i) - n;
            r[i] = Math.min(r[i + n], i + 2 * n) - n;
            add(1, Math.min(i - l[i], r[i] - i), a[i], a[i], p, s);
            add(Math.min(i - l[i], r[i] - i) + 1, Math.max(i - l[i], r[i] - i), (Math.min(i - l[i], r[i] - i)) * a[i], 0, p, s);
            add(Math.max(i - l[i], r[i] - i) + 1, r[i] - l[i] - 1, (Math.min(i - l[i], r[i] - i)) * a[i] - a[i], -a[i], p, s);
        }

        for (int i = 1; i <= n; i++) {
            s[i] += s[i - 1];
            p[i] += s[i];
        }
        for (int i = 2; i <= n; i++) {
            p[i] += p[i - 1];
            System.out.println(p[i]);
        }
        System.out.println(p[n]); // the last answer is the same as the second-to-last
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;
int p[N << 1], s[N << 1], a[N * 3], l[N * 3], r[N * 3], q[N * 3], cnt;

inline void add(int l, int r, int x, int y) { // maintain second-order difference
    if (r < l) {
        return;
    }
    p[l] += x;
    p[r + 1] -= y * (r - l) + x;
    s[l + 1] += y;
    s[r + 1] -= y;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i + n];
        a[i + n * 2] = a[i] = a[i + n];
        r[i] = 3 * n + 1;
    }

    for (int i = 1; i <= n * 3; i++) {
        while (cnt && a[q[cnt]] >= a[i]) {
            cnt--;
        }
        l[i] = q[cnt];
        q[++cnt] = i;
    }
    cnt = 0;
    for (int i = n * 3; i >= 1; i--) {
        while (cnt && a[q[cnt]] > a[i]) {
            cnt--;
        }
        if (cnt) {
            r[i] = q[cnt];
        }
        q[++cnt] = i;
    }

    for (int i = 1; i <= n; i++) {
        l[i] = max(l[i + n], i) - n;
        r[i] = min(r[i + n], i + 2 * n) - n;
        add(1, min(i - l[i], r[i] - i), a[i], a[i]);
        add(min(i - l[i], r[i] - i) + 1, max(i - l[i], r[i] - i), (min(i - l[i], r[i] - i)) * a[i], 0);
        add(max(i - l[i], r[i] - i) + 1, r[i] - l[i] - 1, (min(i - l[i], r[i] - i)) * a[i] - a[i], -a[i]);
    }

    for (int i = 1; i <= n; i++) {
        s[i] += s[i - 1];
        p[i] += s[i];
    }
    for (int i = 2; i <= n; i++) {
        p[i] += p[i - 1];
        cout << p[i] << endl;
    }
    cout << p[n] << endl; // the last answer is the same as the second-to-last
    return 0;
}

#招商##银行##春招##秋招##笔试#