⚠️ 注：本文信息借助不可信回忆+AI生成，不构成任何形式的指南或保证。本文信息可能过时或不适用于你的具体情况。因参考本文产生的任何后果，作者概不负责。

时间：2025年9月12日-9月13日

形式和考察范围等和夏令营基本一致

笔试#

考察了：

命题逻辑、一阶逻辑
已知p1, p2, p3 = softmax(z1, z2, z3)，真实标签为y1, y2, y3，求 softmax 关于输入求导，并结合交叉熵损失
设：
- 模型输出（logits）为：
  $\mathbf{z} = [z_1, z_2, z_3]$
- 经过 Softmax 后的预测概率为：
  $p_i = \text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{k=1}^3 e^{z_k}} = \frac{e^{z_i}}{S}, \quad S = \sum_{k=1}^3 e^{z_k}$
- 真实标签为 one-hot 编码形式：
  $\mathbf{y} = [y_1, y_2, y_3], \quad \text{其中 } y_i \in \{0,1\}, \sum y_i = 1$
- 交叉熵损失函数为：
  $L = -\sum_{i=1}^3 y_i \log p_i$
我们的目标是求：损失 $L$ 对 logits $z_j$ 的导数 $\frac{\partial L}{\partial z_j}$ ，这在反向传播中非常重要。

先计算 $\frac{\partial p_i}{\partial z_j}$ 。

情况 1：当 $i = j$
$\frac{\partial p_i}{\partial z_i} = \frac{\partial}{\partial z_i} \left( \frac{e^{z_i}}{S} \right) = \frac{e^{z_i} \cdot S - e^{z_i} \cdot e^{z_i}}{S^2} = \frac{e^{z_i}}{S} - \frac{e^{2z_i}}{S^2} = p_i - p_i^2 = p_i(1 - p_i)$
情况 2：当 $i \neq j$
$\frac{\partial p_i}{\partial z_j} = \frac{\partial}{\partial z_j} \left( \frac{e^{z_i}}{S} \right) = e^{z_i} \cdot \left( -\frac{e^{z_j}}{S^2} \right) = -\frac{e^{z_i} e^{z_j}}{S^2} = -p_i p_j$
所以统一写成：
$\frac{\partial p_i}{\partial z_j} = \begin{cases} p_i(1 - p_i), & i = j \\ -p_i p_j, & i \neq j \end{cases} = p_i (\delta_{ij} - p_j)$
其中 $\delta_{ij}$ 是 Kronecker delta 函数（ $i=j$ 时为 1，否则为 0）。
$\frac{\partial L}{\partial z_j} = \frac{\partial}{\partial z_j} \left( -\sum_{i=1}^3 y_i \log p_i \right) = -\sum_{i=1}^3 y_i \cdot \frac{1}{p_i} \cdot \frac{\partial p_i}{\partial z_j}$
代入上面的导数表达式：
$\frac{\partial L}{\partial z_j} = -\sum_{i=1}^3 y_i \cdot \frac{1}{p_i} \cdot p_i (\delta_{ij} - p_j) = -\sum_{i=1}^3 y_i (\delta_{ij} - p_j)$
拆开求和：
$= -\left( \sum_{i=1}^3 y_i \delta_{ij} - \sum_{i=1}^3 y_i p_j \right) = -\left( y_j - p_j \sum_{i=1}^3 y_i \right)$
由于 $\sum y_i = 1$ （one-hot 标签），所以：
$\frac{\partial L}{\partial z_j} = -(y_j - p_j) = p_j - y_j$
总结

令：
- $\mathbf{p} = \text{softmax}(\mathbf{z})$
- $\mathbf{y}$ 为 one-hot 真实标签
则：
$\nabla_{\mathbf{z}} L = \mathbf{p} - \mathbf{y}$
这个结果意味着，在实现分类网络时，Softmax + CrossEntropyLoss 的反向传播梯度就是预测概率与真实标签之差。

此外，现代框架（如 PyTorch）提供 LogSoftmax 和 NLLLoss 或直接 CrossEntropyLoss，内部已融合优化，避免显式计算 $\log(p_i)$ 带来的数值问题。
动态规划：nxm 矩阵，左下角到右上角，每一步可以→↑↗，求方法总数
判断完全二叉树
关系分类（关系是不是反射的？）、判断映射（满射？）
贝叶斯定理
线性回归 wx+b
CNN 参数量计算

机试#

前两题为强制使用python的算法题，后两题为强制使用C++的算法题。

Q1#

略，较为简单

Q2 最长“山形”子序列#

题目描述#

给定一个长度为 $n$ 的整数数组 $a$ ，求最长的子序列长度，该子序列满足：先严格递增，后严格递减。

特别地，以下情况也被视为合法的“山形”子序列：

仅包含严格递增部分（不下降部分）
仅包含严格递减部分（不上升部分）
仅包含一个元素

子序列不要求连续。

输入格式

第一行一个正整数 $n$ ，表示数组长度。
第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示数组元素。

输出格式

输出一个整数，表示满足条件的最长子序列的长度。

样例

样例输入 1

1
7
2
1 3 2 5 7 6 4

样例输出 1

1
5

样例解释 1 一个最长的合法子序列为：1 3 5 7 4 或 1 3 5 6 4，长度为 5。

样例输入 2

样例输出 2

1
5

样例解释 2 整个序列严格递减，是合法的（只有下降部分）。

样例输入 3

样例输出 3

1
5

样例解释 3 整个序列严格递增，是合法的（只有上升部分）。

数据范围

对于 $30\%$ 的数据， $1 \leq n \leq 100$
对于 $60\%$ 的数据， $1 \leq n \leq 1000$
对于 $100\%$ 的数据， $1 \leq n \leq 10^5$ ， $1 \leq a_i \leq 10^9$

提示子序列可以从原序列中不连续地选取元素，但必须保持原有顺序。

解题思路#

我们可以使用动态规划：

计算以每个位置 i 结尾的最长严格递增子序列长度 dp_inc[i]
计算以每个位置 i 开始的最长严格递减子序列长度 dp_dec[i]
对于每个位置 i，它可以作为“山顶”，则通过它的最长山形子序列长度为：dp_inc[i] + dp_dec[i] - 1（减1是因为山顶被计算了两次）
答案就是所有位置中的最大值

1
def solve():
2
    n = int(input())
3
    if n == 0:
4
        return 0
5
    a = list(map(int, input().split()))
6

7
    # dp_inc[i]: 以位置 i 结尾的最长严格递增子序列长度
8
    dp_inc = [1] * n
9
    for i in range(1, n):
10
        for j in range(i):
11
            if a[j] < a[i]:
12
                dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1)
13

14
    # dp_dec[i]: 从位置 i 开始的最长严格递减子序列长度
15
    dp_dec = [1] * n
16
    for i in range(n-2, -1, -1):
17
        for j in range(i+1, n):
18
            if a[i] > a[j]:
19
                dp_dec[i] = max(dp_dec[i], dp_dec[j] + 1)
20

21
    # 找到最长的山形子序列
22
    max_length = 0
23
    for i in range(n):
24
        length = dp_inc[i] + dp_dec[i] - 1
25
        max_length = max(max_length, length)
26

27
    return max_length
28

29
# 读取输入并输出结果
30
print(solve())

Q3 字符串平移拼接序列的第 K 个字符#

题目描述#

定义一个字符串生成序列 $S_0, S_1, S_2, \dots$ ，规则如下：

初始值： $S_0 = \texttt{"a"}$
递推规则：对于 $i \geq 1$ $i \geq 1$ ，有 $S_i = S_{i-1} + \text{shift}(S_{i-1})$ $S_{i} = S_{i - 1} + shift (S_{i - 1})$
- 其中 $\text{shift}(T)$ $shift (T)$ 表示将字符串 $T$ $T$ 中每个字符按字母表向后平移一位：
  - $\texttt{'a'} \to \texttt{'b'},\ \texttt{'b'} \to \texttt{'c'},\ \dots,\ \texttt{'y'} \to \texttt{'z'},\ \texttt{'z'} \to \texttt{'a'}$
  - 即循环右移：字符 $c$ 变为 $(c - \texttt{'a'} + 1) \bmod 26 + \texttt{'a'}$

例如：

$S_0 = \texttt{"a"}$
$S_1 = \texttt{"a" + shift("a")} = \texttt{"a" + "b"} = \texttt{"ab"}$
$S_2 = \texttt{"ab" + shift("ab")} = \texttt{"ab" + "bc"} = \texttt{"abbc"}$
$S_3 = \texttt{"abbc" + shift("abbc")} = \texttt{"abbc" + "bccd"} = \texttt{"abbcbccd"}$
$S_4 = \texttt{"abbcbccd" + shift("abbcbccd")} = \texttt{"abbcbccd" + "bccdcdee"} = \texttt{"abbcbccdbccdcdee"}$

给定一个正整数 $k$ ，请求出在某个足够大的 $n$ 下， $S_n$ 的第 $k$ 个字符（1-indexed）。

注意：由于 $S_n$ 的长度随 $n$ 指数增长，你不需要构造整个字符串，而应设计高效算法直接定位第 $k$ 个字符。

输入格式

一行一个正整数 $k$ ，表示查询位置（从 1 开始计数）。

输出格式

输出一个字符，表示序列中第 $k$ 个位置上的小写字母。

样例

样例输入 1

1
1

样例输出 1

1
a

样例输入 2

1
3

样例输出 2

1
b

样例解释 2 $S_2 = \texttt{"abbc"}$ ，第 3 个字符是 $\texttt{'b'}$ 。

样例输入 3

1
7

样例输出 3

1
c

样例解释 3 $S_3 = \texttt{"abbcbccd"}$ ，第 7 个字符是 $\texttt{'c'}$ 。

数据范围

对于 $30\%$ 的数据， $1 \leq k \leq 10^3$
对于 $60\%$ 的数据， $1 \leq k \leq 10^6$
对于 $100\%$ 的数据， $1 \leq k \leq 10^{18}$

提示

字符串长度满足： $\text{len}(S_0) = 1$ $len (S_{0}) = 1$ ， $\text{len}(S_i) = 2 \times \text{len}(S_{i-1})$ $len (S_{i}) = 2 \times len (S_{i - 1})$
- 即 $\text{len}(S_i) = 2^i$
可通过递归方式求解：若 $k \leq 2^{n-1}$ ，则答案在左半部分；否则在右半部分（需还原平移操作）。

解题思路#

我们观察到：

$S_0 = \texttt{"a"}$ , 长度为 $2^0 = 1$
$S_i = S_{i-1} + \text{shift}(S_{i-1})$ ，长度为 $2^i$

关键性质：

每次操作将字符串长度翻倍
前半部分就是 $S_{i-1}$
后半部分是前半部分整体字符向后平移一位（z→a）

因此我们可以递归求解第 $k$ 个字符：

找到最小的 $n$ 使得 $2^n \geq k$ ，即确定 $k$ 所在的字符串层级
如果 $k == 1$ 且当前视为 $S_0$ ，返回 'a'
若 $k \leq 2^{n-1}$ ，说明在左半部分，递归处理 $S_{n-1}$
若 $k > 2^{n-1}$ ，说明在右半部分，对应位置为 $k - 2^{n-1}$ ，递归得到该位置在左半部分的原始字符，再将其逆平移（向前移一位）

注意：右半部分比左半部分每个字符大1，所以我们找到对应位置的字符后要还原。

1
#include <iostream>
2
using namespace std;
3

4
char solve(long long k) {
5
    if (k == 1) {
6
        return 'a';
7
    }
8

9
    // 找到最小的 n 使得 2^n >= k
10
    long long length = 1;
11
    while (length < k) {
12
        length <<= 1; // 相当于 length *= 2
13
    }
14

15
    long long half = length >> 1; // 左半部分长度 = length / 2
16

17
    if (k <= half) {
18
        // 在左半部分，递归处理
19
        return solve(k);
20
    } else {
21
        // 在右半部分，对应左半部分的位置是 k - half
22
        char c = solve(k - half);
23
        // 右半部分字符 = 左半部分字符 + 1 (循环)
24
        return 'a' + (c - 'a' + 1) % 26;
25
    }
26
}
27

28
int main() {
29
    long long k;
30
    cin >> k;
31
    cout << solve(k) << endl;
32
    return 0;
33
}

复杂度分析#

时间复杂度： $O(\log k)$ ，每次递归将问题规模减半
空间复杂度： $O(\log k)$ ，递归栈深度

该算法可以高效处理 $k \leq 10^{18}$ 的情况。

Q4#

略，较为简单

面试#

自我介绍英文：未来研究计划项目为何项目和科研兴趣不一致机器学习决策树对三维重建有什么了解自己的优点和缺点 transformer