哪位大佬能帮我评测（代交）一下A16337(CF1523A)? 我的代码： 结果私信我，蟹蟹！

求解法

input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')input() for i in range(9): print('abz',end='') print('ab')

谁能告诉我样例3是哪个啊啊啊啊啊啊啊啊！！！！！

首先，题目里并没有保证 a≤ba \leq ba≤b 一定成立； 其次，测试点 #1 中，的确出现了很多 a>ba>ba>b 的情况。 但是，题解并没有写出这种情况。也就是说，真正的 AC 代码应该是：

0.TRIE介绍 Trie，即字典树、单词查找树，是一种使用空间换取时间的数据结构。 除了根节点（空字符），其它节点都是一个字符，所以字典树上的一条路径就是一个的字符串。也就是说，字符串共用一个前缀。 1.TRIE的结构 以拥有字符串 a、abc、abcd、bnm、brx、lje 的一棵 Trie 为例（红色节点标志着这是一个字符串的最后字符，不然无法确认）： 可以发现 Trie 每个字符串的最后字符在树上离 root 节点即这个字符串的长度。 Trie 的每个节点的儿子也只可能有字符集的大小个，一般来说，这个数不超过 256256256。 同时，Trie 最差的空间复杂度即 O(∑M)O(\sum M)O(∑M)（MMM 代表字符串的长度），不难想到构造这样的例子只需要让前缀不同即可。 这里给出数组实现的代码（一样的，后文中我们也只使用数组实现）： 2.TRIE的基本操作 插入 例如我们将上图所示的 Trie 再插入一个字符串 aaa，Trie 就会变成： 操作顺序即： * 从 root 节点出发，保存一个计数器 cntcntcnt，代表当前要插入的字符（插入 SSS，下标从 111 开始）。 * 寻找当前节点的子节点，若存在等同于 ScntS_{cnt}Scnt 的节点，进入这个节点，cntcntcnt 加一，继续这个操作直至 cnt=∣S∣+1cnt=|S|+1cnt=∣S∣+1；否则进入下一步。 * 插入 ScntS_{cnt}Scnt ，cntcntcnt 加一，进入上一步（实际上已经没有意义，因为必定不存在子节点，故不用查询，但为了实现方便可以这样）。 代码实现为： 查询 以图中 Trie 寻找字符串 bna 为例（箭头为查询顺序）： 操作顺序即： * 从 root 节点出发，保存一个计数器 cntcntcnt，代表当前要查询的字符（插入 SSS，下标从 111 开始）。 * 寻找当前节点的子节点，若存在等同于 ScntS_{cnt}Scnt 的节点，进入这个节点，cntcntcnt 加一，继续这个操作直至 cnt=∣S∣+1cnt=|S|+1cnt=∣S∣+1，直至 cnt=∣S∣cnt=|S|cnt=∣S∣，寻找当前节点的子节点是否有为最后且等于 ScntS_{cnt}Scnt 的字符，没有或不是最后进入下一步；否则进入下一步。 * 字符串不存在。 代码实现为： 完整实现 仅为示例： 时间复杂度 因为 Trie 的操作只会进入一条路径，故最差时间复杂度为 O(M)O(M)O(M)（MMM 为字符串长度）。 3.例题及对比其它算法或数据结构的比较 洛谷P8306 【模板】字典树 备注：模板 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 洛谷P2580 于是他错误的点名开始了 算法或数据结构 时间复杂度（单次） 额外空间复杂度 暴力 O(∑i=1n∣ti∣)O(\sum_{i=1}^n|t_i|)O(∑i=1n ∣ti ∣) O(1)O(1)O(1) Trie O(∣ti∣)O(|t_i|)O(∣ti ∣) O(∑i=1n∣ti∣)O(\sum_{i=1}^n|t_i|)O(∑i=1n ∣ti ∣) 二分 O(n∑i=1nlog⁡∣ti∣)O(n\sum_{i=1}^n\log{|t_i|})O(n∑i=1n log∣ti ∣) O(1)O(1)O(1) STL 库 map（平衡树） O(n∑i=1nlog⁡∣ti∣)O(n\sum_{i=1}^n\log{|t_i|})O(n∑i=1n log∣ti ∣) O(∑i=1n∣ti∣)O(\sum_{i=1}^n|t_i|)O(∑i=1n ∣ti ∣) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 洛谷P4551 最长异或路径 洛谷P10471 最大异或对 The XOR Largest Pair 备注：01Trie 4.TRIE的拓展 由于 Trie 的优越复杂度和树形的易拓展性，Trie 被应用于许多算法。例如 AC 自动机、01Trie 等算法，请读者自行了解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 洛谷版传送门

https://www.acgo.cn/application/1909575544164126720 求多加人！！！

1. 循环嵌套 T40243.乘法口诀表 2. 二维数组 T40233.二维数组初始化 T40234.二维数组的一行 T40235.二维数组输入输出 T40236.数0 T40237.行逆序输出 作业链接 额外挑战题

题目 解密QQ号 鱼的记忆 程序输入问题 查找 x 第一个大于等于 x 的数 第一个大于 x 的数 【二分查找】最后一个小于等于 x 解密QQ号 题目大意 小码酱给了一串加密的数字字符串（最多 101010 位），它是她的 QQ 号的加密形式。 解密规则如下： 1. 将第 111 个数从串头取出，记入解密后的 QQ 号； 2. 将第 222 个数移动到串尾； 3. 删除第 333 个数，记入 QQ 号； 4. 移动第 444 个数到串尾； 5. ... 依此类推，交替执行“删除加入结果”与“移动到尾部”操作，直到队列中只剩一个数字，将它也删掉并加入结果。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这个过程非常符合**队列结构（FIFO）**的行为： * 每次处理当前队首元素； * 若处于“删除并加入结果”轮次，则记录下来； * 若处于“移到尾部”轮次，则将该元素重新加入队尾； * 直到队列为空，整个解密结束。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 将字符串中每个字符依次入队； 2. 使用一个标志变量（如 turn = true/false）控制当前操作是“删除加入结果”还是“移动到队尾”； 3. 持续处理队首元素，直到队列清空。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每个字符最多被操作两次（一次加入结果，一次移动到尾）； * 所以总时间复杂度为 O(n)\boxed{O(n)}O(n) ，其中 nnn 为字符串长度，最多为 101010； * 空间复杂度也是 O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 鱼的记忆 题目大意 小码君正在学习字符，但他的记忆力有限，他最多能同时记住 mmm 个字符。 给定一个长度为 nnn 的字符序列，当他遇到不认识的字符时会查看书本： * 若当前记忆未满，则将该字符加入记忆； * 若当前已记满 mmm 个字符，则先忘掉最早记住的那个，再记住新字符； * 若字符已在记忆中，则不需要查看书本。 求整个过程中，小码君总共查看书本的次数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 本题等价于一个固定长度的先进先出缓存队列（FIFO），当缓存中没有某元素时，需要“缓存替换”。 我们要模拟这个缓存系统，判断每个字符是否已经存在于缓存中，若没有则计数并按规则更新队列。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 使用一个队列 q 模拟小码君的记忆，最大长度为 mmm； 2. 遍历输入的 nnn 个字符： * 如果字符已存在于 q 中，跳过； * 否则： * 查看书本，计数器加一； * 如果队列未满，直接加入； * 如果已满，弹出队首（最早记住的字符），再加入新字符； 3. 最终输出查看书本的总次数。 优化技巧 * 为避免每次都线性扫描队列判断字符是否存在，可以使用 unordered_set<char> 或 set<char> 进行快速查找； * 当前代码用纯 queue 实现，也可通过两次循环保证正确性（当前数据范围 n≤100n \le 100n≤100 足够使用此法）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 原始实现： * 每次判断字符是否已在队列中，复杂度 O(m)O(m)O(m)； * 总共 nnn 个字符，整体复杂度 O(n⋅m)O(n \cdot m)O(n⋅m)； 由于 n≤100n \le 100n≤100，m≤10m \le 10m≤10，所以最大操作量为 100010001000，可以接受。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 程序输入问题 题目大意 程序员在敲代码时可能会出现错误，采用如下两种方式进行补救： * 退格符 #：表示撤销上一个字符； * 退行符 @：表示整行清空，即撤销从上一个换行符到当前位置之间的所有输入。 你将获得若干行输入数据，每一行都表示一次输入，直到遇到 ****** 为止。 请你模拟每一行的输入处理过程，输出最终每一行的“有效字符串”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 该问题需要模拟用户的输入行为，本质上是： * 对字符流进行逐个解析； * 支持 “撤销最后一个字符” 的栈操作； * 支持 “清空整行” 的栈清空操作。 因此，非常适合使用 栈（stack） 来实现： * 入栈表示输入字符； * # 表示弹出栈顶； * @ 表示清空整个栈； * 最终将栈内字符拼接还原为字符串即为所求。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 读取每一行字符串，直到遇到结束标志 "******"； 2. 对于每一行，使用一个栈模拟编辑过程： * 普通字符：压入栈； * #：如果栈不为空，则弹出一个字符； * @：清空整个栈； 3. 最后将栈中字符倒序拼接为最终结果字符串； 4. 每一行输出一行结果。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每行最多处理 100100100 个字符； * 每个字符处理操作为 O(1)O(1)O(1)； * 假设总共有 LLL 行，总复杂度为 O(L⋅n)O(L \cdot n)O(L⋅n)，其中 nnn 是每行长度，最大为 100100100； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 查找 X 题目大意 给定一个升序排列的长度为 nnn 的整数序列，所有元素互不相同。 请你查找某个整数 xxx 是否存在于该序列中： * 如果存在，输出 xxx 在序列中的位置（下标从 111 开始）； * 如果不存在，输出 −1-1−1。 题目要求使用 二分查找 完成。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 由于序列是升序且无重复元素，非常适合使用二分查找进行快速定位。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用经典的二分查找模板： 1. 设置左右指针 l=1,r=nl = 1, r = nl=1,r=n（注意从 111 开始）； 2. 每次取中点 mid=⌊l+r2⌋mid = \lfloor \frac{l + r}{2} \rfloormid=⌊2l+r ⌋； 3. 判断： * 若 a[mid]=xa[mid] = xa[mid]=x，则找到了，输出 midmidmid； * 若 a[mid]>xa[mid] > xa[mid]>x，说明目标在左侧，令 r=mid−1r = mid - 1r=mid−1； * 若 a[mid]<xa[mid] < xa[mid]<x，说明目标在右侧，令 l=mid+1l = mid + 1l=mid+1； 4. 循环结束后若未找到，则输出 −1-1−1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每次查找将搜索区间缩小一半； * 最多执行 log⁡2n\log_2 nlog2 n 次比较； * 所以时间复杂度为 O(log⁡n)\boxed{O(\log n)}O(logn) ； * 对于 n≤100n \le 100n≤100，效率非常高。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 第一个大于等于 X 的数 题目大意 给定一个长度为 nnn 的升序序列（可能包含重复元素），请你查找第一个大于等于某个数 xxx 的元素的下标（从 111 开始）。 如果这样的元素存在，输出其下标；如果不存在（即 xxx 比所有元素都大），也要输出 −1-1−1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个经典的二分查找变形问题，即找第一个满足条件的下标（也叫左侧边界查找）。 给定序列是升序的，允许重复元素，目标是： > 找到第一个 a[i]≥xa[i] \ge xa[i]≥x 的下标 iii。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 采用二分查找模板进行变形： 1. 初始化左右边界：l=1,r=nl = 1, r = nl=1,r=n； 2. 每次取中点 mid=⌊l+r2⌋mid = \lfloor \frac{l + r}{2} \rfloormid=⌊2l+r ⌋； 3. 判断： * 若 a[mid]≥xa[mid] \ge xa[mid]≥x，记录当前位置为候选解，并继续向左查找（r=mid−1r = mid - 1r=mid−1）； * 否则，说明当前位置过小，向右查找（l=mid+1l = mid + 1l=mid+1）； 4. 循环结束后，输出记录的下标（若没找到则为 −1-1−1）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每轮搜索将范围减半，最多进行 log⁡2n\log_2 nlog2 n 次； * 所以时间复杂度为 O(log⁡n)\boxed{O(\log n)}O(logn) ； * 空间复杂度为 O(1)O(1)O(1)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 第一个大于 X 的数 题目大意 给定一个升序数组（可能有重复元素），你需要找到其中第一个严格大于某个整数 xxx 的元素下标（下标从 111 开始）。 * 若存在这样的元素，输出其下标； * 若不存在（即 xxx 不小于所有元素），输出 −1-1−1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 本题本质是一个标准的二分查找左侧边界问题（upper bound 查找）。 目标是找到最小的 iii，使得 a[i]>xa[i] > xa[i]>x 成立。 注意与上一题（查找第一个 ≥x\ge x≥x）的区别：此题要求严格大于。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 采用标准二分查找模板进行修改： 1. 初始化左右边界 l=1,r=nl = 1, r = nl=1,r=n； 2. 使用变量 ans 记录满足条件的位置，初始为 −1-1−1； 3. 在循环中不断取中点： * 若 a[mid]>xa[\text{mid}] > xa[mid]>x，说明当前元素可能是答案，同时可能左边还有更小的符合条件的值，故令 r=mid−1r = \text{mid} - 1r=mid−1，并记录 ans = mid； * 否则说明 a[mid]≤xa[\text{mid}] \le xa[mid]≤x，不符合要求，向右搜索，令 l=mid+1l = \text{mid} + 1l=mid+1； 4. 循环结束后输出 ans 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每轮查找将区间折半，最多执行 log⁡2n\log_2 nlog2 n 次； * 所以时间复杂度为 O(log⁡n)\boxed{O(\log n)}O(logn) ； * 空间复杂度为 O(1)O(1)O(1)，不使用额外数组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 【二分查找】LOWER_BOUND 函数 题目大意 给定一个升序排列（元素可能重复）的长度为 nnn 的整数序列，要求使用 lower_bound 函数，查找第一个 大于等于 xxx 的元素，并输出其下标（从 111 开始）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是标准的二分查找变形题，要求使用 STL 中的 lower_bound 函数。 什么是 LOWER_BOUND？ * 在一个有序区间中，lower_bound(first, last, x) 返回第一个不小于 xxx 的位置； * 它等价于：在区间中找最小的下标 iii 满足 a[i]≥xa[i] \ge xa[i]≥x； * 若不存在满足条件的元素，返回 last。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 输入数据时从下标 111 开始存储； 2. 使用 lower_bound(a + 1, a + n + 1, x) 来查找； 3. 最后返回的是一个指针，减去 a 即可得到下标； 4. 若 xxx 比所有元素都大，返回的下标会是 n+1n + 1n+1，即越界，也符合题意（即没找到）； * 如需判断是否找到，可加判断 if (pos <= n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * lower_bound 内部是用二分查找实现的； * 时间复杂度为 O(log⁡n)\boxed{O(\log n)}O(logn) ； * 空间复杂度为 O(1)O(1)O(1)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 【二分查找】UPPER_BOUND 函数 题目大意 给定一个长度为 nnn 的升序序列（元素可能重复），查找第一个 严格大于 xxx 的元素的位置，并输出其下标（从 111 开始）。 本题要求使用 STL 的 upper_bound 函数来实现。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个经典的 二分查找右边界 问题，即： > 在升序序列中找第一个满足 a[i]>xa[i] > xa[i]>x 的位置。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 函数说明 UPPER_BOUND(BEGIN, END, X) * 作用：返回第一个严格大于 xxx 的位置； * 实现方式：标准二分查找； * 时间复杂度：O(log⁡n)\boxed{O(\log n)}O(logn) ； * 返回的是一个指针/迭代器，需要通过减去基地址转换为下标。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 将输入数组从下标 111 开始读入； 2. 使用 upper_bound(a + 1, a + n + 1, x) 查找； 3. 该函数返回的是指针，减去 a 得到下标； 4. 若 xxx 大于等于所有元素，则返回 n+1n + 1n+1，表示“未找到”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 【二分查找】最后一个小于等于 X 题目大意 给定一个升序数组（元素可能重复），要求找到最后一个小于等于给定整数 xxx 的元素下标（从 111 开始）。如果找不到，输出 −1-1−1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个二分查找右边界问题，即： > 在升序序列中查找最大的 iii，使得 a[i]≤xa[i] \le xa[i]≤x。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 我们可以使用以下三种方法实现该查找： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 方法一：STL UPPER_BOUND 原理解释： * upper_bound(first, last, x) 返回第一个满足 a[i]>xa[i] > xa[i]>x 的迭代器； * 所以最后一个 ≤x\le x≤x 的元素一定在它的前一个位置； * 故：pos = upper_bound(...) - a - 1。 注意： * 若 upper_bound 返回的是 a + 1，说明没有任何元素 ≤x\le x≤x，应特判输出 -1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 方法二：用 LOWER_BOUND(X + 1) 等价替代 原理解释： * lower_bound(first, last, x + 1) 返回第一个 ≥x+1\ge x + 1≥x+1 的位置； * 也就是第一个 >x> x>x 的位置； * 同理，前一个就是最后一个 ≤x\le x≤x 的位置。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 方法三：手写二分查找（推荐掌握） 原理解释： * 满足 a[mid]≤xa[\text{mid}] \le xa[mid]≤x 时，继续往右找； * 记录满足条件的最大下标 ans； * 若找不到，ans 仍为 -1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 三种方法均使用二分查找，其时间复杂度为： O(log⁡n)\boxed{O(\log n)}O(logn) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完整代码（包含三种方法）

哈喽，大家好，今天我给大家带来动态规划中的背包知识点。 > 点个赞吧！！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前言 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本蒟蒻是一位只有六年级的小学生，第一次写知识点类型的文章，希望各位大佬多多指点。（点个赞吧！！QVQ） @AC君 给个精选、置顶吧！！！写这篇文章把我累成狗了好累啊！！！ 好了，话不多说，现在就进入正题！！ 目录 > 1——动态规划与背包问题 > > > 2——01背包 > > > 3——完全背包 > > > 4——多重背包 > > > 5——01背包 > > > 6——总结回顾 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > THE FIRST PART：动态规划与背包问题 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 很多同学在刚开始接触动态规划时都会问：”动态规划是什么？？“，我也一样，首先让我们一起来看看动态规划的定义。 动态规划（Dynamic Programming，简称DP）是一种用于解决最优化问题和计数问题的高效算法。 实际上，动态规划就是运用了类似递推的思想，中间通过记录子问题的值从而减少重复计算，提高效率。 注意：能运用动态规划解决的题目需拥有最优子结构与无后效性。 新名词：动态转移方程，即转移（递推）时用到的式子（转移式）。 而今天的知识点——背包，就是动态规划中较为基础的一种类型。 背包，顾名思义，就是往一个像背包一样的容器内装不同体积、不同价值的东西。要使得物品体积总和不超过背包容量的情况下，最多能装多少价值的物品。 背包问题主要有三种类型：01背包、完全背包与多重背包。让我们逐一攻破！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > THE SECOND PART：01背包 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先看一道题目：题目 读完题目，你想到了什么？？是贪心？还是搜索？……看看接下来这几种经典错误方法中有没有你的方法： 1、按草药的价值从大到小排序 想法：价值越大，越应该取。 错误样例： 本应输出101（取后两种），但是按照这种方法会输出100 ❌ 2、按采药的时间从小到大排序 想法：时间少的划算，能取更多。 错误样例： 本应输出100（取第一种），但是按照这种方法会输出99 ❌ 3、按采药的”性价比“从小到大排序 想法：性价比越高（时间/价值），取到的价值肯定最大。 错误样例： 本应输出40（取后两种），但是按照这种方法会输出33 ❌ 那么正解到底是什么呢？？——没错，就是背包（动态规划） 题目翻译：背包体积为T，草药数量为M，每次输入每株草药的体积t[i]与价值w[i]。 分析与解：我们设一个二维数组DP，DP[I][J]表示在当前考虑前I个物品，且背包容量为J的情况下，所能取到物品的最大价值。 接着，我们利用类似于递推的思想，推演DP[I][J]如何得到： 对于我们遇到的每一个物品，只有选与不选两种情况， 1、不选：则继承上一个物品（即考虑I-1个物品时）在背包容量为J时的最大价值和； 2、选：则继承上一个物品在背包容量为（现在背包容量-现在物品体积）的情况下，加上现在物品价值。 接着取两种情况中的最大值就可以解决这道题了。 由此，我们得到了动态转移方程：DP[I][J]=MAX(DP[I-1][J],DP[I-1][J-T[I]]+W[I]) 注：此处如果不理解，可以自己打个表试试看。 CODE_1 接下来我们会发现：只需记录上一轮的情况与这一轮的情况即可，可以用滚动数组优化。 CODE_2 然后我们又发现：既然都能用滚动数组优化，那难道就不能直接优化为一维的吗？ 最后，我们就得到了01背包问题的模板： CODE_3 你学会了吗？？ 更多习题：题1、题2、题3、题4 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > THE THIRD PART：完全背包 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目 完全背包只有一点与01背包不同，就是每件物品有无数件。 此时，我们只需要将第二重循环改为正序即可。 注：此处若有不理解，可以自行打表尝试，在此我就不多赘述（千万别知道是因为我懒） 那么这道题目也就迎刃而解了。 CODE_1 此处再提供一种思路，请大家自行体会（这个方法可能更好理解） CODE_2 怎么样？是不是很简单？ 更多习题：题1、题2 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > THE FOURTH PART：多重背包 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目 多重背包的不同点在于每件物品都有对应的个数，既不是1个，也不是无数个。 对于这样的问题，我们可以在01背包的基础之上加一重循环，用变量K来枚举每一个物品所取的个数。 那么动态转移方程就是：DP[J]=MAX(DP[J],DP[I-1][J-W[I]*K]+V[I]*K) CODE_1 但是我们会发现，这道题目的数据较大，这个程序无法通过所有测试点，需要优化。 那如何进行优化呢？我们考虑采用二进制拆分的方式，将这个问题转化为01背包问题，减少遍历次数。 例如一个物品有18件，我们可以将它拆分为价值与重量都为1，2，4，8，3的五件物品，（1+2+4+8+3=18）这样就可以高效地解决这个问题了。 CODE_2 所以我们就得到了多重背包的模板了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > THE FIFTH PART：总结回顾 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1、三种背包的不同点： 01背包：每种物品只有1个，只有选与不选两种情况； 完全背包：每种物品有无数个，需考虑要不要取/要取几个； 多重背包：每种物品有固定的个数，需考虑取几个。 2、三种背包的共同点： 代码都较为固定，基于01背包。 3、三种背包的优化： 01背包：滚动数组、一维优化； 完全背包：滚动数组、一维优化； 多重背包：二进制优化。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 结语 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 好了，本期的分享就到这里，“业精于勤荒于嬉，行成于思毁于随”，希望大家多多刷题，早日AC，越变越强！ 最后的最后，大家点个赞吧！！

程序入口是那个指令？ A cin B cout Creturn Dint main

谁写的?\HUGE 谁写的?谁写的? 给我站出来!\HUGE 给我站出来!给我站出来! 这是让人做的吗?\HUGE 这是让人做的吗?这是让人做的吗?

HDU-1850 看书时看见的

看标题

！！！

在评论区讨论

欢迎欢迎，热烈欢迎！！！

大家可以期待一下第二章哈

一、数据类型 1. 整数： 2. 小数：(分数，浮点数， 实数) 3. 字符串： 4. 字符 二、占位符 > %d --- int类型占位符 > %f --- float类型占位符 > %lf --- double类型占位符 ★整数的对齐输出 三、数据类型转换 实例1: 计算平均分 > 🚩 控制小数点位数 四、模运算取位数 > 除10的作用： 消除最后一位 //cout << a/10 << endl; > 模10的作用：取出最后一位 //cout << a%10 << endl;