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

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

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍥 本次考察的知识点非常全面，树相关/前缀和/动态规划/树状数组/离散化 等

1️⃣ 推公式，这个只需要推出公式算每个点的贡献即可

2️⃣ 前缀和+dp预处理, 本题数据范围较小，可以直接二维枚举预处理

3️⃣ 比较经典的线性DP，枚举当前字母要改几次即可/改成什么字母。

4️⃣ 离散化+树状数组

🌲 01.K小姐的树形网络 评测链接🔗

题目描述

K小姐是一家大型互联网公司的网络工程师。最近，她接到了一个任务,需要优化公司内部的树形网络结构。

这个网络由 个节点组成,编号从 到 ,节点之间通过 条边相连。初始时,所有节点都直接或间接地连接在一起,整个网络形成一棵树,不存在环。

K小姐发现,如果存在一个节点 ,使得节点 和节点 之间有一条边,节点 和节点 之间也有一条边,那么就可以在节点 和 之间添加一条新的边,从而优化网络结构。

K小姐想知道, 可以添加多少条新边。

输入格式

第一行包含一个正整数 ，表示网络中节点的数量。

接下来 行,每行包含两个正整数 和 ,表示初始时节点 和节点 之间有一条边。保证 且 ,同一条边不会重复出现。

输出格式

输出一个整数,表示最多可以添加的新边数量。

样例输入

5
1 2
1 3
2 4
2 5

样例输出

4

数据范围

题解

结论+推公式

可以这样考虑:对于树上的每个节点 ，如果它有 个相邻的节点，那么这 个节点两两之间都可以通过节点 来连接一条新边。因此，节点 可以贡献 条新边。

只需要遍历每个节点，计算它的相邻节点数量，然后套用上述公式，将所有节点的贡献相加即可得到答案。

参考代码

• Python

from math import comb

# 读入节点数
n = int(input())
# 建立邻接表,用于存储树的边
g = [[] for _ in range(n)]
# 读入 n-1 条边,构建树
for _ in range(n - 1):
    # 读入边的两个端点 a 和 b,并将其减 1 以转换为 0 索引
    a, b = map(lambda x: int(x) - 1, input().split())
    # 在邻接表中添加边 a-b
    g[a].append(b)
    g[b].append(a)

# 初始化结果变量
res = 0
# 遍历每个节点
for i in range(n):
    # 获取节点 i 的相邻节点数量
    sz = len(g[i])
    # 计算节点 i 能贡献的新边数量,即从 sz 个节点中选 2 个节点的组合数
    res += comb(sz, 2)
# 输出结果
print(res)

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读入节点数
        int n = Integer.parseInt(br.readLine());
        // 建立邻接表,用于存储树的边
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        // 读入 n-1 条边,构建树
        for (int i = 0; i < n - 1; i++) {
            String[] edge = br.readLine().split(" ");
            // 读入边的两个端点 a 和 b,并将其减 1 以转换为 0 索引
            int a = Integer.parseInt(edge[0]) - 1;
            int b = Integer.parseInt(edge[1]) - 1;
            // 在邻接表中添加边 a-b
            g[a].add(b);
            g[b].add(a);
        }

        // 初始化结果变量
        long res = 0;
        // 遍历每个节点
        for (int i = 0; i < n; i++) {
            // 获取节点 i 的相邻节点数量
            int sz = g[i].size();
            // 计算节点 i 能贡献的新边数量,即从 sz 个节点中选 2 个节点的组合数
            res += (long) sz * (sz - 1) / 2;
        }
        // 输出结果
        System.out.println(res);
    }
}

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读入节点数
    int n;
    cin >> n;
    // 初始化结果变量
    long long res = 0;
    // 建立邻接表,用于存储树的边
    vector<vector<int>> g(n);
    // 读入 n-1 条边,构建树
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        // 将节点编号减 1,以转换为 0 索引
        --a, --b;
        // 在邻接表中添加边 a-b
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // 遍历每个节点
    for (int i = 0; i < n; i++) {
        // 获取节点 i 的相邻节点数量
        int sz = g[i].size();
        // 计算节点 i 能贡献的新边数量,即从 sz 个节点中选 2 个节点的组合数
        res += 1ll * sz * (sz - 1) / 2;
    }
    // 输出结果
    cout << res << "\n";
    return 0;
}

🪐02.K小姐的子数组最大和 评测链接🔗

问题描述

K小姐有一个长度为 的整数数组 。她想知道对于给定的 个区间 ，数组 中所有长度在 到 之间（包括 和 ）的子数组的最大和是多少。

如果数组 可以通过删除数组 的若干个（可能为 0 个）前缀元素和若干个（可能为 0 个）后缀元素得到，则称数组 是数组 的子数组。

输入格式

第一行包含两个正整数 和 （，），分别表示数组 的长度和询问的个数。

第二行包含 个整数 （），表示数组 的元素。

接下来 行，每行包含两个整数 和 （），表示一个询问的区间。

输出格式

对于每个询问，输出一行一个整数，表示该询问区间内所有子数组的最大和。

样例输入

3 2
1 2 -1
1 2
3 3

样例输出

3
2

数据范围

题解

前缀和预处理+动态规划

首先预处理出前缀和数组 ,其中 表示数组 的前 个元素之和。这样就可以用 快速求出区间 的元素和了。

然后再预处理出一个数组 ,其中 表示所有长度为 的子数组的最大元素和。

接下来定义状态 表示数组 中下标范围 内的子数组的最大元素和。

转移方程如下:

• 当 时,,即长度为 的子数组的最大元素和；
• 当 时,,即从 和 中取较大值。

这里范围比较小，所以直接 预处理即可，若需要处理更大的区间可以考虑用 ST表/线段树等结构

最后对于每个询问 ，答案就是 。

时间复杂度

空间复杂度

参考代码

• Cpp

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q;
    cin >> n >> q;
    
    // 读入数组 a
    vector<int> a(n);
    for (int& i : a) cin >> i;
    
    // 计算前缀和数组 s
    vector<int> s(n + 1);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i - 1];
    }
    
    // 预处理数组 maxv,其中 maxv[i] 表示所有长度为 i 的子数组的最大元素和
    vector<int> maxv(n + 1, -1e18);
    for (int sz = 1; sz <= n; sz++) {
        for (int i = 1; i + sz - 1 <= n; i++) {
            int l = i, r = i + sz - 1;
            maxv[sz] = max(maxv[sz], s[r] - s[l - 1]);
        }
    }
    
    // 定义状态 f[i][j] 表示数组 maxv 中下标范围 [i, j] 内的子数组的最大元素和
    vector<vector<int>> f(n + 1, vector<int>(n + 1, -1e18));
    for (int i = 1; i <= n; i++) {
      	f[i][i] = maxv[i];
        for (int j = i; j <= n; j++) {
   
                // 当 i < j 时,f[i][j] = max(f[i][j - 1], maxv[j]),即从 f[i][j - 1] 和 maxv[j] 中取较大值
                f[i][j] = max(f[i][j - 1], maxv[j]);
        }
    }
    
    // 处理询问
    while (q--) {
        int l, r;
        cin >> l >> r;
        // 对于每个询问 [l, r],答案就是 f[l][r]
        cout << f[l][r] << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int q = Integer.parseInt(params[1]);
        
        // 读入数组 a
        int[] a = new int[n];
        params = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(params[i]);
        }
        
        // 计算前缀和数组 s
        long[] s = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i - 1];
        }
        
        // 预处理数组 maxv,其中 maxv[i] 表示所有长度为 i 的子数组的最大元素和
        long[] maxv = new long[n + 1];
        Arrays.fill(maxv, Long.MIN_VALUE);
        for (int sz = 1; sz <= n; sz++) {
            for (int i = 1; i + sz - 1 <= n; i++) {
                int l = i, r = i + sz - 1;
                maxv[sz] = Math.max(maxv[sz], s[r] - s[l - 1]);
            }
        }