03. 最新文章

bnuzh-weekmatch-10

BNUZH-ACM 周赛 Round 10 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/309684

bnuzh-weekmatch-9

BNUZH-ACM 周赛 Round 9 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/307236

bnuzh_weekmatch_7

BNUZH-ACM 周赛 Round 7 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/295792problems

2025 bnuzh 周赛-6

BNUZH-ACM 周赛 Round 6 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/294160

bnuzh 2025 周赛-5

BNUZH-ACM 周赛 Round 5 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/292476

2025 bnuzh 周赛-4

BNUZH-ACM 周赛 Round 4 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/290567

2025 bnuzh 周赛-3

BNUZH-ACM 周赛 Round 3 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/289012problems

2025 bnuzh 周赛-1

BNUZH-ACM 周赛 Round 1 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/contest/282997problems

BNU Zhuhai 25春 实变函数期中考试

<center>任课教师：薛庆营&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;卷面总分：100分&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;考试时长：100分钟</center> 说明 - 第六、七题和第八、九题为两组选做题，选答一道即可。 - 第十一题为附加题。 - 课本原题网络上参考较多，在此不再重复。 - 部分证明...

第二讲：搜索与优化技巧

Link 蓝桥杯\ 第二讲：搜索与优化技巧 - 题单 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/training/714047problems 提醒：本文代码均可点击左上角折叠，希望能帮助您优化阅读体验。 Solution

2024 蓝桥杯省赛 python A组 解题报告

题目传送门https://www.lanqiao.cn/paper/4403/result/ A 拼正方形 Solution 二分答案。根据题目所求为满足条件的最大值，因此二分枚举所得正方形的最大边长，并检验是否能拼成。

CF2001D Longest Max Min Subsequence

Problem - 2001D - Codeforceshttps://codeforces.com/problemset/problem/2001/D Solution 所求序列长度为 a 中的元素种类数。小根堆 L 维护每种元素最后一次出现的位置。

CF837D Round Subset

Round Subset - 洛谷 | 计算机科学教育新生态 luogu.com.cnhttps://www.luogu.com.cn/problem/CF837D Solution 问题转化为：设取的 k 个数的因子中共有 x 个 2，y 个 5。选择取数的方案，使得 \min\{x,y\} 最大化。

CF372C Watching Fireworks is Fun

Watching Fireworks is Fun - 洛谷 | 计算机科学教育新生态 luogu.com.cnhttps://www.luogu.com.cn/problem/CF372C Solution 定义 F_{i,j} 表示在位置 j 观看烟花 i 时，目前开心值的最大值。设 len=dt_i-t_{i-1}，则 F_{i,j}=\max\{F_{i-1,k}+b_i-|a_i-j|\...

CF1187E Tree Painting

Tree Painting - 洛谷 | 计算机科学教育新生态 luogu.com.cnhttps://www.luogu.com.cn/problem/CF1187E Solution 容易得出结论：可选择的只有第一个染色点，且不妨将该点视作根结点。该点确定后，本题答案也就确定了为所有子树的大小之和。现在要求的是如何选择根结点，使得答案最大。

CF208E Blood Cousins

Blood Cousins - 洛谷 | 计算机科学教育新生态 luogu.com.cnhttps://www.luogu.com.cn/problem/CF208E Solution 用倍增可以快速求出 v_i 的 p_i 级祖先 u_i，然后对 u_i 打上标记，表示它与询问 i 有关。标记可用 vector 维护。

CF600E Lomsat gelral

Lomsat gelral - 洛谷 | 计算机科学教育新生态 luogu.com.cnhttps://www.luogu.com.cn/problem/CF600E Solution 树上启发式合并模板题。 考虑暴力做法：设以 i 为根的子树的答案为 A_i，每次求 A_i 都重新遍历整棵子树。选择从 1 开始往下 dfs，然后从子结点开始一个一个地求 A_i，时间复杂度为 On^2。

线性基

Link 线性基 - OI Wiki oi-wiki.orghttps://oi-wiki.org/math/linear-algebra/basis/贪心法 【模板】线性基 - 洛谷https://www.luogu.com.cn/problem/P3812

CCPC2024网络赛 E 随机过程

传送门https://codeforces.com/gym/105336 Solution 设最大节点数为 M，因为第 i 层最多有 26^i 个节点，所以有 M=\sum \limits ^m_{i=0}\min \{26^i,n\}。

CCPC2024网络赛 D 编码器-解码器

传送门https://codeforces.com/gym/105336 Solution 注意到 S'_n 由左右两个相同的 S'_{n-1} 夹着一个新字符 S_n 拼接而来。所以可以尝试从 S'_{n-1} 的答案转移得到 S'_n 的答案。

CF767C Garland

传送门https://www.luogu.com.cn/problem/CF767C Solution 设所有节点的权重之和为 tot，若 tot 不能被 3 整除，则问题无解。

CF337D Book of Evil

传送门https://www.luogu.com.cn/problem/CF337D Solution 设 a_u 表示以 u 为根的子树中，离 u 最远的重要结点，b_u 表示以 u 为根的子树中，离 u 次远的重要结点，c_u 表示以 u 为根的子树外离 u 最远的结点。

CF1132F Clear the String

传送门https://www.luogu.com.cn/problem/CF1132F Solution 区间 dp。设 F_{l,r} 为删去区间 l,r 的最小代价。显然，一个包含两种或以上字符的区间，它代价最小的删去方法中，一定存在一个断点将区间分成左右两半，使得这两个区间是各自删去的。

CF383C Propagating tree

传送门https://www.luogu.com.cn/problem/CF383C Solution 一棵子树中的所有点的 dfs 序必定连续，因此先 dfs 求出每个点的 dfs 序和深度，以及该子树的点的 dfs 序的左右边界。

CF432D Prefixes and Suffixes

传送门https://www.luogu.com.cn/problem/CF432D Solution 使用扩展 KMP 求出 z_i。设字符串 S 长度为 n，下标从 0 开始。某前缀同时也是后缀，当且仅当 i+z_i=n。

CF438D The Child and Sequence

传送门https://www.luogu.com.cn/problem/CF438D Solution 设 m=n\bmod p，那么一定有 m\le \dfrac{n}{2}。因此每个点最多经过 \log a_i 次取余就会变成 1。

CF2B The least round way

传送门https://www.luogu.com.cn/problem/CF2B Solution 每个 10 都是由一对 2、5 相乘而得。设 F_{i,j,0} 为点 1,1 到 i,j 路上最少 2 的数量，F_{i,j,1} 为最少 5 的数量。答案即为 ans=\min\{F_{n,n,0},F_{n,n,1}\}。

CF920F SUM and REPLACE

传送门https://www.luogu.com.cn/problem/CF920F Solution 对于 1\le a_i \le 10^6，不超过 6 次操作可将一个 a_i 变为 1 或 2。有 On\log n 的方法预处理出 1\sim 10^6 的正约数个数。

luoguP2391 白雪皑皑

传送门https://www.luogu.com.cn/problem/P2391 Solution 倒序染色使得每个点被染色后，可从序列中删去。使用单向链表，设 nxt_i 为点 i 在链表中指向的下一个点。设当前染色区间为 L,R，点 i 染色结束后，令 nxt_i=nxt_R。

UVA1316 Supermarket

传送门https://www.luogu.com.cn/problem/UVA1316 Solution 对物品以过期时间（从小到大）为第一关键字，价格（从大到小）为第二关键字进行排序，然后开一个按照物品价值排序的小根堆。

CF1200E Compress Words

传送门https://www.luogu.com.cn/problem/CF1200E Solution 设当前待合并的串为 A，已合并的串为 B。若 |A|\ge |B|，则 C=A+B。否则 C 等于 A 与 B 长度为 |A| 的后缀拼接而成的字符串。对 C 进行 KMP，求出最大相同前后缀长度 nxt_{|C|}。把 A 的相应长度后缀并入 B 后面即可。

CF242E XOR on Segment

传送门https://www.luogu.com.cn/problem/CF242E Solution 观察到 a_i\le 10^6 <2^{20}，拆位后数组变成 20 条长度为 n 的 01 串。开二十棵线段树分别维护这些串的区间和。

CF2003D2 Turtle and a MEX Problem (Hard Version)

传送门https://codeforces.com/contest/2003/problem/D2 Solution 设第 i 个序列最小没出现的非负整数为 v_i，次小没出现的非负整数为 u_i。从 u_i 向 v_i 连有向边。由于 u_i>v_i，最后得到的是一张有向无环图，且每个点之间不一定连通。

CF1627D Not Adding

传送门https://www.luogu.com.cn/problem/CF1627D Solution 注意数据范围。用桶记录某数是否在数组内出现。从 10^6 枚举 x 到 1，检查是否能生成 x。若所有在数组内的 x 的倍数的最大公约数等于 x，则可生成 x。 设数组内最大的数为 N，时间复杂度 ON\log N

CF19B Checkout Assistant

传送门https://www.luogu.com.cn/problem/CF19B Solution 若设 F_a 为选择付款的商品的 t_i 之和为 a 时，支付的最小金额，k 为这些商品的数量。那么只有 a\ge n-k 时，F_a 才为一种合法的答案。

CF126B Password

传送门https://www.luogu.com.cn/problem/CF126B Solution 1 考虑使用 Z 函数（exkmphttps://oi-wiki.org/string/z-func/）且设 S 长度为 n，下标从 0 开始。

luoguP10894 虚树

传送门https://www.luogu.com.cn/problem/P10894 Solution 树上 dp，设 f_u 为以 u 为根的子树中好的非空子集数量。若 u 为叶节点， 则 f_u=1。下面假设 u 非叶节点，v 为 u 的子节点：

CF2001C Guess The Tree

传送门https://codeforces.com/contest/2001/problem/C Solution 初始化 V_1=1，其余 V_i=0，? 1 2 加入询问队列。 每次从队头取出询问 ? u v （保证 V_u=1，V_v=0），返回的结果是 u，v 路径的中点 p。

ABC367E Permute K times

传送门https://www.luogu.com.cn/problem/AT_abc367_e Solution 设 f_{i,k} 表示经过 2^k 次操作后，位置 i 上的数字为 a_{f_{i,k}}。初始化 f_{i,0}=x_i。转移方程 f_{i,j}=f_{f_{i,j-1},j-1}

ABC367F Rearrange Query

传送门https://www.luogu.com.cn/problem/AT_abc367_f Solution 用 mt19937 重新给 1\sim 2\times 10^5 随机赋权为 1\sim 10^9+7 中的一个数，然后判断两个区间内的元素之和是否相等即可。区间和保证在 long long 范围内。

ABC367D Pedometer

传送门https://www.luogu.com.cn/problem/AT_abc367_d Solution 首先拆环成链，令 a_{i+n}=a_i。 然后求出 a_i 的前缀和 s_i。当 s_i\equiv s_j\pmod M 时，说明 M | a_{i+1}+\cdot \cdot \cdot + a_j。

CF1998C Perform Operations to Maximize Score

传送门https://codeforces.com/contest/1998/problem/C Solution 取出的 a_i 若 i>\lfloor \dfrac{n}{2} \rfloor，则 \text{median}c_i=a_{\lfloor \frac{n}{2} \rfloor}。否则 \text{median}c_i=a_{\lfloor \frac{n}{2} \rfloor...

HDU7523 cats 的 k-xor

传送门https://vjudge.net/problem/HDU-7523 Solution k 进制下不进位加法的本质是，若两数第 i 位相加后超过了 k^i，则减去 k^i。所以 a+b \ge c 时问题有解，且当 a+b>c 时，有 k|a+b-c。

ABC366F Maximum Composition

传送门https://www.luogu.com.cn/problem/AT_abc366_f Solution 设 f_1x=a_1x+b_1，f_2x=a_2x+b_2。若 f_1f_2x<f_2f_1x，则 a_1b_2+a_1<a_2b_1+b_2。又因为 b_1,b_2>0，移项得\dfrac{a_1-1}{b_1}<\dfrac{a_2-1}{b_2}。

HDU7528 cats 的电脑中毒

传送门https://acm.hdu.edu.cn/showproblem.php?pid=7528 Solution 设两个二进制串有 k 位不同，那么它们的距离 d=k。设与串 i 的距离为 d_i，题目即求使得 \min\{d_1,d_2,d_3\} 最大的串。

【CSP 202312】树上搜索

传送门https://www.acwing.com/problem/content/5420/ Solution 朴素算法 遍历所有点来选择询问点，每次删点后，暴力更新每个点的 w_{\delta}。 时间复杂度 Omn^2，可通过 CCF 原数据。

CF1997F Chips on a Line

传送门https://www.luogu.com.cn/problem/CF1997F Solution 设 fib_i 为斐波那契数列的第 i 项，c_i 为第 i 格的芯片数，那么当所有 c_i 确定时，无论怎么操作，都能保证 k=\sum fib_ic_i 不变。因此所有情况都可以变成在第一格上放置若干个芯片，其它格子上没有芯片。

CF1993D Med-imize

传送门https://www.luogu.com.cn/problem/CF1993D Solution 有一个显然的事实：被删除的块的大小一定是 k 的整数倍。因此我们不妨将原先的操作变成：挑选 \lfloor \dfrac{n-1}{m} \rfloor 个不重复的，大小为 k 的区间进行消除。

【原神】 胡芙夜钟

队伍配置 最低配置 芙宁娜 1+0，其余 0+0，共 5 金。 0 命芙不作推荐，不如胡行钟夜。

ARC181C Row and Column Order

传送门https://atcoder.jp/contests/arc181/tasks/arc181_c Solution 小清新构造题。 把每一格初始化为 -1，接下来进行 n 次操作。第 i 次操作将第 p_i 行为 -1 的格子全部变成 0，然后将第 q_{n-i+1} 列为 -1 的格子全部变成 1。

ARC181D Prefix Bubble Sort

传送门https://www.luogu.com.cn/problem/AT_arc181_d Solution 先用树状数组求逆序对，得出数组总共的逆序对数量 tot。设 a_i 和它前面的数共组成 inv_i 对逆序对。 手玩样例后不难理解，操作 i 的本质，其实就是对所有 j\le i，若 a_j 非零，则 a_j-1。设执行操作 i 前有 m 个 a_j 非零，则执行操作后整个序列的逆序对...

questions_resource

橙题 Collatz Conjecture - 洛谷 | 计算机科学教育新生态 luogu.com.cnhttps://www.luogu.com.cn/problem/CF1982B 黄题 XOUR - 洛谷 | 计算机科学教育新生态 luogu.com.cnhttps://www.luogu.com.cn/problem/CF1971G Boring Day - 洛谷 | 计算机科学教育新生态...

ABC362E Count Arithmetic Subsequences

传送门https://www.luogu.com.cn/problem/AT_abc362_e Solution 设 F_{i,len, d} 表示以 a_i 结尾，长度为 len，公差为 d 的等差数列数量。转移方程为 F_{i,len,d}=\sum\limits_{j=1}^{i-1} F_{j,len-1,d}

CF1223F Stack Exterminable Arrays

传送门https://www.luogu.com.cn/problem/CF1223F Solution 从 1 到 n 枚举数字，对于当前数字，若与栈顶元素相同，则弹出栈顶元素，否则压入当前数字。随后将当前栈的状态通过哈希映射到 map 数组中。map 数组负责统计该状态出现的次数。

CF1982D Beauty of the mountains

传送门https://www.luogu.com.cn/problem/CF1982D Solution 设有雪顶和无雪顶的山的总高度差为 c。 通过计算代表山峰类型的 01 矩阵的二维前缀和，可以求出每个大小为 k\times k 的方形区域中，两种类型的山的数量差。设每个方形的数量差分别为 a_i，则问题转换为方程

CF1989D Smithing Skill

传送门https://www.luogu.com.cn/problem/CF1989D Solution 注意到每把武器只使用一种金属锻造，可以独立计算每种金属锭的贡献。 把问题转换为：有一个数 x 和 n 个操作，每个操作包含两个参数 a_i、b_i。当满足 x\le a_i，则可执行操作 i，使 x 变为 x-a_i-b_i。求可对 x 操作次数的最大值。

CF1982C Boring Day

传送门https://codeforces.com/contest/1982/problem/C Description 有大小为 n 的数组 a_i，正整数 l、r。数组中相邻的多个数可绑定为一组。一个数只能在一个组内。求最多能有多少组满足组内元素之和在 l,r 内。

CF1986E Beautiful Array

传送门https://www.luogu.com.cn/problem/CF1986E Description 给定一个长度为 n 的数组 {a_i}和正整数 k，数组可任意排序且不占用操作次数。一次操作可将 a_i=a_i+k。求最少多少次操作能将该数组变为回文数列，即保证 a_i=a_{n - i + 1}。

CF1986F Non-academic Problem

传送门https://www.luogu.com.cn/problem/CF1986F Description 一张连通无向图，你可以剪断任意一条边。求剪断后存在路径的点对数的最小值。

KMP

简介 对比朴素枚举，KMP 的思想是当匹配出现不一样的字符时，根据模式串当前子串的最大相同前后缀，将模式串的指针回退到最大相同前缀的末尾而非模式串的开头，从而优化时间复杂度。 记录子串最大相同前后缀长度的数组为 next_i。下图展示了 next_i 的求解过程。

USACO2.3 最长前缀 Longest Prefix

传送门https://www.luogu.com.cn/problem/P1470 逐个对集合 P 中的字符串进行 KMP ，得出其在串 S 中的所有覆盖区间。问题转换成如何选取相互无重合部分的区间，以 S 串的左端点为起点，能覆盖最大的连续区域。 对区间以左端点为关键字，从小到大进行排序。定义数组 b_i 记录点 i 的左侧是否已被全部无重合地覆盖。枚举区间，若区间左端点的左边已全部覆盖，即 b...

Set 和 muitiset

简介 set 和 multiset 作为 C++ STL 的一部分，由红黑树实现，能保持容器内元素始终有序。其插入、查找、删除的时间复杂度均为 \Theta\log n。两者区别在于 set 不允许有重复元素，multiset 允许有重复元素。 这里顺便提起 unordered_set 和 unordered_multiset，底层实现是哈希表，容器内元素无序。插入、查找、删除的时间复杂度最好为 ...

题解 CF1618G Trader Problem

传送门https://www.luogu.com.cn/problem/CF1618G Solution 并查集。在一个 k 下能通过若干次交换相互得到的物品构成一个集合。 对 q 个询问升序排序，离线处理。 对大小为 n+m 的数组 a_n 进行排序，枚举 a_i，二分查找在哪个询问时合并 a_i 和 a_{i+1} 所在集合。 一个集合包含的元素必然在有序数组 a_n 中构成连续区间。

题解 CF1971H ±1

传送门https://www.luogu.com.cn/problem/CF1971H Solution 2-SAThttp://qianianxy.cn/2024/05/11/2-SAT/ 板子题。 设点 u_{i} 为 i=-1，u_{i+n} 为 i=1。 对于每一列，最少要有两个 1。这意味着，若一列中的一个数为 -1，则其余两个数必定为 1，这就得到了两条有向边。我们分别假设一列中的三个...

2-SAT

问题描述： 有 n 个 bool 变量，有m个条件，如 \lfloor x_i 为 true/flase 或 x_j 为 true/false \rfloor。求是否有方案能满足所有条件。构造出一组符合题意的解。 算法思路： 按照条件建立分层图，令 x_i 为 true，x_{i+n} 为 false。

题解 CF1971G XOUR

传送门https://codeforces.com/contest/1971/problem/G Solution 注意到若 a_i \oplus a_j < 4，则 a_i>>2=a_j>>2。我们将除以四后结果相同的元素分到同一组。显然，若 a_i，a_j 可交换，a_j，a_k 可交换，则 a_i，a_k 可交换。所以同一组内的所有元素可相互交换，即每一组均可内部排序。 将每一组排好序后，倒...

【蓝桥杯 2022 国 A】 最大公约数

传送门https://www.luogu.com.cn/problem/P8792 Solution 首先考虑数组内已经有 1 的情况。设此时有 n_1 个 1，则答案为 n-n_1。 再考虑数组内没有 1 的情况。要想让整个数组变成 1，首先要先在某一段连续的区间内进行 \gcd 操作，生成第一个 1。然后通过 n-1 次 \gcd，把数组的其余元素变成 1。设生成第一个 1 的连续区间长度为 ...

题解 [蓝桥杯 2022 国 A] 选素数

传送门https://www.luogu.com.cn/problem/P8795 Solution 设第一次操作的结果为 x，选定的素数为 p_1。第二次操作的结果为 y，选定的素数为 p_2。由题意可得 x-p_1+1\le y-p_2<x\le y 题目给出的是 y，所求为 x-p_1+1 的最小值。要使 x 最小，则要使 y-p_2 最小。因此找出 y 的最大质因数。再枚举 p_1，求出符...

质数筛法

本文包括埃氏筛和线性筛。

康托展开

简介 康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。本文内容包括逆康托展开。

错排问题

问题引入 n 封信从信封拆出，现将信放回，要求每封信都不能放到原来的信封里。求信放回的方案数。

Method of Four Russians

前置知识 - 笛卡尔树http://qianianxy.cn/2024/05/05/%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91/ - ST表https://www.luogu.com.cn/problem/P3865 - 分块思想 - 状态压缩

树状数组求逆序对

分析 用 \text{map} 对数组离散化，防止撑爆树状数组。 从左到右扫一遍数组。i-1 表示左边有 i 个数。显然左边的数与 a_i 构成逆序对的数量为 i-1 减左边比 a_i 小的数的数量。 记得去重。

模拟退火

具有某些优点的随机化算法，适用于最优解问题。 可以根据温度系数决定跳出当前最优解的概率，可以避免陷于局部最优解的情况。 定义最大温度，降温系数，最低温度，当前温度。当前温度初始化为最大温度，每次乘以降温系数，直到低于最低温度。

笛卡尔树

定义 笛卡尔树一是一棵二叉树。对于每个结点，有两个权值 k,w。 若只看 k，整颗树为二叉查找树；只看 w，树为堆。 如图，点在数组中的位置号码为 k，元素内数字为 w。

根号分治

简介 对于一类问题，有两种或多种不同的解法，均无法单独在时限内过题，但在特定的数据范围内优势明显。这时可以设定阈值，对于不同的数据范围，使用不同的算法，令总时间复杂度可以接受。 常见的阈值：\sqrt{n} 等。