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

ACM金牌团队️ | 多次AK大厂笔试 ｜ 大厂实习经历

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

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

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

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

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

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

美团秋招笔试，来啦！！！

本次的第三题有点问题，不清楚是题意还是其他有没描述清楚什么，目前没看到通过率 100% 的解法。

1️⃣ 简单的分奇偶考虑

2️⃣ 可以DFS，也可以直接for循环模拟，只需要统计儿子的数量即可。

3️⃣ 线段树，但目前没有通过率 100 的做法，需要完成 区间+-，区间求最大/最小，区间统计0的数量等操作，这些信息需要线段树来维护，如果有正确解法,后续会更新～

01.LYA的魔法书架

问题描述

LYA是一位热爱魔法的少女。她有一个神奇的书架，上面摆放着 本魔法书。每本书都有一个魔力值 。LYA发现，当书架上所有书的魔力值都是奇数或都是偶数时，书架会释放出强大的魔法。

为了激活书架的魔法，LYA可以对任意一本书施加增强魔法。每次施法，她可以选择一本书，将其魔力值增加任意正整数 （）。但是，每次施法都需要消耗能量，消耗的能量值等于该书原本的魔力值加上增加的魔力值，即 。

现在，LYA想知道要使书架上的所有书魔力值要么全为奇数，要么全为偶数，她最少需要消耗多少能量。

输入格式

第一行一个整数 （），表示魔法书的数量。

第二行 个整数，第 个数为 （），表示第 本书的魔力值。

输出格式

一个整数，表示 LYA 使书架上的所有书魔力值要么全为奇数，要么全为偶数所需消耗的最少能量。

样例输入

3
1 2 3

样例输出

3

数据范围

题解

最优情况是取 ，然后分别计算变成全偶数和全奇数的情况即可，

参考代码

• Python

# 读取输入
n = int(input())
books = list(map(int, input().split()))

# 初始化变成全奇数和全偶数的代价
cost_to_odd = 0
cost_to_even = 0

# 遍历每本书，计算代价
for book in books:
    if book % 2 == 0:  # 如果是偶数
        cost_to_odd += book + 1  # 变成奇数的代价
    else:  # 如果是奇数
        cost_to_even += book + 1  # 变成偶数的代价

# 输出较小的代价
print(min(cost_to_odd, cost_to_even))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取书的数量
        int n = scanner.nextInt();
        
        // 初始化变成全奇数和全偶数的代价
        long costToOdd = 0;
        long costToEven = 0;
        
        // 遍历每本书，计算代价
        for (int i = 0; i < n; i++) {
            int book = scanner.nextInt();
            if (book % 2 == 0) {  // 如果是偶数
                costToOdd += book + 1;  // 变成奇数的代价
            } else {  // 如果是奇数
                costToEven += book + 1;  // 变成偶数的代价
            }
        }
        
        // 输出较小的代价
        System.out.println(Math.min(costToOdd, costToEven));
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    // 初始化变成全奇数和全偶数的代价
    long long cost_to_odd = 0, cost_to_even = 0;
    
    // 遍历每本书，计算代价
    for (int i = 0; i < n; i++) {
        int book;
        cin >> book;
        if (book % 2 == 0) {  // 如果是偶数
            cost_to_odd += book + 1;  // 变成奇数的代价
        } else {  // 如果是奇数
            cost_to_even += book + 1;  // 变成偶数的代价
        }
    }
    
    // 输出较小的代价
    cout << min(cost_to_odd, cost_to_even) << "\n";
    
    return 0;
}

02.LYA的魔法树园

问题描述

LYA 是一位热爱魔法的少女。她的魔法树园里有许多奇妙的树，每棵树都有一个根节点和若干子节点。LYA 发现，当两个节点拥有相同数量的直接子节点时，这两个节点就