笔试时间：2024年09月29日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

小红有a个桃子，b个苹果，c个雪梨。她现在想将这些水果装到篮子里。每个篮子需要刚好装15个水果，一个篮子最少装4个桃子，3个苹果，

个苹果，2个雪梨。小红想知道最多使用多少个篮子？

输入描述

第一行输入一个正整数t，代表询问的次数。

接下来的t行，每行输入一行三个正整数a,b,c，分别表示桃子、苹果、雪梨的数量。

1≤t≤10^5，1≤a,b,c≤ 10^9。

输出描述

输出t行，每行输出一个正整数，表示答案。

样例输入

2

6 5 5

20 6 4

样例输出

1

2

参考题解

二分答案，在去掉必须的水果之后，判断剩余的水果够不够填充。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int l = 0, r = min({a / 4, b / 3, c / 2});
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        int A = mid * 4;
        int B = mid * 3;
        int C = mid * 2;
        bool ok = true;
        if (A > a || B > b || C > c) {
            ok = false;
        }
        ll remain = a - A + b - B + c - C;
        if (remain < 6 * mid) {
            ok = false;
        }
        if (ok) {
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    cout << l << "\n";
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        int l = 0;
        int r = Math.min(Math.min(a / 4, b / 3), c / 2);
        
        while (l < r) {
            int mid = (l + r + 1) / 2;
            int A = mid * 4;
            int B = mid * 3;
            int C = mid * 2;
            
            boolean ok = true;
            if (A > a || B > b || C > c) {
                ok = false;
            }
            
            long remain = a - A + b - B + c - C;
            if (remain < 6 * mid) {
                ok = false;
            }
            
            if (ok) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        
        System.out.println(l);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solve():
    a, b, c = map(int, input().split())
    
    l, r = 0, min(a // 4, b // 3, c // 2)
    
    while l < r:
        mid = (l + r + 1) // 2
        A = mid * 4
        B = mid * 3
        C = mid * 2
        
        ok = True
        if A > a or B > b or C > c:
            ok = False
        
        remain = a - A + b - B + c - C
        if remain < 6 * mid:
            ok = False
        
        if ok:
            l = mid
        else:
            r = mid - 1
    
    print(l)

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

第二题

题目

小红正在玩一个战争棋盘，棋盘可以视为一个n行m列的矩阵。小红初始往棋盘上投放了k支军队，每个军队属于不同势力。每回合，小红可以任选一个军队按"上、下、左、右"四种方向中的一种移动一个方格，会出现以下4种情况:1.当这个军队移动到一个未被任何势力占领的格子，则军队移动成功，并将其占领。2.当这个军队移动到自己势力的格子，此时军队移动成功。3.若这个军队将移出地图的边界，将移动失败。该军队原地不动。4.若这个军队将移动到另外一个势力的格子，那么两个势力将发生冲突，拥有较多领土的势力将获胜，并占领对方所有领土，消灭对方的军队。特殊的，若两个冲突的势力领土数量相等，那么势力名字的字典序较大者获胜。如果进攻方获胜，则进攻方移动成功。如果防守方获胜，那么防守方的军队保持原来的位置。请你在每次移动操作后输出当前操作的结果。ps:若投放军队的时候有两个或多个军队在同一格子，则直接发生冲突，名字字典序最大的那个势力存活，其他势力消亡。

输入描述

第一行输入n，m，k，分别代表棋盘的行数，列数，以及势力的数量。

接下来k行，每行一个字符串str，x，y。str代表势力的名称，保证所有势力名称不同。x和y代表势力的起始位置。

接下来一个整数q，代表回合数。接下来q行，每行出入一个字符串str和一个字符c。str代表势力的名称，c代表这次移动的方向（W,A,S,D W代表向上走，A向左走，S向下走，D向右走）。

1 <= n, m <= 500

1 <= k <= min(n * m, 2 * 10^4)

1 <= x <= n, 1 <= y <= m

1 <= q <= 2 * 10^4

保证str长度不超过10，仅包含小写英文字母，保证c为(W,A,S,D)中的一个。

输出描述

对于每次操作，输出一行答案:

若本次移动占领了新的边界，则输出一行字符串"vanquish!"

若本次移动到了自己的领土，则输出一行字符串"peaceful."

若本次由于将移出边界导致移动失败，则输出一行字符串"out of bounds!"

若本次移动发生了冲突，胜利者是xxx，则输出一行字符串"xxx wins!”(xxx为势力名字)若输入了不存在的势力，或者输入的字符串代表的势力已经败北则输出一行字符串"unexisted empire."

样例输入

3 3 2

ranko 1 1

kotori 2 2

5

ranko D

ranko W

ranko A

kotori W

kotori W

样例输出

vanquish!

out of bounds!

peaceful.

ranko wins!

unexisted empire.

参考题解

维护一个并查集，并且维护每个格子被谁占领，并且维护谁现在在哪个位置，然后根据题意进行模拟即可。编码可能有点复杂，需要细心。

C++：[此代码未进行大量数据的测试，仅供参考]

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    unordered_map<string, pair<int, int>> mp;
    vector<vector<string>> grid(n, vector<string>(m));
    vector<int> f(n * m), cnt(n * m);
    for (int i = 0; i < n * m; i++) {
        f[i] = i;
        cnt[i] = 1;
    }
    auto transform = [&](int x, int y) -> int {
        return x * m + y;
    };

    auto father = [&](auto self, int i) -> int {
        if (f[i] == i) return i;
        return f[i] = self(self, f[i]);
    };

    auto connect = [&](int i, int j) -> void {
        int fi = father(father, i);
        int fj = father(father, j);
        if (fi != fj) {
            f[fj] = fi;
            cnt[fi] += cnt[fj];
        }
    };

    for (int i = 0; i < k; i++) {
        string name;
        int x, y;
        cin >> name >> x >> y;
        x--, y--;
        if (grid[x][y] == "") {
            grid[x][y] = name;
            mp[name] = {x, y};
        }else {
            string enemy = grid[x][y];
            if (enemy < name) {
                grid[x][y] = name;
                mp[name] = {x, y};
                mp.erase(enemy);
            }
        }
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string name;
        cin >> name;
        char c;
        cin >> c;
        if (!mp.count(name)) {
            cout << "unexisted empire." << "\n";
            continue;
        }
        pair<int, int> p = mp[name];
        int x = p.first, y = p.second;
        int nx = x, ny = y;
        if (c == 'W') {
            nx--;
        }else if (c == 'A') {
            ny--;
        }else if (c == 'S') {
            nx++;
        }else {
            ny++;
        }
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            cout << "out of bounds!" << "\n";
            continue;
        }
        
        int fa1 = father(father, transform(x, y));
        int fa2 = father(father, transform(nx, ny));
        if (fa1 == fa2) {
            cout << "peaceful." << "\n";
            mp[name] = {nx, ny};
            continue;
        }
        int fa_nx = fa2 / m;
        int fa_ny = fa2 % m;
        if