集训记录
共 30 篇文章
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} \
2025 Summer Day27
2025 Summer Day27 ~~昨天忘记传了喵~~~ 课堂内容 二分图匹配 Hall 定理 假设 G = (X,Y,E) 是一个二分图，且 |X| \le |Y|。对于 W \subseteq X，记 N_{G}(W) 表示在图 G 中所有与集合 W 中的点相邻的点的集合。那么
2025 Summer Day28
2025 Summer Day28 Content：网络流进阶 Date：2025.8.13 昨天太累了，没写，就今天补上吧 课堂内容 上下界网络流 OI Wiki：Link 很可惜，没学懂，但是大概意思应该是用差分的思想将原来的上下界网络流转换为网络最大流。 没学过真的听不懂啊…… 题目 模拟题-
2025 Summer Day29
2025 Summer Day29 Content：杂题 Date：2025.8.14 CodeForces-1870E Another MEX Problem 题目大意 给你一个数组 a，你可以选择任意互不相交的子数组，先计算每一个子数组的 MEX 值，然后将这些 MEX 值的异或和作为这个方案的
2025 Summer Day30
2025 Summer Day30 Content：模拟赛 Date：2025.8.15 Problem-A 图书配对 题目描述 给定 n 本图书，定义 merge(a_{i},a_{j}) 表示 a_i, a_{j} 直接拼接得到的结果，求满足 merge(