下集传送门：线段树 树的类： 二叉树变种： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 输入树： 先输入元素个数N，然后输入N个元素，后面N行每行输入两个正整数A、B表示输入的第B项是第A项的子节点。（根节点是第0项，不计入输入中） 例如: 输入为： 二叉树变种： 先输入元素个数N，然后输入N个元素，后面N行每行输入三个正整数A、J和B。 如果J为0，表示输入的第B项是第A项的左子节点，如果J为1，则表示输入的第B项是第A项的右子节点。（根节点是第0项，不计入输入中） 例如: 输入为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 展示树的结构： 二叉树变种： 例如: 输出为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二叉树前序遍历： 例如: 输出为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二叉树中序遍历： 例如: 输出为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二叉树后序遍历： 例如: 输出为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 层次（BFS）遍历： 二叉树变种： 例如: 输出为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 叶节点遍历： 例如: 输出为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一个实例程序： 几组测试数据： * 1 * 2 * 3 二叉树的实例程序放不下了，就自己写吧（DOGE 二叉树的测试数据： * 1 * 2 * 3（有惊喜哦~）

回家以后，我每天都忍不住哭出来

Atc ABC 319 C 12AC 11WA 代码如下：

https://www.acgo.cn/discuss/4409

题解，顾名思义，就是题目的解答。 但很多ACGO的网友的题解往往都只有代码，而没有分析。 我们不缺优秀的代码，我们缺乏优秀的分析！ 比如说全站最牛逼的法神，也缺乏对题目的分析，对代码的讲解。(并非故意针对) 还有很多网友在这个暑假里疯狂刷题，一天做差不多一百多道题，一共发了几百篇题解，几乎能反超法神。 很多网友都喜欢做这样的题解： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我认为ACGO应该不倡导这种题解。 比如说洛谷就很少会出现这种题解，某道题就连点赞最少的题解它都是比较详细的，不会像上面的那种类型的题解一样 我不是想针对各位网友，我只是想倡导一下大家，请不要 用脚做题解！

我刷题，我快乐|"尽情挑战C++，锻炼编程技能，成就程序之道！"|"探索C世界，解锁无限可能，成就编程一生！"|"勇闯C的征程，追逐技术巅峰，成就开发之星！"|"拥抱C++，开启编程奇幻之旅，掌握创造力的魔法！"

2023年10月21日，CSP-J/S 2023第二轮真题来了。 CSP-S 密码锁 消消乐 结构体 种树 CSP-J 小苹果 公路 一元二次方程 旅游巴士

还行吧

RMQ问题，大概是区间多次查询问题。 最近小码君掌握的知识，也可以解决这个简单的RMQ问题了： 给一个数组a，长度为n，每个数组元素a i 最开始都为0。 接下来有q次询问，其中有两种操作： · 1 x y z：对数组区间[x,y]的每一个数增加z · 2 x y：查询数组区间[x,y]中所有元素之和 其中区间[x,y]可以理解成：从x到y中间的所有数，比如x,x+1,x+2,...,y−2,y−1,y 那么数组区间[x,y]即：a[x],a[x+1],...,a[y−1],a[y] 输入格式 第一行包含一个整数n，表示元素个数。 第二行包含一个整数q，表示查询个数。 接下来q行，每行输入一个整数o，表示操作类型。若o=1，则输入三个整数x, y, z；若o=2，则输入两个整数x, y，具体操作如描述所说。 输出格式 对于每个操作2，输出区间[x,y]的区间和，占一行。

稻妻的方块谜题 原神生日会 可莉的蹦蹦炸弹 （之后还有别的原神题目会更新的）

https://www.acgo.cn/problemset/5378/info

问一个问题，在坐的各位是不是都是x01或x02的？大多数人是不是上完就不登账号，不发消息了？

题目网址https://www.acgo.cn/problemset/2479/info?questionCollectionId=849 麻烦官方看眼数据的点的第三个

众而所知,水仙花数是一个三位数,上网搜大家也知道是4个数 从下面查看就可以发现这个水仙花数已被设定为三位数 题目描述 求100-n中的水仙花数。一个数x，x的百位、十位、个位，分别用a、b、c来表示； 当a * a * a + b * b * b + c * c * c = x时，x就被称为水仙花数。(n<= 999) 上面的题目中已经指出n是一个三位数,可是提交一个for循环: 便可以发现第三个样例错误. 我添加1000与1001时却对了.明显样例错误,与题目矛盾; 综上所述,官方出错,申请官方重新改样例

前言 又到了万众瞩目的我Macw来给大家讲题。感谢x01班的同学们参与本场oi考试，oi赛制的考试确实比ioi赛制的考试要刺激（老师们也感到刺激）。今天的题目一共七道题，难度确实也稍微有点大，但我为你们x01班的所有同学鼓掌，为你们的坚持喝彩。 题目解析 - 商品纪念铺 题目链接：https://www.acgo.cn/problemset/4441/info?teamCode=1664181761155715072。 这道题考查的核心知识点在于同学对数组等线性表的”增删改差“操作。数组是一个很神奇的数据结构，其在内存中是连续分布的，因此对数组来说，删除元素是一个很复杂的事情。虽然本题难度比较大，但可以将一个大问题分解为许多个小问题一一解决，这样子这道题就很好做出来了。 问题一：如何进行数组的初始化操作？ 这一个小问题考察的就是学生在数组中存储数据的熟练程度。数组的存储可以使用一个for循环批量的将数据存储下来： 这就完成了第一步操作，是不是非常简单？ 问题二：如何进行数组的单点累加操作？ 所谓的数组单点累加操作，就是取数组中的m个数，将这m个数相加即可。这个小问题考察的就是学生对数组索引取值的掌握程度。为了获取数组中某一个位置上的值，可以通过索引获得。 例如获取数组中的第一个数字： 因此，我们可以创建一个累加器total，用于记录所有数字的和。代码如下，其中n代表需要累加的数字的数量，t代表每一个累加的数字的索引。 先献上本题的前半部分的代码，到目前为止应该都是很简单的，就是普通的数组操作仅此而已。 接下来难度就要上去了，有请： 问题三：如何将数组的数往前挪一位？ 这个问题也比较简单，可以通过一层for循环的方式解决。具体代码如下： 以上代码应该非常好理解，将数组中第i+1个位置的数存到数组中的第i个位置。这样子就能完成将数组中的数往前挪一位的效果。这就是本题的核心难度，本题最难的地方就是如何将数组中所有的数字往前挪一位，如果到这里你都看得懂的话，那么恭喜你这道题对你来说就是小菜一碟了。 问题四：在什么时候需要将数组中的数往前挪一位？ 这个问题也很好理解。设想一下在数组中，如果这个数已经被取走了，则后面的数字都需要在数组中往前挪一位。因此问题就被转化成了如何记录一个数字已经被取走了？ 事实上，我们可以在每次结束累加arr[i]的操作后将arr[i]的值设置为-1，这样子我们就可以通过遍历arr中的所有值的值哪些数字之后的数字都需要往前挪一位。 前半部分的代码如下： 问题五：当取走K物品后，数组的长度是多少？ 一开始，数组的长度为n，代表有n件商品。随着商品被购买走后，n的大小也需要随之减少。那当k件商品被取走了，n的大小是多少呢？答案是n的大小会缩小k，也就是n -= k。也就是说，每次当一个物品被买走后，数组在排序后的长度就是原本长度-1。这个应该很好理解吧。 最后，完整代码如下： 上面这个代码是肖老师的代码，肖老师的代码比较好理解，这边再附上我自己写的官方版本，稍微有点难理解，但是总体的思路都是差不多的。 小彩蛋 在赛后看题目的过程中，我还看到了x01同学给我献上的真挚祝福（大家都挺开心的）。 好了，今天就到此为止吧，祝大家在杭州过得开心，过得快乐！

点击跳转 笔记都是自己整理的，可能不太好，有的不是特别全 前缀和于区间和（不全） 快排+高精度 栈与队列 图+dijkstra最短路 Floyd 弗洛伊德算法+背包问题 树与二叉树 深搜+广搜+优先队列排序规则

目录 FLOYD-WARSHALL（弗洛伊德算法）： 核心参考代码： 关系： 距离>1的是间接朋友，距离<1的没有关系，默认值为无穷大 背包问题： 01背包（最基础的背包问题）： 01背包特点： 01背包优化： 完全背包公式: 多重背包: 目录

上半部分跳转 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY5 下午 第十课 深度优先搜索 模板 DAY6 下午 第十二课 广度优先搜索 实验性代码 DAY7 上午 第十三课 树与二叉树 PART 1 背景 PART 2 树的存储 实验性代码（孩子表示法） PART 3 二叉树 二叉树的五大性质： 【性质 1】在二叉树的第 i 层上最多有 2^i − 1 个结点（i >= 1）。第 1 层最多 1 个结点，第 2 层最多 2 个结点，第 3 层最多 4 个结点…… 【性质 2】深度为 k 的二叉树至多有 2^k − 1 个结点（k >= 1） 【性质 3】任意一棵二叉树，若其叶子结点 (度为 0 结点) 的数量为 n0，度为 2 的结点数量为 n2，则：n0 与 n2 一定满足：n0 = n2 + 1 。 【性质 4】具有 n (n ≥ 0) 个结点的完全二叉树的深度为 ⌊log2⁡(n)⌋ + 1。⌊ ⌋ 表示下取整。 【性质 5】    若将一棵有 n 个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1，2，…，n，则： 1. 若结点编号 i = 1 ，则结点 i 为根，无父结点； 2. 若 i > 1 ，则 i 的父结点编号为 i / 2； 3. 针对编号为 i 的结点：        3.1 其左孩子编号为 2 * i (2 * i ≤ n) ；        3.2 其右孩子编号为 2 * i + 1 (2 * i + 1 ≤ n)； 二叉树的存储 二叉树的遍历 DAY7 下午 第十四课 图论 PART 1 图的定义与概念 PART 2 图的存储 邻接矩阵 样例代码 邻接表 PART 3 DIJKSTRA 最短路 实验性代码 DAY 8 上午 第15课 FLOYD最短路 例题 过关道具 记忆化搜索 最后一课放不下了，点击跳转第三部分 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完结撒花 date 8.20

DAY1 上午 第一课 算法入门 PART 1 算法的定义 PART 2 时间复杂度 PART 3 空间复杂度 PART 4 素数问题 1） 埃筛 原理：将所有不大于 n\sqrt{n}n  的所有质数的倍数剔除，剩下的自然数就是质数； 模板： 2） 线性筛 原理：每个非质数只被其最小的质因子对应的最大整数因子剔除 唯一分解定理历史 唯一分解定理数学解释 模板： DAY1 下午 第二课 STL模板 PART 1 VECTOR 常用成员函数： 函数名 作用 时间复杂度 val.push_back(data) 对val向后插入data O(1) val.pop_back(data) 删除尾数据 O(1) val.size() val内元素个数 O(1) val.clear() 清空val O(N) val.begin() 起始迭代器 / val.end() 末尾迭代器 / val.empty() 判空 / PART 2 SET 常用成员函数： 函数名 作用 时间复杂度 val.insert(data) 对val插入data O(log(N)) val.erase(it) 1.删除一个it迭代器所指的位置 O(1) val.erase(it) 2.删除值为it的数据 O(log(N)) val.erase(first,last) 3.删除迭代器于{last,first}的数据 O(last-first) val.size() val内元素个数 O(1) val.clear() 清空val O(N) val.begin() 起始迭代器 / val.end() 末尾迭代器 / val.find(data) 在val中寻找data O(log(N)) 模板 PART 3 MAP 常用成员函数： 函数名 作用 时间复杂度 mp.erase(it) 1.删除一个it迭代器所指的位置 O(1) mp.erase(it) 2.删除键为it的数据 O(log(N)) mp.erase(first,last) 3.删除迭代器于{last,first}的数据 O(last-first) mp.size() 键的个数 O(1) mp.clear() 清空 O(N) mp.begin() 起始迭代器 / mp.end() 末尾迭代器 / DAY2 上午 第三课课 前缀和与差分 PART 1 前缀和与区间和 PART 2 差分与区间修改 DAY2 下午 第四课 递归与递推 PART 1 递归 PART 2 递推 PART 3 例题 （1）平行线分割平面 （2）错排问题 DAY3 上午 第五课 贪心算法 PART 1 概念 PART 2 例题 活动排序 DAY3 下午 第六课 二分 PART 1 二分搜索 查找X PART 2 LOWER_BOUND AND UPPER_BOUND SORT 样例代码 DAY4 归并，快排和高精度 PART 1 归并排序 样例代码 PART 2 快速排序 PART 3 高精度算法 背景 加法 减法 乘法 ####除法 DAY5 上午 第九课 栈和队列 PART 1 栈 实验性代码[1] Part 2 队列 实验性代码 Part 3 前后中缀表达式 长度不够喽，第二部分在这里 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 实验性代码指通过代码可视化等手段来更好的发现问题，完成纠错等环节，在后面的笔记中还会有很多 ↩︎