BNUZH-ACM 周赛第 10 场题解
BNUZH-ACM 周赛 Round 10 - 洛谷 | 计算机科学教育新生态
思考的索引
算法题解、数学笔记，以及沿途的小发现。
7 分钟
BNUZH-ACM 周赛第 9 场题解
BNUZH-ACM 周赛 Round 9 - 洛谷 | 计算机科学教育新生态
BNUZH-ACM 周赛第 7 场题解
BNUZH-ACM 周赛 Round 7 - 洛谷 | 计算机科学教育新生态
BNUZH-ACM 周赛第 6 场题解
BNUZH-ACM 周赛 Round 6 - 洛谷 | 计算机科学教育新生态
BNUZH-ACM 周赛第 5 场题解
BNUZH-ACM 周赛 Round 5 - 洛谷 | 计算机科学教育新生态
BNUZH-ACM 周赛第 4 场题解
BNUZH-ACM 周赛 Round 4 - 洛谷 | 计算机科学教育新生态
BNUZH-ACM 周赛第 3 场题解
BNUZH-ACM 周赛 Round 3 - 洛谷 | 计算机科学教育新生态
BNUZH-ACM 周赛第 2 场题解
比赛链接
BNUZH-ACM 周赛第 1 场题解
(BNUZH-ACM 周赛 Round 1 - 洛谷 | 计算机科学教育新生态)
2024 蓝桥杯国赛 Python B 组题解
A Solution dfs 枚举所有题目的选择情况。状态数一共为 。答案为 。
2025 年春季北师大珠海校区实变函数期中试题与解答
说明 第六、七题和第八、九题为两组选做题，选答一道即可。 第十一题为附加题。 课本原题网络上参考较多，在此不再重复。 部分证明只提供了思路梗概，严格证明的细节读者容易自己给出。
2023 蓝桥杯国赛 Python A 组题解
A 跑步计划 Solution datetime 库中 的 weekday() 可以获取某一天的星期信息。
2023 蓝桥杯省赛 Python A 组题解
A 特殊日期 Solution 利用 Python 系统库 datetime 可以省去日期枚举中的细节处理。
2025 蓝桥杯培训第二讲：搜索与优化技巧
[蓝桥杯] 第二讲：搜索与优化技巧 - 题单 - 洛谷 | 计算机科学教育新生态 提醒：本文代码均可点击左上角折叠，希望能帮助您优化阅读体验。 Solution
2024 蓝桥杯省赛 Python B 组题解
题目传送门 A 穿越时空之门 Solution 枚举，按题意暴力计算即可。
2024 蓝桥杯省赛 Python A 组题解
题目传送门 A 拼正方形 Solution 二分答案。根据题目所求为满足条件的最大值，因此二分枚举所得正方形的最大边长，并检验是否能拼成。
CF2001D Longest Max Min Subsequence 题解
Problem - 2001D - Codeforces Solution 所求序列长度为 中的元素种类数。小根堆 维护每种元素最后一次出现的位置。
CF837D Round Subset 题解
Round Subset - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Solution 问题转化为：设取的 个数的因子中共有 个 ， 个 。选择取数的方案，使得 最大化。
CF372C Watching Fireworks is Fun 题解
Watching Fireworks is Fun - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Solution 定义 表示在位置 观看烟花 时，目前开心值的最大值。设 ，则
CF1187E Tree Painting 题解
Tree Painting - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Solution 容易得出结论：可选择的只有第一个染色点，且不妨将该点视作根结点。该点确定后，本题答案也就确定了为所有子树的大小之和。现在要求的是如何选择根结点，使得答案最大。
CF208E Blood Cousins 题解
Blood Cousins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Solution 用倍增可以快速求出 的 级祖先 ，然后对 打上标记，表示它与询问 有关。标记可用 vector 维护。
CF600E Lomsat gelral 题解
Lomsat gelral - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Solution 树上启发式合并模板题。 考虑暴力做法：设以 为根的子树的答案为 ，每次求 都重新遍历整棵子树。选择从 开始往下 dfs，然后从子结点开始一个一个地求 ，时间复杂度为 。
异或线性基：构造、最大异或和与可表示性查询
线性基 - OI Wiki (oi-wiki.org) 【模板】线性基 - 洛谷
2024 CCPC 网络赛 E 随机过程题解
传送门 Solution 设最大节点数为 ，因为第 层最多有 个节点，所以有 。
2024 CCPC 网络赛 D 编码器-解码器题解
传送门 Solution 注意到 由左右两个相同的 夹着一个新字符 拼接而来。所以可以尝试从 的答案转移得到 的答案。
CF767C Garland 题解
传送门 Solution 设所有节点的权重之和为 ，若 不能被 整除，则问题无解。
CF337D Book of Evil 题解
传送门 Solution 设 表示以 为根的子树中，离 最远的重要结点， 表示以 为根的子树中，离 次远的重要结点， 表示以 为根的子树外离 最远的结点。
CF1132F Clear the String 题解
传送门 Solution 区间 dp。设 为删去区间 的最小代价。显然，一个包含两种或以上字符的区间，它代价最小的删去方法中，一定存在一个断点将区间分成左右两半，使得这两个区间是各自删去的。
CF383C Propagating tree 题解
传送门 Solution 一棵子树中的所有点的 dfs 序必定连续，因此先 dfs 求出每个点的 dfs 序和深度，以及该子树的点的 dfs 序的左右边界。
CF432D Prefixes and Suffixes 题解
传送门 Solution 使用扩展 KMP 求出 。设字符串 长度为 ，下标从 开始。某前缀同时也是后缀，当且仅当 。
CF438D The Child and Sequence 题解
传送门 Solution 设 ，那么一定有 。因此每个点最多经过 次取余就会变成 。
CF2B The least round way 题解
传送门 Solution 每个 都是由一对 、 相乘而得。设 为点 到 路上最少 的数量， 为最少 的数量。答案即为 。
CF920F SUM and REPLACE 题解
传送门 Solution 对于 ，不超过 6 次操作可将一个 变为 或 。有 的方法预处理出 的正约数个数。
洛谷 P2391 白雪皑皑题解
传送门 Solution 倒序染色使得每个点被染色后，可从序列中删去。使用单向链表，设 为点 在链表中指向的下一个点。设当前染色区间为 ，点 染色结束后，令 。
UVA1316 Supermarket 题解
传送门 Solution 对物品以过期时间（从小到大）为第一关键字，价格（从大到小）为第二关键字进行排序，然后开一个按照物品价值排序的小根堆。
CF1200E Compress Words 题解
传送门 Solution 设当前待合并的串为 ，已合并的串为 。若 ，则 。否则 等于 与 长度为 的后缀拼接而成的字符串。对 进行 KMP，求出最大相同前后缀长度 。把 的相应长度后缀并入 后面即可。
CF242E XOR on Segment 题解
传送门 Solution 观察到 ，拆位后数组变成 20 条长度为 的 01 串。开二十棵线段树分别维护这些串的区间和。
CF2003D2 Turtle and a MEX Problem (Hard Version) 题解
传送门 Solution 设第 个序列最小没出现的非负整数为 ，次小没出现的非负整数为 。从 向 连有向边。由于 ，最后得到的是一张有向无环图，且每个点之间不一定连通。
CF1627D Not Adding 题解
传送门 Solution 注意数据范围。用桶记录某数是否在数组内出现。从 枚举 到 ，检查是否能生成 。若所有在数组内的 的倍数的最大公约数等于 ，则可生成 。 设数组内最大的数为 ，时间复杂度
CF19B Checkout Assistant 题解
传送门 Solution 若设 为选择付款的商品的 之和为 时，支付的最小金额， 为这些商品的数量。那么只有 时， 才为一种合法的答案。
CF126B Password 题解
传送门 Solution 1 考虑使用 Z 函数（exkmp）且设 长度为 ，下标从 开始。
洛谷 P10894 虚树题解
传送门 Solution 树上 dp，设 为以 为根的子树中好的非空子集数量。若 为叶节点， 则 。下面假设 非叶节点， 为 的子节点：
CF2001C Guess The Tree 题解
传送门 Solution 初始化 ，其余 ，? 1 2 加入询问队列。 每次从队头取出询问 ? u v （保证 ，），返回的结果是 ， 路径的中点 。
洛谷 P10893 城市化发展委员会题解
传送门 Solution 设 所有元素之和为 。 若 ，答案为 。
ABC367E Permute K times 题解
传送门 Solution 设 表示经过 次操作后，位置 上的数字为 。初始化 。转移方程
ABC367F Rearrange Query 题解
传送门 Solution 用 mt19937 重新给 随机赋权为 中的一个数，然后判断两个区间内的元素之和是否相等即可。区间和保证在 long long 范围内。
ABC367D Pedometer 题解
传送门 Solution 首先拆环成链，令 。 然后求出 的前缀和 。当 时，说明 。
CF1998C Perform Operations to Maximize Score 题解
传送门 Solution 取出的 若 ，则 。否则 。
HDU7523 cats 的 k-xor 题解
传送门 Solution 进制下不进位加法的本质是，若两数第 位相加后超过了 ，则减去 。所以 时问题有解，且当 时，有 。
二元一次不定方程：扩展欧几里得算法与应用
前置知识 扩展欧几里得算法（辗转相除法） 对 ，有
ABC366F Maximum Composition 题解
传送门 Solution 设 ，。若 ，则 。又因为 ，移项得。
HDU7528 cats 的电脑中毒题解
传送门 Solution 设两个二进制串有 位不同，那么它们的距离 。设与串 的距离为 ，题目即求使得 最大的串。
CSP 2023-12 树上搜索题解
传送门 Solution 朴素算法 遍历所有点来选择询问点，每次删点后，暴力更新每个点的 。 时间复杂度 ，可通过 CCF 原数据。
CF1997F Chips on a Line 题解
传送门 Solution 设 为斐波那契数列的第 项， 为第 格的芯片数，那么当所有 确定时，无论怎么操作，都能保证 不变。因此所有情况都可以变成在第一格上放置若干个芯片，其它格子上没有芯片。
CF1993D Med-imize 题解
传送门 Solution 有一个显然的事实：被删除的块的大小一定是 的整数倍。因此我们不妨将原先的操作变成：挑选 个不重复的，大小为 的区间进行消除。
ARC181C Row and Column Order 题解
传送门 Solution 小清新构造题。 把每一格初始化为 ，接下来进行 次操作。第 次操作将第 行为 的格子全部变成 ，然后将第 列为 的格子全部变成 。
ARC181D Prefix Bubble Sort 题解
传送门 Solution 先用树状数组求逆序对，得出数组总共的逆序对数量 。设 和它前面的数共组成 对逆序对。 手玩样例后不难理解，操作 的本质，其实就是对所有 ，若 非零，则 。设执行操作 前有 个 非零，则执行操作后整个序列的逆序对数量减少 。
ABC362E Count Arithmetic Subsequences 题解
传送门 Solution 设 表示以 结尾，长度为 ，公差为 的等差数列数量。转移方程为
CF1223F Stack Exterminable Arrays 题解
传送门 Solution 从 到 枚举数字，对于当前数字，若与栈顶元素相同，则弹出栈顶元素，否则压入当前数字。随后将当前栈的状态通过哈希映射到 map 数组中。map 数组负责统计该状态出现的次数。
CF1982D Beauty of the mountains 题解
传送门 Solution 设有雪顶和无雪顶的山的总高度差为 。 通过计算代表山峰类型的 矩阵的二维前缀和，可以求出每个大小为 的方形区域中，两种类型的山的数量差。设每个方形的数量差分别为 ，则问题转换为方程
CF1989D Smithing Skill 题解
传送门 Solution 注意到每把武器只使用一种金属锻造，可以独立计算每种金属锭的贡献。 把问题转换为：有一个数 和 个操作，每个操作包含两个参数 、。当满足 ，则可执行操作 ，使 变为 。求可对 操作次数的最大值。
CF1982C Boring Day 题解
传送门 Description 有大小为 的数组 ，正整数 、。数组中相邻的多个数可绑定为一组。一个数只能在一个组内。求最多能有多少组满足组内元素之和在 内。
CF1986E Beautiful Array 题解
传送门 Description 给定一个长度为 的数组 和正整数 ，数组可任意排序且不占用操作次数。一次操作可将 。求最少多少次操作能将该数组变为回文数列，即保证 。
CF1986F Non-academic Problem 题解
传送门 Description 一张连通无向图，你可以剪断任意一条边。求剪断后存在路径的点对数的最小值。
KMP 字符串匹配：前缀函数与算法实现
对比朴素枚举，KMP 的思想是当匹配出现不一样的字符时，根据模式串当前子串的最大相同前后缀，将模式串的指针回退到最大相同前缀的末尾而非模式串的开头，从而优化时间复杂度。 记录子串最大相同前后缀长度的数组为 。下图展示了 的求解过程。
洛谷 P1470 最长前缀（Longest Prefix）题解
传送门 逐个对集合 中的字符串进行 KMP ，得出其在串 中的所有覆盖区间。问题转换成如何选取相互无重合部分的区间，以 串的左端点为起点，能覆盖最大的连续区域。 对区间以左端点为关键字，从小到大进行排序。定义数组 记录点 的左侧是否已被全部无重合地覆盖。枚举区间，若区间左端点的左边已全部覆盖，即 ，则该区间可…
C++ STL：set 与 multiset 用法
set 和 multiset 作为 C++ STL 的一部分，由红黑树实现，能保持容器内元素始终有序。其插入、查找、删除的时间复杂度均为 。两者区别在于 set 不允许有重复元素，multiset 允许有重复元素。 这里顺便提起 unordered_set 和 unordered_multiset，底层实现是…
CF1618G Trader Problem 题解
传送门 Solution 并查集。在一个 下能通过若干次交换相互得到的物品构成一个集合。 对 个询问升序排序，离线处理。 对大小为 的数组 进行排序，枚举 ，二分查找在哪个询问时合并 和 所在集合。 一个集合包含的元素必然在有序数组 中构成连续区间。
CF1971H ±1 题解
传送门 Solution 2-SAT 板子题。 设点 为 ， 为 。 对于每一列，最少要有两个 。这意味着，若一列中的一个数为 ，则其余两个数必定为 ，这就得到了两条有向边。我们分别假设一列中的三个数为 ，就得到了 条有向边。因为有 列，所以一共有 条有向边。然后跑 Tarjan，判断是否有 、 在同一强连通…
2-SAT：蕴含图建模与 Tarjan 算法
问题描述： 有 个 bool 变量，有个条件，如 为 true/flase 或 为 true/false 。求是否有方案能满足所有条件。构造出一组符合题意的解。 算法思路： 按照条件建立分层图，令 为 true， 为 false。
CF1971G XOUR 题解
传送门 Solution 注意到若 ，则 。我们将除以四后结果相同的元素分到同一组。显然，若 ， 可交换，， 可交换，则 ， 可交换。所以同一组内的所有元素可相互交换，即每一组均可内部排序。 将每一组排好序后，倒序枚举原数组，将每个元素替换成所在组内的最后一个元素，并将其从组内弹出。替换完成的新数组即为答案。
2022 蓝桥杯国赛 A 组：最大公约数题解
传送门 Solution 首先考虑数组内已经有 的情况。设此时有 个 ，则答案为 。 再考虑数组内没有 的情况。要想让整个数组变成 ，首先要先在某一段连续的区间内进行 操作，生成第一个 。然后通过 次 ，把数组的其余元素变成 。设生成第一个 的连续区间长度为 ，本题答案即为
2022 蓝桥杯国赛 A 组：选素数题解
传送门 Solution 设第一次操作的结果为 ，选定的素数为 。第二次操作的结果为 ，选定的素数为 。由题意可得 题目给出的是 ，所求为 的最小值。要使 最小，则要使 最小。因此找出 的最大质因数。再枚举 ，求出符合上文不等式的最小合法 ，可找出答案。
质数筛法：埃氏筛与线性筛
本文包括埃氏筛和线性筛。
康托展开与逆康托展开
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。本文内容包括逆康托展开。
错排问题：递推关系与通项公式
问题引入 封信从信封拆出，现将信放回，要求每封信都不能放到原来的信封里。求信放回的方案数。
四毛子算法（Method of Four Russians）：线性预处理 RMQ
前置知识 笛卡尔树 ST表 分块思想 状态压缩
树状数组求逆序对：离散化与计数
分析 用 对数组离散化，防止撑爆树状数组。 从左到右扫一遍数组。 表示左边有 个数。显然左边的数与 构成逆序对的数量为 减左边比 小的数的数量。 记得去重。
模拟退火：算法流程、调参与例题
具有某些优点的随机化算法，适用于最优解问题。 可以根据温度系数决定跳出当前最优解的概率，可以避免陷于局部最优解的情况。 定义最大温度，降温系数，最低温度，当前温度。当前温度初始化为最大温度，每次乘以降温系数，直到低于最低温度。
笛卡尔树：性质、单调栈建树与应用
笛卡尔树一是一棵二叉树。对于每个结点，有两个权值 。 若只看 ，整颗树为二叉查找树；只看 ，树为堆。 如图，点在数组中的位置号码为 ，元素内数字为 。
根号分治：阈值划分与例题
对于一类问题，有两种或多种不同的解法，均无法单独在时限内过题，但在特定的数据范围内优势明显。这时可以设定阈值，对于不同的数据范围，使用不同的算法，令总时间复杂度可以接受。 常见的阈值： 等。
网络流模板：最大流与最小费用最大流
网络流代码合集