笔试时间：2024年06月21日

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

第一题

题目

小易正在参加阴阳师的斗技。已知斗技的规则是，双方各上5名式神，谁先击败对方所有角色谁就获胜了。本题为了简化，可以假设每个式神均为单体攻击，每回合玩家将出动自己的一号式神，攻击对方的一号式神，当一号式神血量降到0或0以下时，则式神死亡，二号变成一号。当一方发动攻击时，受到攻击的式神的血量将减去攻击方的攻击力。双方轮流攻击，小易先手攻击，现在小易想知道，最终谁将获得游戏胜利，胜利的一方还剩多少个存活的式神?

输入描述

第一行输入5个正整数，代表小易从1号到5号每个式神的攻击力。

第二行输入5个正整数，代表小易从1号到5号每个式神的血量。

第三行输入5个正整数，代表小易的对手从1号到5号每个式神的攻击力。

第四行输入5个正整数，代表小易的对手从1号到5号每个式神的血量。

1<=ai,bi,ci,di<=10^4。

输出描述

第一行为一个字符串，表示胜利的一方。如果小易获胜，则输出"win"；否则输出"lose"。

第二行为一个正整数，表示胜利一方剩余的存活式神的数量。

样例输入一

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

样例输出一

win

1

解释：共进行5回合，前四回合双方各战死一名式神，第五回合小易攻击后获得胜利，最终小易还剩一个式神。

样例输入二

2 3 4 5 6

6 5 4 3 2

10 1 1 1 1

1000 1 1 1 1

样例输出二

lose

5

参考题解

我们可以模拟这个斗技的过程。每次小易的式神和对方的式神交替攻击。我们使用队列或者列表模拟每个玩家的式神队列。每当一个式神的血量降至0或以下时，就移动到下一个位置。

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

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> a(5), b(5), c(5), d(5);
    for (int i = 0; i < 5; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < 5; ++i) {
        cin >> b[i];
    }
    for (int i = 0; i < 5; ++i) {
        cin >> c[i];
    }
    for (int i = 0; i < 5; ++i) {
        cin >> d[i];
    }

    int op = 0, idx1 = 0, idx2 = 0;

    while (idx1 < 5 && idx2 < 5) {
        if (op % 2 == 0) {
            d[idx2] -= a[idx1];
            if (d[idx2] <= 0) {
                idx2++;
            }
        } else {
            b[idx1] -= c[idx2];
            if (b[idx1] <= 0) {
                idx1++;
            }
        }
        op++;
    }

    if (idx1 < 5) {
        int ans = 5 - idx1;
        cout << "win" << endl;
        cout << ans << endl;
    } else {
        int ans = 5 - idx2;
        cout << "lose" << endl;
        cout << ans << endl;
    }

    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[5];
        int[] b = new int[5];
        int[] c = new int[5];
        int[] d = new int[5];

        for (int i = 0; i < 5; ++i) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < 5; ++i) {
            b[i] = sc.nextInt();
        }
        for (int i = 0; i < 5; ++i) {
            c[i] = sc.nextInt();
        }
        for (int i = 0; i < 5; ++i) {
            d[i] = sc.nextInt();
        }

        int op = 0, idx1 = 0, idx2 = 0;

        while (idx1 < 5 && idx2 < 5) {
            if (op % 2 == 0) {
                d[idx2] -= a[idx1];
                if (d[idx2] <= 0) {
                    idx2++;
                }
            } else {
                b[idx1] -= c[idx2];
                if (b[idx1] <= 0) {
                    idx1++;
                }
            }
            op++;
        }

        if (idx1 < 5) {
            int ans = 5 - idx1;
            System.out.println("win");
            System.out.println(ans);
        } else {
            int ans = 5 - idx2;
            System.out.println("lose");
            System.out.println(ans);
        }
        
        sc.close();
    }
}

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

def main():
    a = [int(input()) for _ in range(5)]
    b = [int(input()) for _ in range(5)]
    c = [int(input()) for _ in range(5)]
    d = [int(input()) for _ in range(5)]

    op = 0
    idx1 = 0
    idx2 = 0

    while idx1 < 5 and idx2 < 5:
        if op % 2 == 0:
            d[idx2] -= a[idx1]
            if d[idx2] <= 0:
                idx2 += 1
        else:
            b[idx1] -= c[idx2]
            if b[idx1] <= 0:
                idx1 += 1
        op += 1

    if idx1 < 5:
        ans = 5 - idx1
        print("win")
        print(ans)
    else:
        ans = 5 - idx2
        print("lose")
        print(ans)

if __name__ == "__main__":
    main()

第二题

题目

小易正在《明日之后》中建造自己的庄园，已知建筑材料共有石灰、砂岩、花岗岩这三种，现在给定了每个建筑这三种材料的消耗，以及该建筑可以带来的收益值。小易初始有A单位石灰，B单位砂岩，C单位花岗岩。他想知道，自己获得的收益最大值为多少?每个建筑只能最多建一个。

输入描述

第一行包含四个正整数 ( n, A, B, C )，分别代表建筑种类数量以及小易初始的石灰、砂岩、花岗岩的单位数量。接下来的 ( n ) 行，每行包含四个整数 ( a_i, b_i, c_i, u_i )，分别代表每种建筑对应的石灰消耗、砂岩消耗、花岗岩消耗，以及该建筑带来的收益。

1<=A,B,C<=50

1<=ai,bi,ci,vi<=10^9

其中30%数据满足n<=20

输出描述

输出一个整数，代表最大收益。

参考题解

动态规划，这个问题是一个典型的背包问题变种，具体是一个多维的背包问题，即“多维费用背包问题”。我们需要考虑三种资源：石灰、砂岩和花岗岩作为限制条件，每种建筑的建造都会消耗一定数量的这三种资源，并且带来一定的收益。

初始化一个三维 DP 数组，大小为 ( (A+1) x (B+1) x (C+1) )，所有值设为 0。

对于每个建筑，更新 DP 数组。

最后DP[A][B][C]将存储使用所有资源的最大收益。

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

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 55;

long long f[N][N][N];

int main()
{
    int n, A, B, C;
    cin >> n >> A >> B >> C;