⚠️ 注：本文仅为作者个人日记，不构成任何形式的指南或保证。本文信息可能过时或不适用于你的具体情况。因参考本文产生的任何后果，作者概不负责。

时间：2025年8月25日-8月28日

基本信息#

Day 1: 报到 / 志愿填报#

TODO

Day 2: 机试#

电脑上有 VS、VSCode（提供 CodeRunner 插件及使用方法）、Dev-cpp 等IDE，类似 OI 赛制，无法得知评测实际得分，支持 C++17

Q1 考试分数#

搞崩我机试的罪魁祸首。。。考场上的我的罪过不是做不出来这题，而是没判断出来这题我的思路不可能做的出来。。。

考点：状态压缩DP

题面#

小明参加了多门科目的考试，他只记得各科得分拼接成的字符串 s，但忘记了具体的分割方式。

已知：

有 m 门科目的满分分别是 r[1], r[2], ..., r[m]；
其余科目的满分均为 t。

请你帮助小明解析字符串 s，将其分割为若干非负整数（表示每科得分），使得：

每个得分不超过其对应科目的满分；
恰好使用 r 中的每个满分值一次（即有 m 个科目使用 r[i] 作为满分）；
其余科目使用满分 t；
所有得分拼接后等于 s，且每个数无前导零（除非是单独的 “0”）。

在所有合法方案中，求最大可能的总分。数据保证存在合法方案。

输入格式：

第一行三个整数：n（字符串长度），t（通用满分），m（特殊满分科目数）

第二行：一个长度为 n 的字符串 s

第三行：m 个整数，表示数组 r

输出格式：

一个整数，表示最大可能总分

样例：

输入

输出

1
248

参考解答#

1
// 答案借助AI生成，仅供参考
2
// 时间复杂度 O(n² × 2^m × m)
3
// 空间复杂度 O(n × 2^m)
4

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

8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11

12
    int n, t, m;
13
    cin >> n >> t >> m;
14

15
    string s;
16
    cin >> s;
17

18
    vector<int> r(m);
19
    for (int i = 0; i < m; ++i) {
20
        cin >> r[i];
21
    }
22

23
    // total_mask: 所有特殊满分科目的状态总数
24
    int total_mask = 1 << m;
25

26
    // dp[i][mask]: 前 i 个字符，使用了 r 的 mask 集合时的最大总分
27
    vector<vector<long long>> dp(n + 1, vector<long long>(total_mask, LLONG_MIN));
28
    dp[0][0] = 0;
29

30
    // 预处理：检查从 start 开始长度为 len 的子串是否合法，并获取数值
31
    auto parseNum = [&](int start, int len) -> long long {
32
        if (len == 0) return -1;
33
        if (len > 1 && s[start] == '0') return -1; // 前导零非法
34
        long long num = 0;
35
        for (int i = start; i < start + len; ++i) {
36
            if (!isdigit(s[i])) return -1;
37
            num = num * 10 + (s[i] - '0');
38
        }
39
        return num;
40
    };
41

42
    // 枚举结束位置 i
43
    for (int i = 1; i <= n; ++i) {
44
        // 枚举起始位置 j
45
        for (int j = 0; j < i; ++j) {
46
            int len = i - j;
47
            long long num = parseNum(j, len);
48
            if (num == -1) continue; // 非法数字
49

50
            // 枚举之前的状态：dp[j][mask]
51
            for (int mask = 0; mask < total_mask; ++mask) {
52
                if (dp[j][mask] == LLONG_MIN) continue;
53

54
                // 选项1：使用 t 作为通用满分（剩余科目）
55
                if (num <= t) {
56
                    if (dp[i][mask] < dp[j][mask] + num) {
57
                        dp[i][mask] = dp[j][mask] + num;
58
                    }
59
                }
60

61
                // 选项2：使用 r 中的某个未使用的特殊满分
62
                for (int k = 0; k < m; ++k) {
63
                    if ((mask & (1 << k)) == 0) { // r[k] 未使用
64
                        if (num <= r[k]) {
65
                            int new_mask = mask | (1 << k);
66
                            if (dp[i][new_mask] < dp[j][mask] + num) {
67
                                dp[i][new_mask] = dp[j][mask] + num;
68
                            }
69
                        }
70
                    }
71
                }
72
            }
73
        }
74
    }
75

76
    // 输出结果：处理完所有字符，且所有特殊满分科目都被使用
77
    cout << dp[n][total_mask - 1] << endl;
78

79
    return 0;
80
}

注意：面试时问我如何进一步优化空间。之前有人说滚动数组，但我目前没想明白在这个题上是怎么弄。

Q2 中位数#

这个还真不难。考场上我基本已经完成了大半…考场上的我怎么会觉得使用set不行呢？？？明明知道set是有序的。。。

我当时想到流式数据的中位数可以用对顶堆维护，是在力扣hot100学到的。不过删除元素又该怎么办呢？于是考场上的我陷入了深深的迷茫。。。。。。

题面#

题目描述：

给定一个长度为 $n$ 的整数数组 $a$ ，以及一个滑动窗口大小 $m$ 。窗口从数组最左端开始，每次向右滑动一个位置，直到覆盖最右端，共产生 $n - m + 1$ 个窗口。

对于每个窗口，定义“独立数”为在该窗口中恰好出现一次的数字。

将每个窗口的所有独立数按升序排序，取排序后序列的中位数：我们这里取下标为 $\left\lfloor \frac{k-1}{2} \right\rfloor$ 的元素（ $k$ 为独立数个数）。若 $k = 0$ ，请输出 “No”

请输出每个窗口的中位数。

输入格式：

第一行两个整数： $n$ （数组长度）， $m$ （窗口大小）

第二行 $n$ 个整数：表示数组 $a$

输出格式：

一行 $n - m + 1$ 个整数，表示每个窗口的独立数中位数，用空格隔开。

数据范围：

$1 \leq m \leq n \leq 10^5$
$1 \leq a[i] \leq 10^9$

样例输入：

1
7 3
2
1 2 2 3 1 4 5

样例输出：

1
1 3 2 3 4

参考解答#

1
// 复杂度分析见结尾
2

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

6
typedef long long ll;
7

8
int main() {
9

10
    int n, m;
11
    cin >> n >> m;
12
    vector<int> a(n);
13
    for (int i = 0; i < n; i++) {
14
        cin >> a[i];
15
    }
16

17
    unordered_map<int, int> freq;
18
    set<int> independent;
19

20
    // 初始化第一个窗口
21
    for (int i = 0; i < m; i++) {
22
        freq[a[i]]++;
23
    }
24
    for (auto& [num, cnt] : freq) {
25
        if (cnt == 1) {
26
            independent.insert(num);
27
        }
28
    }
29

30
    vector<int> ans;
31

32
    // 处理每个窗口
33
    for (int i = 0; i <= n - m; i++) {
34
        // 计算当前窗口中位数
35
        if (independent.empty()) {
36
            ans.push_back(-1);
37
        } else {
38
            auto it = independent.begin();
39
            int k = independent.size();
40
            int idx = (k - 1) / 2;
41
            advance(it, idx);
42
            ans.push_back(*it);
43
        }
44

45
        // 滑动窗口
46
        if (i == n - m) break;
47

48
        int left = a[i];
49
        int right = a[i + m];
50

51
        int old_freq_left = freq[left];
52
        freq[left]--;
53
        int new_freq_left = freq[left];
54

55
        if (old_freq_left == 1) {
56
            independent.erase(left);
57
        } else if (old_freq_left == 2) {
58
            independent.insert(left);
59
        }
60

61
        if (new_freq_left == 0) {
62
            freq.erase(left);
63
        }
64

65
        int old_freq_right = freq.count(right) ? freq[right] : 0;
66
        freq[right]++;
67
        int new_freq_right = freq[right];
68

69
        if (old_freq_right == 0) {
70
            independent.insert(right);
71
        } else if (old_freq_right == 1) {
72
            independent.erase(right);
73
        }
74
    }
75

76
    // 输出结果：-1 转换为 "No"
77
    for (int i = 0; i < ans.size(); i++) {
78
        if (i > 0) cout << " ";
79
        if (ans[i] == -1) {
80
            cout << "No";
81
        } else {
82
            cout << ans[i];
83
        }
84
    }
85
    cout << endl;
86

87

88
    return 0;
89
}

最坏 O(nm)

实际上集合维护是 O(nlogm) 的，但每次找中位数都要 O(k) （k：窗口内独立数个数），最坏可达 O(m)

对顶堆不能删除元素，所以就不能用了么？并非如此，可以用 multiset 模拟堆。还是对顶堆的思想，维护两个 multiset 即可。这样每次插入/删除/查中位数都是 O(log m)，这样总的时间复杂度也可以保证 O(nlogm)

Q3 树的重心#

OI-wiki 上看到过。没认真看。这下服气了。

题面#

题目描述

给定一棵由 $n$ 个节点组成的无根树，我们定义一个节点的平衡值为：删除该节点后，所形成的若干连通块（子树）中，节点数的最大值。

一棵树的重心是指使该平衡值最小的节点。可以证明，一棵树最多有两个重心，且若有两个重心，则它们相邻。

现在，请你找出这棵树的所有重心。

输入格式

第一行一个正整数 $n$ ，表示树的节点数。

接下来 $n - 1$ 行，每行两个正整数 $u$ 和 $v$ ，表示树上存在一条连接节点 $u$ 和 $v$ 的边。

输出格式

输出共一行，按升序输出所有重心的编号，用空格隔开。

样例输入

样例输出

1
3

参考解答#

详见 OI-wiki

1
// 时间复杂度： O(n)
2
// 空间复杂度： O(n)
3

4
const int MAXN = 50005;
5

6
int n;
7
// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]
8
int siz[MAXN],  // 这个节点的「大小」（所有子树上节点数 + 该节点）
9
    weight[MAXN];  // 这个节点的「重量」，即所有子树「大小」的最大值
10
vector<int> centroids;  // 用于记录树的重心（存的是节点编号）
11
vector<int> g[MAXN];
12

13
void dfs(int cur, int fa) {  // cur 表示当前节点 (current)
14
  siz[cur] = 1;
15
  weight[cur] = 0;
16
  for (int v : g[cur]) {
17
    if (v != fa) {  // v 表示这条有向边所通向的节点
18
      dfs(v, cur);
19
      siz[cur] += siz[v];
20
      weight[cur] = max(weight[cur], siz[v]);
21
    }
22
  }
23
  weight[cur] = max(weight[cur], n - siz[cur]);
24
  if (weight[cur] <= n / 2) {  // 依照树的重心的定义统计
25
    centroids.push_back(cur);
26
  }
27
}
28

29
void get_centroids() { dfs(1, 0); }

Q4 万年历#

Q5 Z-order 曲线 / Morton 序坐标映射#

考试的时候看都没看。没想到并不困难。

题面#

题目描述

给定一个边长为 $2^n$ 的正方形方阵（行和列均从 0 开始编号）。该方阵的构造规则如下：

将整个 $2^n \times 2^n$ 的方阵划分为四个 $2^{n-1} \times 2^{n-1}$ 的子方阵，分别称为左上、右上、左下、右下子方阵。
这四个子方阵按照 左上 → 右上 → 左下 → 右下 的顺序，依次填入连续的整数，从 0 开始。
每个子方阵内部的填充方式递归地遵循相同的规则，直到子方阵的边长为 $2^0 = 1$ （即单个格子）为止。

例如，当 $n = 2$ 时，方阵如下所示：

1
 0  1  4  5
2
 2  3  6  7
3
 8  9 12 13
4
10 11 14 15

现在，给定参数 $n$ 以及坐标 $(x, y)$ ，请求出该坐标处方阵中的数值。

输入格式

输入共两行。

第一行包含一个整数 $n$ 。
第二行包含两个整数 $x$ 和 $y$ ，表示查询的坐标。

输出格式

输出一个整数，表示坐标 $(x, y)$ 处的数值。

样例输入

样例输出

1
11

参考解答#

直接构造整个方阵在 $n$ 较大时当然会超出时间和空间限制。递归即可解决。

1
// 时间 O(n)
2
// 空间 O(n)
3

4
#include <iostream>
5
using namespace std;
6

7
long long solve(int n, long long x, long long y) {
8
    if (n == 0) {
9
        return 0;
10
    }
11

12
    long long mid = 1LL << (n - 1); // 子方阵边长：2^(n-1)
13
    long long area_size = mid * mid; // 每个子方阵包含的格子数
14

15
    bool in_top = (x < mid);
16
    bool in_left = (y < mid);
17

18
    if (in_top && in_left) {
19
        // 左上
20
        return solve(n - 1, x, y);
21
    } else if (in_top && !in_left) {
22
        // 右上
23
        return area_size + solve(n - 1, x, y - mid);
24
    } else if (!in_top && in_left) {
25
        // 左下
26
        return 2 * area_size + solve(n - 1, x - mid, y);
27
    } else {
28
        // 右下
29
        return 3 * area_size + solve(n - 1, x - mid, y - mid);
30
    }
31
}
32

33
int main() {
34
    int n;
35
    long long x, y;
36
    cin >> n >> x >> y;
37

38
    cout << solve(n, x, y) << endl;
39

40
    return 0;
41
}

实际上，Z-order 曲线 / Morton 码可以通过 位交织（bit interleaving） 直接计算：

1
long long z_order(int n, long long x, long long y) {
2
    long long result = 0;
3
    for (int i = 0; i < n; i++) {
4
        long long bit_x = (x >> i) & 1;
5
        long long bit_y = (y >> i) & 1;
6
        result |= (bit_y << (2 * i)) | (bit_x << (2 * i + 1));
7
    }
8
    return result;
9
}

Day 2: 英语口试#

共5分钟，简短自我介绍，然后是简单提问，介绍项目等。

Day 4: 面试#

允许带简历。也可以不带。15分钟。

7个面试官，但只有少数老师在提问。个人感觉负责提问的老师对我非常友善，但我自己非常不争气。。。

机试问机试成绩为什么这么差。（我开始解释怎么从第一题在上浪费了大量时间。）于是紧接着问现在有思路了嘛，讲讲第一题思路，如何进一步优化等。
数学一直掷硬币直到连续两次正面，问次数期望。
项目问了实现细节、模型效果。
AI （看我学了深度学习）卷积神经网络的效果为什么好？它的核心特点是什么？（我的某个项目用到了随机森林）介绍下随机森林算法？知不知道我们学校谁随机森林做的比较好？（看我是南大的想让我回答周老师但我没敢答。。。）
其他聊天问如何看待本科生科研和精力分配（看我没什么科研经历以及简历上写了很多乱七八糟的东西hhh）问为什么报我们复旦？（我提到本校还没有offer）如果本校候补到了，和复旦你选哪个？问对AIGC了解多少（感觉是老师觉得实在没什么可以问的了，问我啥我啥不会>_<）

结果#

TODO，铁定寄了

基本信息#

Day 1: 报到 / 志愿填报#

Day 2: 机试#

Q1 考试分数#

题面#

参考解答#

Q2 中位数#

题面#

参考解答#

Q3 树的重心#

题面#

参考解答#

Q4 万年历#

Q5 Z-order 曲线 / Morton 序 坐标映射#

题面#

参考解答#

Day 2: 英语口试#

Day 4: 面试#

结果#

Q5 Z-order 曲线 / Morton 序坐标映射#