2387 字

12 分钟

经验-2025年南大智科预推免

2025-09-13

2026-08-30

经验

大学

/

考试

⚠️ 注：本文由不完整的个人回忆整理而成，题面、样例和解法部分借助了 AI 补全，并非官方原题。文中未标明的精确数据范围已无法确认，请勿将本文当作报考或备考指南。

2026-08-30 修订：根据评论区反馈，更正了 Q2 的样例和时间复杂度，以及 Q3 的 $S_4$ 和平移方向；同时删除了无法核实的精确数据范围。

时间：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++的算法题。

注：已记不清当时的评测平台，也无法确认是否需要自行编写输入输出和头文件，请不要据此判断是 LeetCode 模式还是 ACM 模式。

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
6

样例解释 1 一个最长的合法子序列为 1 3 5 7 6 4，长度为 6。也可以选择 1 2 5 7 6 4。

样例输入 2

样例输出 2

1
5

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

样例输入 3

样例输出 3

1
5

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

原题的精确数据范围已记不清。本节的样例、输入输出描述与代码是根据题意重建的，不是官方原文。

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

解题思路#

我们可以使用动态规划，并用“耐心排序”的方法在 $O(n\log n)$ 时间内求出每个位置对应的长度：

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

1
from bisect import bisect_left
2

3

4
def solve():
5
    n = int(input())
6
    a = list(map(int, input().split()))
7

8
    # dp_inc[i]: 以位置 i 结尾的最长严格递增子序列长度
9
    dp_inc = [0] * n
10
    tails = []
11
    for i, value in enumerate(a):
12
        pos = bisect_left(tails, value)
13
        if pos == len(tails):
14
            tails.append(value)
15
        else:
16
            tails[pos] = value
17
        dp_inc[i] = pos + 1
18

19
    # dp_dec[i]: 从位置 i 开始的最长严格递减子序列长度
20
    dp_dec = [0] * n
21
    tails.clear()
22
    for i in range(n - 1, -1, -1):
23
        pos = bisect_left(tails, a[i])
24
        if pos == len(tails):
25
            tails.append(a[i])
26
        else:
27
            tails[pos] = a[i]
28
        dp_dec[i] = pos + 1
29

30
    return max(dp_inc[i] + dp_dec[i] - 1 for i in range(n))
31

32
# 读取输入并输出结果
33
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" + "bccdcdde"} = \texttt{"abbcbccdbccdcdde"}$

给定一个正整数 $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'}$ 。

原题的精确数据范围已记不清。本节的样例、输入输出描述与代码是根据题意重建的，不是官方原文。

提示

字符串长度满足： $\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}$ ，递归得到该位置在左半部分的原始字符，再将其按字母表向后平移一位

注意：右半部分是左半部分的 shift 结果，所以找到对应位置的字符后要执行一次同向平移，并在 z 后回到 a。

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
}