归档
时光荏苒，文字留痕
共 39 篇文章
2025 Summer Day17
2025 Summer Day17 Content：博弈论 Date：2025.8.2 课堂内容 SG 函数 表示当前游戏局面的函数，后手必胜当且仅当 SG 函数为 0。 多个游戏的组合的 SG 函数为每个游戏的 SG 函数的 异或和。 经典模型 取石子游戏 题目描述 有 n 堆石子，A、B 轮流取
2025 Summer Day18
2025 Summer Day18 课堂内容 完全图匹配构造 描述 对于一个 n （n \mid 2） 个顶点的完全图，将其分为 n-1 个匹配。 思路 我们将其中一个点提出来，剩下的 n-1 个点形成一个正多边形，然后将提出的那个点放在中心。 对于每一条 “斜率” 相同的边，我们把他们放在一个方案
2025 Summer Day19
2025 Summer Day19 内容 休息一天喵o(〃＾▽＾〃)o~
2025 Summer Day20
2025 Summer Day20 课堂内容 字符串哈希 定义哈希函数 H(s): H(s) = \sum_{i=1}^n base^{n-i} s_i \bmod P 其中 base 大于字符集大小。这个哈希函数的冲突概率为 \frac{1}{P}。 通过这个定义，我们可以通过前缀和处理，得到这个
2025 Summer Day21
2025 Summer Day21 Luogu-P13270 最小表示法 题意 给定一个长度为 n 的字符串 s，求 s 的最小表示法。 思路 首先如果暴力的话，复杂度是 O(n^2) 的，但是我们发现如果我们当前已经发现了一个最小表示法，我们想要找到一个比这个还小的表示法，那么一定存在一个位置，使
2025 Summer Day22
2025 Summer Day22 课堂内容 后缀数组 后缀数组主要指两个数组 sa 和 rank： sa_i 表示所有后缀中按字典序大小从小到大排序后排名为 i 的后缀的起始位置。 rank_i 表示以 i 为起始位置的后缀的排名。 其中这两个数组有如下性质：
2025 Summer Day23
2025 Summer Day23 题目 CodeForces-P1672E notepad.exe 题目大意 交互题。 有 n 个长度分别为 l_i 的单词，要求将这些单词排放在一个记事本当中，每两个单词之间需要空格（换行不需要）。你最多可以询问 n+30 次，每次可以询问一个宽度 w，裁判会告诉
2025 Summer Day25
2025 Summer Day25 课堂内容 图论基础知识 图的定义：由点集 V 和边集 E 组成，记作图 G (V, E)。 阶：图的点数，记作 |G|。 相邻：称图中的两个点 相邻，当且仅当 (i,v) \in E。 连通：无向图中若存在 v_0 = u, v_k = v 的路径则称
2025 Summer Day24
2025 Summer Day24 Problem-A IEEE 754 题目描述 题目背景告诉你浮点数表示法(IEEE 754 标准)，要求你求 5^n，其中 n < 1024。 思路 赛场上是直接写的高精度，但是赛后看过题解发现有更简单的做法。 首先用 Python 计算发现，5^1023 大约
2025 Summer Day26
2025 Summer Day26 课堂内容 差分约束 Problem 给定一个包含 n 个不等式的不等式组，要求求出这个不等式组的任意一组解，或者判断不等式组无解。 Solution 对于给定的这个问题，整理一下，发现要求解： \begin{cases} x_1 - x_{2} > c_{1} \