# 省流急速版 :::warning[你可能会笑死，请斟酌后点开] j:100+100+70+40=310 s:100+0+8+3=113 ::: # day -inf S 模拟赛，打了两场，第一场 250pts，第二场 5pts，感觉良好。 # 10.31 周五，jx 下午三点才放学，我们火车也在三点，所以中午起床直…

挺有意思的题。 对于一只袋鼠，为了淘汰更多的敌人，它必须要走到所有能走到的位置，即走遍它所在联通块内所有位置。如果走遍之后只剩它一个，它就可以贡献答案。显然这样是最优的。 分析一下时间复杂度：可能有 $nm$ 只袋鼠，联通块大小为 $nm$，为了走遍联通块行走序列的长度为 $nm$，复杂度为 $O((nm)^3)$，显…

发现尼姑上没有太多 A* 学习笔记，来一发。 # 算法简介 A* 又称启发式搜索，能够解决带权有向图上的最短路问题。具体的，给出起点 $s$ 和终点 $t$，它能在**不劣于**（不是一定优于）优先队列 bfs（即 Dijkstra）的时间内求出从起点到终点的最短路。 我们先来思考，为什么 Dijkstra 会在有些情…

# 前言 :::info[关于文章渲染] 本文章使用了 2025 年 7 月的新版 Markdown 进行渲染。 ::: 非常好搜索，使我的大脑旋转。 :::info[前置知识] - IDDFS，迭代加深搜索 - 搜索剪枝 - 韦达定理 - 一元二次方程的判别式、求根公式等 - ~~一些卡常小技巧~~ ::: # 题意…

# 10.1 模拟赛 ## T1 ### pro 给出两个二进制数 $a,b$，问 $a\bmod b$ 是否为 $0$。 $a \le 2^{10^5},b \le 2^{200}$ ### sol 考虑除法竖式，显然除数在一直向右平移。那么对于被除数上一位 $1$，只能在当前位置解决。否则后面就够不到这一位了。 所…

# T1 简单 dfs，记录数组 $vis$ 表示一个点有没有被搜索过，从小到大遍历 $vis$，如果 $vis_i=0$ 则从 $i$ 开始遍历图，遍历时记录答案即可。 ```cpp #include using namespace std; int n,m; long long a[30005]; vector G…

# 前言 手搓蓝色数据结构，好开心。 # 题意 维护序列，支持区间加、区间统计比给定值小的数的个数。 # 题解 先对题意做一个简单转化：区间统计小于给定值的数的个数，就是求给定值在区间内排第几。这是主席树的经典应用“求区间 $k$ 大值”，复杂度 $O(n \log n)$。由于 $n$ 没多大，用分块的根号复杂度也能…

# 数论分块 以 $O(\sqrt n)$ 的复杂度求出 $\left \lfloor \frac{n}{1}\right \rfloor +\left \lfloor \frac{n}{2}\right \rfloor+\left \lfloor \frac{n}{3}\right \rfloor+\dots+\le…

昨天晚上想到的绝妙证法。 # 题意 $n$ 个数，把他们排成一排、首尾相接，求拼接后的数最大是多少。 # 分析 注意到题目中有拼接操作，考虑用 `string` 存数字。这样有一个好处，在两个字符串长度相同时，比较两个数字变成的字符串的字典序大小就相当于比较两个数的大小。 我们为了让结果尽可能大，就要保证大的数字在前，…

# 题意 $n$ 个数，把它们打乱、首尾相接，求相接后拼成的数字的最大值。 # 分析 首先有一些前置芝士。 - `string` 类型有 `+` 运算符，表示将两个字符串拼接；还可以用大于小于号比较两个字符串字典序的大小； - 字典序的大小是这么规定的： - 如果两个字符串长度不一样，那么在短的字符串后面补齐后，按字符…

终于遇到唐诗翻译题了，看 5 分钟没看懂。orz # 题意 $n$ 个人，每个人可以与别人配对，或者自己单独一人。与别人配对可以看做合并成了一个人。问：这些人排队一共有多少种方案？（对 $10^9+7$ 取模，$n \le 10^5$） 样例中 $n=3$ 时，有如下 $4$ 种情况： - 三个人都是单独一人 - 第一…

我们在平时写代码时总会遇到一些奇怪的问题需要挑错，这时一些挑错的技巧就很重要了。今天 CEXE 为大家带来了 $10$ 个挑错方面的小技巧，希望能帮到大家！ # 打断点 打断点在遇到奇怪的 RE 时有奇效！顾名思义，我们不知道哪里出现了 RE 时，可以在运行了一部分代码后输出什么，如果输出了这个东西，就说明前面没有 R…

# 题意 CEXE 有 $n$ 个字符串，他给了你 $n-1$ 个类似“字符串 $x$ 的后面是字符串 $y$”的信息。他想让你按顺序输出所有字符串。 # 分析 楼下代码又臭又长，我来发一个简单的双 `map` 做法。 具体地，记一个 $cnt$ 表示字符串出现的次数，一个 $to$ 表示每个关系。不难发现起点和重点在…

# 题意 一个 $n \times m$ 点矩形 $a$，给出每个点的权值。CEXE 从第一行出发往下走，每次可以从 $a_{i,j}$ 到达 $a_{i+1,j-1},a_{i+1,j},a_{i+1,j+1}$。到达一个点可以取走一个点的权值，求最大权值和。 # 分析 神秘动态规划。 定义 $dp_{i,j}$ 为…

# 题意 有 $n$ 支铅笔，每个铅笔有一个权值 $a_i$。现在要把所有铅笔放到若干个盒子里，每个盒子至少要放 $k$ 支铅笔。且一个盒子中任意两只铅笔的权值差的绝对值不能超过 $d$。问是否有可行放法。 # 题解 一眼动态规划。 注意到放的顺序对结果没有影响，考虑先对权值排序。而排序后，我们再把所有铅笔分成若干个区…

神秘模拟题。 这道题唯一的难点在于如何计算位置距离。显然位置距离就是两点中间的间隔数。假设两个人位置为 $a$ 和 $b$，那么位置距离可以用 $\min(\left | a-b\right |,n-\left|a-b \right|)$ 这个式子计算。 剩下的考验语言知识，请看代码。 ```cpp #include…

# 前言 最近学文化课学傻了，来复习一下数据结构。 能够实现区间操作的数据结构其实并不多，平常也就能用到这几个： - ST 表 - 树状数组 - 线段树 - 分块 今天我就只说这几个，方便新手入门。如果你是学数据结构的新手，一定一定要循序渐进，这几个数据结构是提高组很常考的考点。 # ST 表 - 前置知识：倍增，动态…

# 数论学习笔记 ## 前置知识 最大公约数：$\gcd(x,y)=\gcd(y \bmod x,x)$ 扩展欧几里得：$ax+by=\gcd(a,b)$ ## 常用定理 OI 中常用的公式其实主要只有三个： - 中国剩余定理 CRT - 卢卡斯定理 - 大步小步 BSGS 还有它们的扩展。 下面是公式。 - 中国剩余…

# 前言 我又来口胡新算法啦！这次写文章的时间比较仓促，可能漏洞百出，欢迎各位指正。orz ~~懒得 p 牢九门了，将就着看~~ # 小引子 大家学字符串算法时，有没有这样一种感受：算法难度两极分化。字符串哈希、字典树偏简单，其他算法又偏难。这启发了我：多项式算法都难度很大，难道没有难度小的算法吗？ 有的兄弟，有的。这…

# 前言 扫描线板子题。与 [P5490](https://www.luogu.com.cn/problem/P5490) 完全一样，可以当双倍经验。 # 题意 给你 $n$ 个矩形的四个角的坐标，把所有矩形拼成一个大的不规则图形，求这个不规则图形的面积。 # 题解 这道题目可以用扫描线轻松解决。 把问题简化，先看两个…

# 线下好友 [](https://www.luogu.com.cn/user/1238374) @untitled_…

# 前言 本文章为合集“年轻人的第一节算法课”中的第三篇文章。 - [年轻人的第一节算法课（1）——模拟、枚举、排序](https://www.luogu.com.cn/article/s666u0mr) - [年轻人的第一节算法课（2）——前缀和、差分、二分查找](https://www.luogu.com.cn/a…

# 前言 本文章为合集“年轻人的第一节算法课”中的第二篇文章。 - [年轻人的第一节算法课（1）——模拟、枚举、排序](https://www.luogu.com.cn/article/s666u0mr) - [年轻人的第一节算法课（2）——前缀和、差分、二分查找](https://www.luogu.com.cn/a…

# 前言 本文章为合集“年轻人的第一节算法课”中的第一篇文章。 - [年轻人的第一节算法课（1）——模拟、枚举、排序](https://www.luogu.com.cn/article/s666u0mr) - [年轻人的第一节算法课（2）——前缀和、差分、二分查找](https://www.luogu.com.cn/a…

[原题](https://www.luogu.com.cn/problem/P5170)一共有三问： - 求 $F(a,b,c,n)=\sum\limits_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor$ - 求 $G(a,b,c,n)=\sum\limits_{i=0}^{n} \…

- 原作者：@[Lovelace_qwq](https://www.luogu.com.cn/user/1223290) - 搬运：@[TFHS_arsc](https://www.luogu.com.cn/user/821849) - 撰文：@[\_\_CrossBow_EXE__](https://www.luog…

# 前言 作者 @\_\_CrossBow_EXE__ 在 2025.5.19 学完了 FFT 后，感觉脑子不够用，因此作此文章。 > FFT 太强了！ # 前置芝士 - 复数 - 多项式 - 函数 不了解也没关系，马上就会介绍。 # 复数 众所周知，$\sqrt {-1}=i$。$i$ 称作虚数单位。形似 $a+bi…

# 前言 自从我写完那一篇[介绍冷门数据结构的文章](https://www.luogu.com.cn/article/fy2h5lpz)后，大家都对文章做出了评论。但也有很多人问我： > 主播主播，你的 C++ 扩展头文件确实很强，但还是太吃大脑内存了，有没有什么简单又强势的头文件推荐一下？ 有的兄弟，有的。这样简单…

# 前言 这题自从被我 hack 之后已经过去 3 天了，居然还能交题解，再补一个分块做法。 # 题解 序列是无序的，先排个序。排完序后，把序列分成 $\sqrt n$ 块，每一块都找出一个最大值。因为序列有序，所以最大值肯定是这一块的最后一个数。 如果我们使用暴力做法，我们需要统计每头奶牛后面有多少奶牛与这头奶牛距离…

# 前言 在我和好友 [UCPP](https://www.luogu.com.cn/user/1238374) 的热血沸腾的[组合技](https://www.luogu.com.cn/discuss/1082475)之后，这道题所有题解都被我们叉了，所以抓紧补一篇题解。 # 题解 先来想暴力做法，再考虑如何优化。…