bnuzh-weekmatch-10
BNUZH-ACM 周赛 Round 10 - 洛谷 计算机科学教育新生态
03. Latest Posts
bnuzh-weekmatch-9
BNUZH-ACM 周赛 Round 9 - 洛谷 计算机科学教育新生态
bnuzh_weekmatch_7
BNUZH-ACM 周赛 Round 7 - 洛谷 计算机科学教育新生态
2025 bnuzh 周赛-6
BNUZH-ACM 周赛 Round 6 - 洛谷 计算机科学教育新生态
bnuzh 2025 周赛-5
BNUZH-ACM 周赛 Round 5 - 洛谷 计算机科学教育新生态
2025 bnuzh 周赛-4
BNUZH-ACM 周赛 Round 4 - 洛谷 计算机科学教育新生态
2025 bnuzh 周赛-3
BNUZH-ACM 周赛 Round 3 - 洛谷 计算机科学教育新生态
2025 bnuzh 周赛-2
比赛链接
2025 bnuzh 周赛-1
BNUZH-ACM 周赛 Round 1 - 洛谷 计算机科学教育新生态
第十五届蓝桥杯国赛 Python B组 解题报告
A Solution dfs 枚举所有题目的选择情况。状态数一共为 。答案为 。
概率论 笔记
判断题
BNU Zhuhai 25春 实变函数期中考试
<center任课教师：薛庆营       卷面总分：100分       考试时长：100分钟</center 说明 - 第六、七题和第八、九题为两组选做题，选答一道即可。 - 第十一题为附加题。 - 课本原题网络上参...
第十四届蓝桥杯国赛 Python A组 解题报告
A 跑步计划 Solution datetime 库中 的 weekday 可以获取某一天的星期信息。
2023 蓝桥杯省赛 Python A组 解题报告
A 特殊日期 Solution 利用 Python 系统库 datetime 可以省去日期枚举中的细节处理。
第二讲：搜索与优化技巧
Link 蓝桥杯 第二讲：搜索与优化技巧 - 题单 - 洛谷 计算机科学教育新生态 提醒：本文代码均可点击左上角折叠，希望能帮助您优化阅读体验。 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，然后从子结点开始一个一个地求 ，时间复杂度为 。
线性基
Link 线性基 - OI Wiki oi-wiki.org 【模板】线性基 - 洛谷
CCPC2024网络赛 E 随机过程
传送门 Solution 设最大节点数为 ，因为第 层最多有 个节点，所以有 。
CCPC2024网络赛 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 次操作可将一个 变为 或 。有 的方法预处理出 的正约数个数。
UVA1316 Supermarket
传送门 Solution 对物品以过期时间（从小到大）为第一关键字，价格（从大到小）为第二关键字进行排序，然后开一个按照物品价值排序的小根堆。
luoguP2391 白雪皑皑
传送门 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 长度为 ，下标从 开始。
luoguP10894 虚树
传送门 Solution 树上 dp，设 为以 为根的子树中好的非空子集数量。若 为叶节点， 则 。下面假设 非叶节点， 为 的子节点：
CF2001C Guess The Tree
传送门 Solution 初始化 ，其余 ，? 1 2 加入询问队列。 每次从队头取出询问 ? u v （保证 ，），返回的结果是 ， 路径的中点 。
luoguP10893 城市化发展委员会
传送门 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 进制下不进位加法的本质是，若两数第 位相加后超过了 ，则减去 。所以 时问题有解，且当 时，有 。
二元一次不定方程（exgcd）
前置知识 扩展欧几里得算法（辗转相除法） 对 ，有
ABC366F Maximum Composition
传送门 Solution 设 ，。若 ，则 。又因为 ，移项得。
HDU7528 cats 的电脑中毒
传送门 Solution 设两个二进制串有 位不同，那么它们的距离 。设与串 的距离为 ，题目即求使得 最大的串。
【CSP 202312】树上搜索
传送门 Solution 朴素算法 遍历所有点来选择询问点，每次删点后，暴力更新每个点的 。 时间复杂度 ，可通过 CCF 原数据。
CF1997F Chips on a Line
传送门 Solution 设 为斐波那契数列的第 项， 为第 格的芯片数，那么当所有 确定时，无论怎么操作，都能保证 不变。因此所有情况都可以变成在第一格上放置若干个芯片，其它格子上没有芯片。
CF1993D Med-imize
传送门 Solution 有一个显然的事实：被删除的块的大小一定是 的整数倍。因此我们不妨将原先的操作变成：挑选 个不重复的，大小为 的区间进行消除。
【原神】 胡芙夜钟
队伍配置 最低配置 芙宁娜 1+0，其余 0+0，共 5 金。 0 命芙不作推荐，不如胡行钟夜。
ARC181C Row and Column Order
传送门 Solution 小清新构造题。 把每一格初始化为 ，接下来进行 次操作。第 次操作将第 行为 的格子全部变成 ，然后将第 列为 的格子全部变成 。
ARC181D Prefix Bubble Sort
传送门 Solution 先用树状数组求逆序对，得出数组总共的逆序对数量 。设 和它前面的数共组成 对逆序对。 手玩样例后不难理解，操作 的本质，其实就是对所有 ，若 非零，则 。设执行操作 前有 个 非零，则执行操作后整个序列的逆序对数量减少 。
questions_resource
橙题 Collatz Conjecture - 洛谷 计算机科学教育新生态 luogu.com.cn 黄题 XOUR - 洛谷 计算机科学教育新生态 luogu.com.cn Boring Day - 洛谷 计算机科学教育新生态 luogu.com.cn 绿题 Beauty of the mountains - 洛谷 计算机科学教育新生态 luogu.com...
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 的思想是当匹配出现不一样的字符时，根据模式串当前子串的最大相同前后缀，将模式串的指针回退到最大相同前缀的末尾而非模式串的开头，从而优化时间复杂度。 记录子串最大相同前后缀长度的数组为 。下图展示了 的求解过程。
USACO2.3 最长前缀 Longest Prefix
传送门 逐个对集合 中的字符串进行 KMP ，得出其在串 中的所有覆盖区间。问题转换成如何选取相互无重合部分的区间，以 串的左端点为起点，能覆盖最大的连续区域。 对区间以左端点为关键字，从小到大进行排序。定义数组 记录点 的左侧是否已被全部无重合地覆盖。枚举区间，若区间左端点的左边已全部覆盖，即 ，则该区间可选取，使 。同时更新答案 。
Set 和 multiset
简介 set 和 multiset 作为 C++ STL 的一部分，由红黑树实现，能保持容器内元素始终有序。其插入、查找、删除的时间复杂度均为 。两者区别在于 set 不允许有重复元素，multiset 允许有重复元素。 这里顺便提起 unordered_set 和 unordered_multiset，底层实现是哈希表，容器内元素无序。插入、查找、删除的时...
题解 CF1618G Trader Problem
传送门 Solution 并查集。在一个 下能通过若干次交换相互得到的物品构成一个集合。 对 个询问升序排序，离线处理。 对大小为 的数组 进行排序，枚举 ，二分查找在哪个询问时合并 和 所在集合。 一个集合包含的元素必然在有序数组 中构成连续区间。
题解 CF1971H ±1
传送门 Solution 2-SAT 板子题。 设点 为 ， 为 。 对于每一列，最少要有两个 。这意味着，若一列中的一个数为 ，则其余两个数必定为 ，这就得到了两条有向边。我们分别假设一列中的三个数为 ，就得到了 条有向边。因为有 列，所以一共有 条有向边。然后跑 Tarjan，判断是否有 、 在同一强连通分量内即可。
2-SAT
问题描述： 有 个 bool 变量，有个条件，如 为 true/flase 或 为 true/false 。求是否有方案能满足所有条件。构造出一组符合题意的解。 算法思路： 按照条件建立分层图，令 为 true， 为 false。
题解 CF1971G XOUR
传送门 Solution 注意到若 ，则 。我们将除以四后结果相同的元素分到同一组。显然，若 ， 可交换，， 可交换，则 ， 可交换。所以同一组内的所有元素可相互交换，即每一组均可内部排序。 将每一组排好序后，倒序枚举原数组，将每个元素替换成所在组内的最后一个元素，并将其从组内弹出。替换完成的新数组即为答案。
【蓝桥杯 2022 国 A】 最大公约数
传送门 Solution 首先考虑数组内已经有 的情况。设此时有 个 ，则答案为 。 再考虑数组内没有 的情况。要想让整个数组变成 ，首先要先在某一段连续的区间内进行 操作，生成第一个 。然后通过 次 ，把数组的其余元素变成 。设生成第一个 的连续区间长度为 ，本题答案即为
题解 [蓝桥杯 2022 国 A] 选素数
传送门 Solution 设第一次操作的结果为 ，选定的素数为 。第二次操作的结果为 ，选定的素数为 。由题意可得 题目给出的是 ，所求为 的最小值。要使 最小，则要使 最小。因此找出 的最大质因数。再枚举 ，求出符合上文不等式的最小合法 ，可找出答案。
质数筛法
本文包括埃氏筛和线性筛。
康托展开
简介 康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。本文内容包括逆康托展开。
错排问题
问题引入 封信从信封拆出，现将信放回，要求每封信都不能放到原来的信封里。求信放回的方案数。
Method of Four Russians
前置知识 - 笛卡尔树 - ST表 - 分块思想 - 状态压缩
树状数组求逆序对
分析 用 对数组离散化，防止撑爆树状数组。 从左到右扫一遍数组。 表示左边有 个数。显然左边的数与 构成逆序对的数量为 减左边比 小的数的数量。 记得去重。
模拟退火
具有某些优点的随机化算法，适用于最优解问题。 可以根据温度系数决定跳出当前最优解的概率，可以避免陷于局部最优解的情况。 定义最大温度，降温系数，最低温度，当前温度。当前温度初始化为最大温度，每次乘以降温系数，直到低于最低温度。
笛卡尔树
定义 笛卡尔树一是一棵二叉树。对于每个结点，有两个权值 。 若只看 ，整颗树为二叉查找树；只看 ，树为堆。 如图，点在数组中的位置号码为 ，元素内数字为 。
根号分治
简介 对于一类问题，有两种或多种不同的解法，均无法单独在时限内过题，但在特定的数据范围内优势明显。这时可以设定阈值，对于不同的数据范围，使用不同的算法，令总时间复杂度可以接受。 常见的阈值： 等。
网络流模板
网络流代码合集