🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

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

🍒 本专栏已收集 70+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🧩 备战秋招还没订阅的朋友们可以冲一下啦，当试题收集至 100 套后，价格会进行一波调整~

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🪔PDD秋招第二场启动！！！

🍥 今天真是crazy场，贪心+贪心+贪心+贪心

1️⃣ 贪心

2️⃣ 贪心

3️⃣ 贪心

4️⃣ 贪心

01.LYA的树木修剪计划

问题描述

LYA是一位热爱园艺的年轻女孩，她拥有一片由 棵树组成的小树林。这些树木通过树枝相连，形成了一个树状结构。每一根连接树木的树枝都有一个特定的美观度值。

为了让树林更加美观，LYA决定进行一次修剪。她可以选择剪掉任意数量的树枝（也可以不剪）。修剪后，树林可能会分成 个独立的部分。LYA为每种可能的分割情况都准备了一个评分 。

修剪后的总美观度计算方法为：保留下来的树枝美观度之和加上对应分割数量的评分 。

LYA想知道通过合理的修剪，她最多能获得多少总美观度。你能帮助她计算出这个最大值吗？

输入格式

第一行一个正整数 ，表示测试用例的数量。

对于每个测试用例：

• 第一行一个整数 ，表示树的节点数。
• 第二行 个整数 ，表示不同分割数量对应的评分。
• 接下来 行，每行 3 个整数 ，表示节点 与节点 之间有一根美观度为 的树枝。

保证所有测试用例中树枝美观度之和不超过 。 保证每个测试用例给出的结构都是一棵树。

输出格式

对于每个测试用例输出一行，包含一个整数，表示LYA能够获得的最大总美观度。

样例输入

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

样例输出

5
6

样例解释

对于第一个测试用例：

• 树林结构：三个节点，两条树枝（1-2 美观度为1，2-3 美观度为2）
• 分割评分：v1 = 1, v2 = 3, v3 = 4
• 可能的修剪方案：
  1. 不剪任何树枝：总美观度 = 1 + 2 + v1 = 1 + 2 + 1 = 4
  2. 剪掉 1-2 树枝：总美观度 = 2 + v2 = 2 + 3 = 5
  3. 剪掉 2-3 树枝：总美观度 = 1 + v2 = 1 + 3 = 4
  4. 剪掉所有树枝：总美观度 = 0 + v3 = 0 + 4 = 4
• 最大总美观度为 5，通过剪掉 1-2 树枝实现。

对于第二个测试用例：

• 树林结构：三个节点，两条树枝（1-2 美观度为1，2-3 美观度为2）
• 分割评分：v1 = 3, v2 = 3, v3 = 4
• 可能的修剪方案：
  1. 不剪任何树枝：总美观度 = 1 + 2 + v1 = 1 + 2 + 3 = 6
  2. 剪掉 1-2 树枝：总美观度 = 2 + v2 = 2 + 3 = 5
  3. 剪掉 2-3 树枝：总美观度 = 1 + v2 = 1 + 3 = 4
  4. 剪掉所有树枝：总美观度 = 0 + v3 = 0 + 4 = 4
• 最大总美观度为 6，通过不剪任何树枝实现。

数据范围

题解

贪心+排序

1. 首先，将所有树枝按美观度从小到大排序。
2. 初始状态下，总美观度为所有树枝美观度之和加上 （因为此时树林是完整的一个部分）。
3. 然后，我们从美观度最小的树枝开始，逐一尝试剪掉：
   • 剪掉一根树枝，总美观度减少这根树枝的美观度，但分割数增加 1，所以要加上新的 。
   • 比较新的总美观度和之前的最大值，保留较大者。
4. 重复步骤 3，直到尝试剪掉所有树枝。

参考代码

• Python

def solve():
    n = int(input())
    v = list(map(int, input().split()))
    w = []
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        w.append(c)
    
    w.sort()  # 将树枝美观度从小到大排序
    total = sum(w)  # 初始总美观度
    ans = total + v[0]  # 初始最大美观度（不剪任何树枝）
    
    for i in range(n - 1):
        total -= w[i]  # 剪掉一根树枝
        ans = max(ans, total + v[i + 1])  # 更新最大美观度
    
    print(ans)

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

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            solve(br);
        }
    }

    static void solve(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        long[] v = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        int[] w = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            String[] line = br.readLine().split(" ");
            w[i] = Integer.parseInt(line[2]);
        }

        Arrays.sort(w);
        long total = Arrays.stream(w).asLongStream().sum();
        long ans = total + v[0];

        for (int i = 0; i < n - 1; i++) {
            total -= w[i];
            ans = Math.max(ans, total + v[i + 1]);
        }

        System.out.println(ans);
    }
}

• Cpp

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

typedef long long LL;

void solve() {
    int n;
    cin >> n;
    
    vector<LL> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    
    vector<int> w(n - 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b >> w[i];
    }
    
    sort(w.begin(), w.end());
    LL total = accumulate(w.begin(), w.end(), 0LL);
    LL ans = total + v[0];
    
    for (int i = 0; i < n - 1; i++) {
        total -= w[i];
        ans = max(ans, total + v[i + 1]);
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
    
    return 0;
}

02.LYA的魔法蛋糕店

问题描述

LYA 经营着一家魔法蛋糕店，她的蛋糕有一个特殊的魔法属性：每个蛋糕都有一个魔力值。为了让蛋糕更加美味，LYA 可以对蛋糕进行两种魔法操作：

1. 选择一个偶数魔力值的蛋糕，将其魔力值减半。
2. 选择两个蛋糕，将它们合并成一个新蛋糕，新蛋糕的魔力值为原两个蛋糕魔力值之和。

LYA 希望最终店里所有蛋糕的魔力值都变成奇数，这样蛋糕会特别美味。她想知道最少需要进行多少次魔法操作才能达成这个目标。

输入格式

第一行一个正整数 ，表示测试用例的数量 。

对于每个测试用例：

• 第一行为一个正整数 ，表示初始蛋糕的数量 。
• 第二行包含 个正整数 ，表示每个蛋糕的初始魔力值 。

输出格式

对于每个测试用例，输出一个整数，表示 LYA 最少需要进行的魔法操作次数。

样例输入

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

样例输出

3
0
2

数据范围

题解

贪心

首先考虑到，如果有一个奇数

可以通过这个奇数将所有的其他偶数变成奇数

如果全是偶数，找到变成奇数次数最小的那个，然后通过当前奇数，对其他所有偶数进行合并操作

参考代码

• Python

def solve():
    n = int(input())
    cakes = list(map(int, input().split()))
    
    odd_count = sum(1 for cake in cakes if cake % 2 == 1)
    even_count = n - odd_count
    
    if odd_count == 0:
        # 找出最少需要减半次数的蛋糕
        min_ops = min(cake.bit_length() - 1 for cake in cakes)
        return min_ops + even_count - 1
    else:
        return even_count

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

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            System.out.println(solve(sc));
        }
    }
    
    static long solve(Scanner sc) {
        int n = sc.nextInt();
        long[] cakes = new long[n];
        int oddCount = 0;
        
        for (