2025.05.17淘天机考笔试真题第三题

春秋招笔试突围

于 2025-05-17 18:52:33 发布

阅读量362

点赞数 19

文章标签：算法数据结构

本文链接：https://blog.csdn.net/Qmtdearu/article/details/148032146

版权

📌 点击直达笔试专栏 👉《大厂笔试突围》

💻 春秋招笔试突围在线OJ 👉 笔试突围OJ

03. 奇偶平衡树分割问题

问题描述

K小姐是一位园林设计师，她设计了一个由多个花坛组成的树形公园。每个花坛中种植了不同数量的花，数量由整数表示。K小姐发现，当公园被分割成多个独立区域时，如果每个区域中的花朵总数都是偶数，游客会感到更加和谐。

现在，K小姐想要通过关闭若干条连接花坛的小路（即删除树的边），将公园分割成若干个独立区域（连通块），使得每个区域内的花朵总数都是偶数。

请你求出，对于每个 $\leq k \leq n-1)$ ，关闭 $k$ 条小路后得到的 $k + 1$ 个独立区域满足条件的方案数。如果不存在满足条件的方案，对应的答案记为 $0$ 。

注意：两种关闭小路的方案若关闭的路径集合不同，则视为不同的方案。

输入格式

第一行给出一个整数 $n$ ，表示花坛的数量。

第二行给出 $n$ 个整数 $W_1, W_2, ..., W_n$ ，其中 $W_i$ 表示第 $i$ 个花坛中的花朵数量。

接下来 $n - 1$ 行，每行包含两个整数 $u$ 与 $\leq u, v \leq n, u \neq v)$ ，表示花坛 $u$ 与花坛 $v$ 之间有一条小路，保证给定的图构成一棵树。

输出格式

输出 $n - 1$ 个数，第 $i$ 个数表示关闭 $i$ 条小路后满足条件的方案数。由于答案可能非常大，请对答案取模 $10^9+7$ 后输出。

样例输入

样例输出

3 3 1 0

样例	解释说明
样例1	当 $k = 1$ 时，关闭方案有 {(1,2)}, {(2,4)}, {(2,5)}，共 3 种。当 $k = 2$ 时，关闭方案有 {(1,2), (2,4)}, {(1,2), (2,5)}, {(2,5), (2,4)}，共 3 种。当 $k = 3$ 时，关闭方案有 {(1,2), (2,4), (2,5)}，共 1 种。当 $k = 4$ 时，没有满足条件的方案。

数据范围

$\leq n \leq 10^5$
$\leq W_i \leq 10^9$
$\leq u, v \leq n$

题解

这道题乍看复杂，但仔细分析后会发现其中的数学规律和解决方案。

首先，我们需要理解什么情况下一个连通块的花朵数能够为偶数。显然，如果一个连通块内奇数花坛的个数为偶数，那么总花朵数一定是偶数（偶数+偶数=偶数，奇数+奇数=偶数）。

我们的目标是通过删除边，将树分成多个连通块，使得每个连通块内的奇数花坛数量都是偶数。那么问题转化为：找出那些删除后能让两侧奇数花坛数量都是偶数的边。

关键观察：一个连通块内奇数花坛数量为奇数时，无论如何分割，都无法使所有子连通块内的奇数花坛数量都为偶数。因为奇数个奇数，无论如何分组，总有一组含有奇数个奇数。

因此，如果整棵树中奇数花坛的总数为奇数，则无解。

接下来，我们定义一个边是"好边"，如果删除这条边后，两个连通块内的奇数花坛数量都是偶数。一条边是好边当且仅当这条边连接的子树内奇数花坛数量为偶数。

如果好边数量为g，那么要删除k条边使所有连通块花朵数为偶数，就相当于从g条好边中选择k条，即组合数C(g,k)。

具体算法如下：

统计整棵树中奇数花坛的总数，如果为奇数，则无解。
通过DFS计算每个子树中奇数花坛的数量。
检查每条边，如果删除后两侧连通块中奇数花坛数量都是偶数，则该边为好边。
计算从g条好边中选k条的组合数C(g,k)，即为答案。

时间复杂度分析：

DFS遍历树的复杂度为O(n)
检查每条边的复杂度为O(n)
计算组合数的复杂度为O(n)
总体时间复杂度为O(n)，空间复杂度为O(n)。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    # 读取输入
    n = int(input())
    w = [0] + list(map(int, input().split()))
    adj = [[] for _ in range(n+1)]
    
    for _ in range(n-1):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    
    # 计算奇数花坛的总数
    odd_count = sum(1 for val in w[1:] if val % 2 == 1)
    
    # 如果奇数花坛总数为奇数，则无解
    if odd_count % 2 == 1:
        print(" ".join(["0"] * (n-1)))
        return
    
    # 计算子树中奇数花坛的数量
    t = [0] * (n+1)
    good_edges = 0
    
    # DFS计算子树信息
    def dfs(node, parent):
        nonlocal good_edges
        is_odd = w[node] % 2  # 当前节点是否为奇数
        
        for child in adj[node]:
            if child != parent:
                # 递归计算子树
                dfs(child, node)
                # 更新当前节点的奇数计数
                is_odd ^= t[child]
        
        t[node] = is_odd
        # 检查是否为好边
        if parent != 0 and t[node] == 0:
            good_edges += 1
    
    # 从根节点开始DFS
    dfs(1, 0)
    
    # 计算组合数
    MOD = 10**9 + 7
    
    # 预计算阶乘和逆元
    fact = [1] * (n+1)
    inv_fact = [1] * (n+1)
    
    for i in range(1, n+1):
        fact[i] = (fact[i-1] * i) % MOD
    
    # 计算逆元（使用费马小定理）
    def pow_mod(x, p):
        res = 1
        while p > 0:
            if p & 1:
                res = (res * x) % MOD
            x = (x * x) % MOD
            p >>= 1
        return res
    
    inv_fact[n] = pow_mod(fact[n], MOD - 2)
    for i in range(n, 0, -1):
        inv_fact[i-1] = (inv_fact[i] * i) % MOD
    
    # 计算组合数C(n,k)
    def comb(n, k):
        if k < 0 or k > n:
            return 0
        return (fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD)
    
    # 计算并输出结果
    result = []
    for k in range(1, n):
        ans = comb(good_edges, k)
        result.append(str(ans))
    
    print(" ".join(result))

if __name__ == "__main__":
    solve()

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

// 快速幂计算a^b mod MOD
ll pow_mod(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 读取花坛权值
    vector<int> w(n+1);
    for (int i = 1; i <= n; i++) 
        cin >> w[i];
    
    // 构建树
    vector<vector<int>> adj(n+1);
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 计算奇数花坛总数
    int tot_odd = 0;
    for (int i = 1; i <= n; i++)
        tot_odd += (w[i] & 1);
    
    // 如果奇数总数为奇数，无解
    if (tot_odd & 1) {
        for (int k = 1; k <= n-1; k++)
            cout << "0" << (k == n-1 ? '\n' : ' ');
        return 0;
    }
    
    // 存储子树奇数数量
    vector<int> t(n+1, 0);
    int good = 0; // 好边数量
    
    // DFS计算子树信息
    vector<bool> vis(n+1, false);
    function<void(int, int)> dfs = [&](int u, int p) {
        int odd = w[u] & 1; // 当前节点是否为奇数
        
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u);
                odd ^= t[v]; // 更新奇数计数
            }
        }
        
        t[u] = odd;
        // 检查是否为好边
        if (p != 0 && t[u] == 0)
            good++;
    };
    
    dfs(1, 0);
    
    // 预计算阶乘和逆元
    vector<ll> fact(n+1, 1), inv_fact(n+1, 1);
    for (int i = 1; i <= n; i++)
        fact[i] = (fact[i-1] * i) % MOD;
    
    inv_fact[n] = pow_mod(fact[n], MOD-2); // 费马小定理
    for (int i = n; i >= 1; i--)
        inv_fact[i-1] = (inv_fact[i] * i) % MOD;
    
    // 组合数计算函数
    auto comb = [&](int n, int k) -> ll {
        if (k < 0 || k > n) return 0;
        return (fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD);
    };
    
    // 输出结果
    for (int k = 1; k <= n-1; k++) {
        ll res = comb(good, k);
        cout << res << (k == n-1 ? '\n' : ' ');
    }
    
    return 0;
}

Java

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

public class Main {
    static final int MOD = (int)1e9 + 7;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取花坛数量
        int n = Integer.parseInt(br.readLine().trim());
        
        // 读取每个花坛的花朵数
        String[] vals = br.readLine().trim().split(" ");
        int[] w = new int[n+1];
        for (int i = 1; i <= n; i++) {
            w[i] = Integer.parseInt(vals[i-1]);
        }
        
        // 构建树
        List<Integer>[] adj = new ArrayList[n+1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < n-1; i++) {
            String[] edge = br.readLine().trim().split(" ");
            int u = Integer.parseInt(edge[0]);
            int v = Integer.parseInt(edge[1]);
            adj[u].add(v);
            adj[v].add(u);
        }
        
        // 计算奇数花坛总数
        int oddCount = 0;
        for (int i = 1; i <= n; i++) {
            if (w[i] % 2 == 1) {
                oddCount++;
            }
        }
        
        // 如果奇数总数为奇数，无解
        if (oddCount % 2 == 1) {
            StringBuilder sb = new StringBuilder();
            for (int k = 1; k <= n-1; k++) {
                sb.append("0");
                if (k < n-1) sb.append(" ");
            }
            System.out.println(sb.toString());
            return;
        }
        
        // 存储子树奇数数量和好边数量
        int[] t = new int[n+1];
        int[] good = new int[1]; // 用数组便于在DFS中修改
        
        // DFS计算子树信息
        dfs(1, 0, w, adj, t, good);
        
        // 预计算阶乘和逆元
        long[] fact = new long[n+1];
        long[] invFact = new long[n+1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i-1] * i) % MOD;
        }
        
        invFact[n] = powMod(fact[n], MOD-2);
        for (int i = n; i > 0; i--) {
            invFact[i-1] = (invFact[i] * i) % MOD;
        }
        
        // 输出结果
        StringBuilder result = new StringBuilder();
        for (int k = 1; k <= n-1; k++) {
            long ans = combination(good[0], k, fact, invFact);
            result.append(ans);
            if (k < n-1) result.append(" ");
        }
        
        System.out.println(result.toString());
    }
    
    // DFS计算子树信息
    static void dfs(int node, int parent, int[] w, List<Integer>[] adj, int[] t, int[] good) {
        int isOdd = w[node] % 2; // 当前节点是否为奇数
        
        for (int child : adj[node]) {
            if (child != parent) {
                dfs(child, node, w, adj, t, good);
                isOdd ^= t[child]; // 更新奇数计数
            }
        }
        
        t[node] = isOdd;
        // 检查是否为好边
        if (parent != 0 && t[node] == 0) {
            good[0]++;
        }
    }
    
    // 快速幂计算
    static long powMod(long a, int b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = (res * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1;
        }
        return res;
    }
    
    // 计算组合数C(n,k)
    static long combination(int n, int k, long[] fact, long[] invFact) {
        if (k < 0 || k > n) return 0;
        return (fact[n] * invFact[k] % MOD * invFact[n-k] % MOD);
    }
}