GF=girl friend 女朋友 MM=妹妹

虫子：这差事不错 苹果：你不要过过来来啊啊！！

https://paste.nugine.xyz/swlbrbeq

关于时间复杂度，想必大家都有了解。在这里，我将详细讲解时间复杂度。 1.排序1.排序1.排序 排序法 最差时间复杂度 平均时间复杂度 最优时间复杂度 冒泡排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n)O(n)O(n) 插入排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n)O(n)O(n) 选择排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) 堆排序 O(nlog⁡n)O(n\log n)O(nlogn) O(nlog⁡n)O(n\log n)O(nlogn) O(nlog⁡n)O(n\log n)O(nlogn) 归并排序 O(nlog⁡n)O(n\log n)O(nlogn) O(nlog⁡n)O(n\log n)O(nlogn) O(nlog⁡n)O(n\log n)O(nlogn) 快速排序 O(n2)O(n^2)O(n2) O(nlog⁡n)O(n\log n)O(nlogn) O(nlog⁡n)O(n \log n)O(nlogn) * 冒泡排序代码框架（已优化） * 插入排序代码框架 * 选择排序代码框架 * 堆排序代码框架（大根堆） * 归并排序代码框架 * 快速排序代码框架 2.质数2.质数2.质数 判断类型 判断方法 最差时间复杂度 平均时间复杂度 最优时间复杂度 核心限制 单个数字 朴素试除法 O(n)O(n)O(n) O(n)O(n)O(n) O(1)O(1)O(1)（n=n=n=偶数时） 无 基础优化试除法 O(n)O(\sqrt n)O(n ) O(n)O(\sqrt n)O(n ) O(1)O(1)O(1)（n=n=n=偶数时） Miller-Rabin O(log⁡3n)O(\log^3 n)O(log3n) O(log⁡3n)O(\log^3 n)O(log3n) O(log⁡3n)O(\log^3 n)O(log3n) 区间数字 设区间为 [A,B][A,B][A,B]，长度L=B−A+1L=B-A+1L=B−A+1 埃氏筛 O(Blog⁡log⁡B)O(B\log \log B)O(BloglogB) BBB不能太大，无法求远端区间 线性欧拉筛 O(B)O(B)O(B) 分段区间筛 O(Llog⁡log⁡B)O(L\log \log B)O(LloglogB) B−AB-AB−A不超过 106∼10710^6\sim10^7106∼107 * 【单个数字】基础优化试除法代码框架 * 【单个数字】MILLER-RABIN代码框架 * 【区间数字】埃氏筛代码框架 * 【区间数字】欧拉线性筛代码框架 * 【区间数字】分段区间筛 3.DP3.DP3.DP DP类型 时间复杂度 提示 01 背包 / 完全背包 O(nV)O(nV)O(nV) nnn 件物品，容量 VVV LIS 朴素 O(n2)O(n^2)O(n2) LIS 贪心二分 O(nlog⁡n)O(n\log n)O(nlogn) LCS O(nm)O(nm)O(nm) 两串长度 n,mn,mn,m 区间 DP（石子合并） O(n3)O(n^3)O(n3) 长度为 nnn 数字三角形 O(n2)O(n^2)O(n2) 设层数为 nnn * 010101背包代码框架 * 完全背包代码框架 * LIS优化版 * LCS * 区间DP * 数字三角形代码框架 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎评论区投稿哦 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 攥写不易请留下一个赞吧

我觉得，我不用函数都能做

自主学习笔记类产物 —————————————————————————————————————————— 前置 一.Graham扫描法 比较重要的是第四步。 三点构成两条线。 sin(θ)sin(\theta)sin(θ) 在后面的计算，我们把三个点变成两个向量。 逆时针作为正方向。 判断是否为逆时针：叉积。 为什么不用点积？点击：cos(θ)cos(\theta)cos(θ) sin:一二象限为正，三四象限为负。 就【判断是否向正方向移动。 好的，来看看苹果： 1.从点集中选出一个最靠近左下方的点 2.以选定的基准点为极点，对其他点按照极角进行逆时针排序。如果极角相同，则根据与基准点的距离排序，距离近的点优先。 3.使用一个栈来维护当前的凸包顶点。首先将基准点和排序后的第一个点压入栈中。 4.遍历排序后的点：从第三个点开始，对于每个点，检查它与栈顶的两个点形成的角度（使用叉积），如果符合要求则将点压入栈中，不符合则弹出栈顶的点，重复检查直到符合要求。 这是我从洛谷第一个题解截的图：它是如何根据极差将点排序的。 放置一道变式题目： https://xinyoudui.com/ac/contest/7470110AC000BED0906A0F/problem/13434 凸包面积 如图可知，一个多边形可以分成很多个三角形。 如何快速求出三个顶点坐标已知的三角形的面积？ 考虑叉积计算的本质。 所以将->AB * ->AC /2=ABC三个点构成的三角形面积

大家觉得这次五级难吗？我觉得太easy了，相对于6级，五级确实难。 其实这次四级也还挺简单的，但相对三级，五级。四级不算超简单。

感谢各位参加 MMOI Round 2，虽然比赛时出现了一些搞笑的问题，但是比赛最后还是结束了（？）本场比赛共 118118118 人提交，797979 人有分。 * A 题预期难度为橙，共 696969 人通过，首 A 为 @starry_fast，获得 100100100 罐头； * B 题预期难度为黄，共 151515 人通过，首 A 为 @Lost，获得 150150150 罐头; * C 题预期难度为绿，共 111111 人通过，首 A 为 @万泉不是入，获得 200200200 罐头； * D 题预期难度为蓝，共 444 人通过，首 A 为 @TheWorstPlayer，获得 400400400 罐头。 排除作弊后的前五名为： * 第一名：@xiao7Mr10，获得 122212221222 罐头； * 第二名：@pangz，获得 407407407 罐头； * 第三到七名：@万泉不是入、@TheWorstPlayer、@Deep欠揍 | 深度欠揍、@cjdst、@Lost，分别获得 818181 罐头。 题解：https://www.acgo.cn/discuss/study/85007。

下集传送门：线段树 树的类： 二叉树变种： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 输入树： 先输入元素个数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（有惊喜哦~）

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 倍增法找 LCA 预处理：用 f[x][t] 表示结点 xxx 向上走 2t2^t2t 步的祖先结点编号 * f[x][0] 为结点 xxx 的父结点 * 当 t≥1t≥1t≥1 时，利用 f[x][t]=f[f[x][t-1]][t-1]; 进行更新 计算 LCA ：调整深度较大的结点和另一个结点相同深度 * 将深度差转为二进制形式 * 利用二进制形式中 1 的位置更新结点 计算 LCA ：不断更新两个结点直到找到最近公共祖先 * 由于只能往根的方向走，不能往叶子方向走 * 所以当祖先结点不相同时才可以进行更新 * 因为相同祖先结点时不确定是否为最近的 * 相当于最后找到了最远的非公共祖先 * 再往上一步即可得到最近公共祖先 往上走的过程仍利用二进制实现，由于此时不知道具体要往上走几步，按照从大到小的顺序枚举每一位 看题 P3379 一眼 __ __（（（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 树上路径求和问题（树上前缀和） 求树上任意两点之间路径上结点权值之和 * 利用最近公共祖先，将路径由一条折线拆成两条直线 * 两条直线均为从当前结点朝向根结点的路径 * 预处理每个结点到根节点的路径上的结点权值之和 * 则可以 O(1)O(1)O(1) 快速求出每条直线路径上的结点权值之和 注意最近公共祖先结点仅需计算一次，不要重复！！！ 看题 P8805 每日一眼（1/1）（ 册那错了 114514 次不写了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 树上路径修改问题（树上差分） 将树上任意两点之间路径上每个结点权值修改 * 记录每个点与其父结点的差，再进行处理？ * 利用差分进行区间修改时，其后继都会接收到信息 * 但是在树上每个点都有若干的后继，该怎么办 * 我们知道除根结点每个点有唯一前驱 * 将前驱和后继交换再进行差分 * 差分数组为每个结点的权值减去所有子结点的权值 * 区间修改时，较深结点 + ，较浅结点父结点 - * 修改结束求原结点权值，对应子树差分权值之和即为结果 * 如果初始路径为折线，需要先拆为两条直线 注意最近公共祖先结点仅需计算一次，不要重复！！！

求教。。。

不是哥们，这是入门？这是《新手入坟》

等级 L 汉堡（L≥1）：自下而上依次为 面包 B、等级 L−1 汉堡、肉饼 P、等级 L−1 汉堡、面包 B。 等级0汉堡：一层肉饼: P 等级1汉堡： 面包B、等级0汉堡（P），肉饼P、等级0汉堡（P），面包B，应该是：BPPPB，跟题目表述也对不上啊 等级2汉堡： 面包B、等级1汉堡（BPPPB），肉饼P、等级1汉堡（BPPPB），面包B，应该是：BBPPPBPBPPPBB，跟题目表述也对不上。 即便题目描述中，关于汉堡的定义有误，正确定义是： 等级 L 汉堡（L≥1）：自下而上依次为 面包 B、等级 L−1 汉堡、面包 B、等级 L−1 汉堡、面包 B。 则等级1汉堡为：BPBPB 等级2汉堡为：BBPBPBBBPBPBB，依然跟题目表述对不上。

A

为什么我的代码第一遍三个TLE，第二遍两个TLE，第三遍就AC了？（代码一样）

当我看到这位用户陈臻武发布的题解CODEFORCES题解(1/50)时，不禁生起怀疑，于是我就去往上查找题解。 我们可以清楚地看到，用户陈臻武抄袭了CSDN网站名叫ZHAOWEIMING2019的题解：题解 CF2A 【WINNER】 这是用户陈臻武的代码 这是CSDN用户的代码： 这位CSDN早在2020年就发布了这条题解，很明显，用户陈臻武抄袭了题解。 而用户陈臻武仅仅加了几句题解： 请大家以此为戒！请勿抄袭!抄袭可耻！！！

why？