https://www.acgo.cn/application/1713030102259507200

【问题】同一个时间的订单该如何选择？我是选择结束时间早的，肯定不正确，但大部分测试用例通过，求助大神 #include<bits/stdc++.h> using namespace std; struct order{ int start; int end; int t; }; bool cmp(order a,order b){ if(a.start==b.start){ return a.end<b.end; } return a.start<b.start; } int main(){ int N,K; cin>>N>>K; order ods[K]; for(int i=0;i<K;i++){ cin>>ods[i].start>>ods[i].t; ods[i].end = ods[i].start+ods[i].t; } sort(ods,ods+K,cmp); }

通俗的讲，算法是解决一系列问题的清晰步骤和方法，是准确解决问题的完整描述，是对有一定的规范的输入，在有限的时间内获得所要求的能力的表达 一个合格的算法，具备五个特性： 1.有穷性：一个合格的算法必须在执行完有穷（有限）步骤后再结束，且有时间限制 2.确定性：算法的步骤规定，含义和执行方式都是非常明确的； 3.可行性：所有操作都可实现 4.输入：算法有多个或0个输入 解决一个问题的算法通常并不唯一，例如计算1+2+3+4+5...+100的结果 算法一：按部就班，一个个从左到右进行累加，将会进行99次累加 算法二：经典"高斯算法""等差数列"等的结论"首项加末项乘以项数除以二"， 大o记法推导规则： 1.o(1)代表所有常数时间复杂度 2.只保留最高阶 3.如果最高阶存在且不是1，则删 去掉与这个项相乘的项数 常见的时间复杂度所耗费的时间从小到大依次是： o(1)<o(log(n))<o(n)<o(nlog(n))<o(n²)<o(n³)<o(2ⁿ)<o(2!) 空间复杂度，是指对一个算法在运行过程中，临时占用存储空间大小的量度 基于种种因素，一般将数组声明发在全局区并强烈建议在数组声明时，用常量声明 STR：Standard Template Library 标准模板库，一般把将这些模板称为"容器" vector 直译为"向量",一般被称为"动态数组"，即长度根据需要而自动更新的数组 相比于普通数组，vector可以相对自由的对结构整体进行调整，并且在一些高级数据结构中，例如图中，拥有更好的应用场景 头文件和名字空间 include<vector> vector<int>v; "通过迭代器访问" val.push.back(date) 对val向后插入date数据 val.pop_back() 删除val尾数据 val.size() 当前val内元素个数 val.clear() 清空当前val容器 val.begin() 起始迭代器 val.end() 末尾迭代器 val.empty() 判空 unique(数组名，数组+数组元素个数); 头文件：#include<set> 定义储存DateType类型数据容器:set<DateType>val; ↓（可以去重，自动升序）↓ 函数名：val.insert(date) 功能：对val插入date数据 时间复杂度：0（log(n) 函数名：val.erase(it) 功能：1.删除一个迭代器it所指的位置 2.删除一个值为it的数据 Val.erase(first,last) 功能：删除迭代器位于[first,last.] val.size() 功能：当前val内的元素个数 val.clear() 功能：清空当前val容器 val.begin() 功能：起始迭代器 val.endl() 功能：结束迭代器 map: 通过下标访问,即键值对访问，例如mp[“name”] 通过迭代器iterator访问元素 头文件： #include<map> 定义: map<DateType1,DateType2>mp; 输入输出提速 与scanf()/printf()解除绑定，不能混用，一律cin/cout Ios::syns_with_stdio cin.tie(0); Cout.tie(0); 埃式筛法： 其思想是将不大于根号N的倍数全部筛除，剩下的自然数自然都是素数 前缀和是指一段序列的前n项之和，可以理解为数学中，数列的前n项之和、 #include<bits/stdc++.h> using namespace std； std;Int a[]; //原数组 Int prefix[] //每项的前缀和 Int main(){ for(int i=1;i<=n;i++){ //求1~i项之和 prefix[i]=prefix[i-1]+a[i]; } return 0; } 区间和往往是指一段序列的某段连续区间之和 L,R区间和：b[R]-b[L-1] 位或计算： 两个数字转换为二进制 右边补齐，高位不足补0，从右往左 每位比较，如果都是0，运算结果为一 如果至少有一个是1，运算结果为1 7|5 0111 7 0101 5 0111 7 贪心： 贪心算法，又称贪婪算法，是指在对问题求解时，模拟一个“贪心”的人做出决策的过程。 在每次做出决策的时候都采用当前看来最好的选择，不从整体最优上去考虑， 他所做出的仅是在某种意义上的局部最优解，所以贪心算法不是对于所有问题都能够得到最优解， 关键是选择贪心的策略。 贪心算法需要具备的特征： 1.贪心的选择：一个问题的整体最优解，能够通过一系列局部的最优解的选择 达到。每次的选择可以依赖以前做出的选择，但不依赖于后面要做出的选择， 这就是贪心选择性质 2.最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。 问题的最优子结构性质是该问题可用贪心法求解的关键所在。 二分搜索，又称二分查找，折半查找，从算法大雷来讲，属于分治的策略 经典的二分搜索例子：猜数字。 1.顾名思义，每次将搜索规模缩小半，所以搜索难度为o（logN） 2.在有序序列中，查询第一个大于等于k数字是否存在（存在相同的数字 1 5 5 5 9 10 查询第一个大于等于5，第二个数字 函数：所需头文件：#include<algorithm> 使用前提：递增序列，如递增数组 作用： lower_bound (a, a + n, x) 在[a, a + n)区域内二分搜索第一个大于等于目标值 x 的地址。 upper_bound (a, a + n, x) 在[a, a + n)区域内二分搜索第一个大于目标值 x 的地址。 若该值存在，返回该值的地址，若该值不存在，返回a+n这个地址。 地址换算为数组中的下标 int v = lower_bound (a, a + n, x) - a int v = upper_bound (a, a + n, x) - a 没有找到则返回结束地址加1 正数：源码二进制=反码=补码 负数用补码表示，按位取反，+1，得到负数的绝对值 01111111111111111…….111+1=100000000000000…000000000 31个1 第31位 第0位 2^31=2147483648 -2147483648 10000000 00000000 00000000 00010111= 中国顶级域名：cn 基本两个字母，或缩写和名字前两字母 带嘤腚级域名：en 国际顶级域名：.com .org .gov .edu…….. 基本三字母 两数不断地取余，将除数移到被除数，余数移到除数，直到余数为0，这除数就是最大公约数 fgets(保存的数组名，限制长度个数，从哪里输入) 栈（stack）又名堆栈，它是一种运算受限的线程表。限定仅在表尾进行插入和a操作的线性表，这一端被称为栈顶，相对的，把另一端称为栈底 STL stack 栈 Stack<数据类型>栈容器名； 方法函数： 入栈push（数据）； 将数据放入栈 栈顶top(); 返回栈顶的数据 出栈pop(); 将栈顶元素出栈 大小size(); 返回栈内数据个数 空栈empty（）； 如果栈内没有数据，返回为true 队列（queue）也是一种运算受限的线形表，限定只在表尾进行插入，表头进行删除的线性表，插入端被称为队尾（tail），删除段被称为队头（head STL priority_queue优先队列 默认是数值越大，越优先出队 Priority_queue<数据类型>优先队列容器名； 按照队列中数据的优先级越高的越早出 入队push(数据) 将数据放入队列中 队首 front() 返回队首数据 队尾 back() 删除队尾数据 出队 size() 返回队列的数据个数 大小 empty() 如果是空队，返回true 优先队列对结构体进行自定义优先级 Strust peo{ Int id; //学号 Double score; //分数 标准模板bool operator<(const结构体类型 &a)const{….} 1. 在结构体中写标准模板 2. 添加同一个b变量和 cmp一致 3. Cmp填写规则 关于添加的删除 Bool operator<(const peo &a,const peo &b)const(…) If(a.score!=score){ Return a.score>score; } Return a.id<id } } Priority_queue<peo>q; 广度优先搜索(Breadth-First Search,BFS) 深度优先搜索中，可见是一种“一路搜到底”的策略。而广度优先搜索则是一层一层地搜索，往往需要队列来维护一层的搜索结果 4. 从初始状态开始，将第一个开始节点放入队列中。 5. 然后取出这个节点，扩展它能达到的所有节点 6. 将拓展的节点插入队列末尾，然后重复上述过程，直到队列为空或找到答案 RAM 随机存储存取器 ‘A’对应的十进制是65 栈：后进先出 哈希表： 25 37 18 46 29 5 7 8 6 9 归并排序：分割 合并 排序 ∪并 ∩交 A与b进行按位与（AND）运算的结果 A&b 二进制同一位都为一的时候结果为一 N个结点的树，有且仅有n-1条边 二叉树（Binary Tree,简称BT），是一种度数为2的树形结构，及二叉树的每个节点最多有两个子节点，每个结点的子节点严格区分左节点和右结点，他的两课子树被称为左子树，右子树 最后一层并靠左连续，且其它层点满，是完全二叉树 先序遍历（根左右 1,树的深度：树中节点的最大层数即树的高度或深度 2,节点的度，一个节点拥有的子树数 3,叶子节点:度为0的节点 满二叉树：所有层的节点数都达到最大 完全二叉树：除最后一层不满外，其余层的都达到该层的最大节点数，最后如果不满，该层所有节点都全部靠左排 二叉树三种遍历方式： 前序遍历：先遍历根节点，再遍历左节点，最后遍历右节点 中序遍历：先遍历左节点，再遍历根节点，最后遍历右节点 后序遍历：先遍历左节点，再遍历右节点，最后遍历根节点 无向完全图（Undirected Complete Graph）:图中任意两个顶点之间都存在边 拥有n个顶点的完全无向图含有n*(n-1)/2条边 有向完全图；图中任意直接两个顶点 单源指起点固定，例如在下图中求1号到其他所有点的最短距离，核心思想是用最短距离确定的点松弛其他点 Floyd-Warshall算法，简称Floyed算法，求解多源最短路径 多源指起点可以是任何顶点，例如在下图中求i号顶点到j号顶点的最短距离 核心思想是以中间点进行松弛。时间复杂度O（n³），且可以解决负边权情况 Floyd算法是最简单的最短路算法，一般用邻接矩阵进行存储。 D[i][j]表示i到j的最短距离，初始仅有直接相连的边权值 动态规划思想是将待求解问题分解成若干个子问题。先求解子问题，然后从这些子问题的解得到原问题的解，经分解得到子问题往往不是互相独立从 同时由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划方法对不同的问题，有各具特色的解题方法 01背包问题（最基础的背包问题 有N件物品和一个容量为v的背包。第i件物品的体积是c[i]，价值是w[i] 。求解将哪些物品·装入背包可使价值总和最大 问题特点 每种物品仅有一件，可以选择放或不放 用子问题定义状态，即dp[i][v]表示前i件物品放入一个容器为v的背包可以获得的最大价值

前两期跳转在这里 第一部分 第二部分 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 1 01背包 二维模板 一维模板 PART 2 完全背包 二维模板 一维模板 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 往后就真的没有内容了哈，有的话在这里加

入门天花板

目录 树： 定义： 度（树有几个直系“儿子”）： 表示法： 双亲表示法（父亲表示法） 孩子表示法 二叉树： 定义： 满二叉树： 完全二叉树： 储存： 顺序存储法（完全二叉树）： 链式储存法： 二叉树的遍历： 先序遍历（根左右）： 以根(A)为分界，分成左右两部分(B,C)。先分左边,根(B)分两部分(D,E),再分右边,根(C)分两部分(F,G)。 中序遍历（左根右） 后序遍历（左右根） 总结： 目录

众所周知，我们在ACGO上是没法用用户名搜人的，但是可以通过这个直接访问个人主页 首先，进入一个团队界面（必须有管理员，没有可以自建）： 然后，点击添加成员： 填入你想搜索的人的用户名： 找到你想要访问主页的用户 复制他后面的ID 最后，打开一个人的主页（随便一个人） 修改链接栏最后的数字为你复制的ID 按enter就可以访问了！

题解：

题解：

题解：

题解：

树与二叉树： 树：树是一种非线性的结构数据，是由n个节点组成的有限集合。 如果n==0时，称为空树，如果n>0，树有且仅有一个特定的节点——根节点。 树的度：节点拥有的子树的数量为节点的度，度为0的节点为叶子节点，度不为 0的节点为分支节点，树的度定义为树的所有节点中的最大值 树的前驱和后驱：除根节点没有前驱外，其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点。节点的直接后继称为节点的孩子，节点的直接前驱为孩子的父亲。有同一个双亲的不同节点互称兄弟。 树中节点的层次：树中根节点为第1层，根的孩子为第2层，以此类推。树中节点的最大层次称为深度或高度。注意：部分题目中根的节点为第0层 除根节点没有父节点外，其余节点有且仅有一个父节点，n个节点的数，有且仅有n-1条边，数中任意两个节点之间有且仅有一条简单路径（路径上的节点都不相同的路径） 双亲表示法：从上到下，从左到右依次给每个点编号，记录的方式可以简单表示为：tree[i] = j 表示编号为i的树节点的父亲是j。 下标： 1 2 3 4 5 6 7 8 9 父节点下标： 0 1 1 2 3 3 4 4 4 孩子表示法：即每个节点存储自己孩子的位置信息。根据结构，可以选择使用vector进行存储。 核心代码： vector<int> tree[N]; tree[i].push_back(idx); 表示i节点是idx节点的双亲 下标 1 2 3 4 孩子下标： 2/3 4 5/6 7/8/9 二叉树：二叉树是一种度数最大为2的树形结构，即二叉树的每个节点最多有两个子节点，每个节点的子节点严格区分左节点和右节点，它的两颗子树称为左子树和右子树。 性质1： 在二叉树的第i层上最多右2的i-1次方个节点（i>=1）。 性质2： 深度为k的二叉树至多2的k次方-1个节点（k>=1）。 性质3： 任意一颗二叉树，若其叶子节子（度为1节点）的数量为n，度为2的节点数量为n2，则：与n2一定满足：n0=n2+1 性质4： 具有n个节点的完全二叉树的深度为[log2(n)]+1.[]表示下取整。 性质5： 若将一颗有n个节点的完全二叉树自上而下，同一层自左向右连续给节点编号1,2…，n，则： 1. 若节点编号i=1，则节点i为根，无父节点； 2. 若i>1，则i的父节点编号为i/2; 3. 针对编号i的节点： 3.1其左孩子编号为2i； 3.2其右孩子编号为2i+1； 满二叉树：指某一二叉树“子孙满堂”，即除叶子节点外，其他节点的度均为2，且每一层的节点总数最大值，这种特殊的状态的二叉树，称为满二叉树（即二叉树深k层共2的k次方-1个节点） 完全二叉树：若某一二叉树深k层，除第k层外，其他层的节点总数达到最大值，即第i（i<k）层节点点数为2的i-1次方。且第k层节点点数小于等于2的k-1次方并靠左侧连续，这种特殊状态的二叉树，称为完全二叉树。 二叉树的存储： 1. 顺序存储法：当二叉树节点较少，呈现完全二叉树时，以二叉树性质5为基础，用顺序数组来模拟二叉树。 核心代码： 2. 链式存储法：当二叉树节点较多，且并非具有完全二叉树时，为了避免可能在使用顺序存储时，导致的内存堆栈溢出则使用链式存储法 核心代码： 1. 先序遍历：根，左，右的深度优先搜索； 2. 中序遍历：左，根，右的深度优先搜索； 3. 后序遍历：左，右，根的深度优先搜索；

不会很难 传送门 手写 贴代码

由@意大利西兰花上课 手打，@意大利西兰花上课 手打，@意大利西兰花上课 手打 树的定义 树的度：结点拥有的子树的数量为结点的度，度为0的结点为叶子结点，度不为0的结点为分支节点，树的度定义为树的所有结点中度的最大值。 注意：n个结点的树，有且只有n-1条边 二叉树 二叉树是一种度数最大为2的树形结构，即二叉树的每个结点，每个结点的字结点严格区分左结点和右结点，它的两棵子树成为左子树、右子树。 完全二叉树 若某一二叉树深k层外，其他层的结点总数达到最大值，即第i（i<k）层结点为2的i-1。且第k层结点树小于第2的k-1并靠左侧连续，这种特殊形态的二叉树，称之为完全二叉树。 性质： —性质1： 在二叉树的第i层上最多有2的i-1个结点（i>=1）。第1层最多1个结点，第二层最多两个结点，第3层最多4个结点… —性质2： 深度为k的二叉树至多有(2的k) -1个结点（k>=1) —性质3： 任意一颗二叉树，若其叶子结点的数量为n的0，度为2的结点数量为n的2，则：n的0与n的2一定满足n的0=n的2+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)