时间复杂度：O(log2b)O(log_2 b)O(log2 b)

背包 1.字串和子序列 子序列：不连续的 字串 ：连续的 2.DP记忆化搜索 方法——结尾法 1. dp[i] 表示以下标 i 作为结尾的答案,ans是{dp[1]~dp[n]}的最优值 2. 记录长度?dp[i]——Answer: dp[i] 表示 以 a[i] 作为结尾的最长上升子序列\textbf{记录长度?}dp[i] ——Answer:\large{ \textbf {\color{red} dp[i] 表示 以 a[i] 作为结尾的最长上升子序列}}记录长度?dp[i]——Answer: dp[i] 表示 以 a[i] 作为结尾的最长上升子序列 过程 1.1.1. $\large\textbf{遍历1 (i−1)1~(i-1)1 (i−1),用 j 下标表示}$ if(a[i]>a[j])if(a[i]>a[j])if(a[i]>a[j])转移条件 $dp[i]=max(dp[i],dp[j]+1); $ 多维技巧 若低维状态无法描述问题，那我们开高维 dp[i][j]//什么含义 前缀法 定义状态 含义例子:dp[i]dp[i]dp[i]就表示111~iii处理完毕的结果，ans=dp[n]ans=dp[n]ans=dp[n]. dp[i][j]dp[i][j]dp[i][j]表示xxx序列处理完 前iii项， YYY序列 处理完前j项的最大公共子序列 例题——LIS最长上升子序列\TEXTBF{例题}——LIS\TEXTBF{最长上升子序列}例题——LIS最长上升子序列 正解： DAG模型 有向无环图 −>dp-> dp−>dp

动态规划 1.高维技巧 > 如果低维状态无法描述问题，就多开一维（dp[i]->dp[i][j]）; 2.破环法(洛谷P1203) > 遇到环时，复制一遍（brrbrbr->brrbrbr brrbrbr） 3.DAG模型（有向无环图）

B3637 最长上升子序列 高维技巧 如果低维状态无法描述问题，则开高维 前缀法 dp[i] 表示已经处理 1 ~ n 的状态的结果， dp[n] 即为答案 破圈法 P1203 [USACO1.1] 坏掉的项链 Broken Necklace DAG 有向无环图 -> dp

AKSZ-DP 多维DP 如果低维无法表示状态，那就多开 题目： 好东西还要前缀法 好东西还要前缀法 蒙一个吧，我*我进AK班了！！！！！！！！ 第一个是团队限定 @又是好东西 DAG模型，有向无环图 所有dp都可以转换成DAG模型。 模板 不想打了，递推都知道吧 今天做了一堆题脑子炸了，我**才很难 AC君！！！ 你给我解释一下cin、cout比scanf、printf快？

DP定义状态的方法 1.一维无法表示开多一维 2.前缀法 定义状态 dp[i]表示已经处理完的1-i的结果 ， 结果->dp[n] 破圈法 将字符串copy一份 首尾相接 DAG模型 有向无环图 绝大多数dp问题可以转为有向无环图

动态规划 1.划分阶段：斐波那契数列的每一项作为一个阶段 2.确定状态：第iii项的值用数组第iii位表示：a[i]a[i]a[i] 3.确定转移方程：a[i]=a[i−1]+a[i−2]a[i]=a[i-1]+a[i-2]a[i]=a[i−1]+a[i−2] 结尾法：dp[i]dp[i]dp[i]就表示以下标iii结尾的答案 1,最优化原理：最优解所包含的子问题的解也是最优的 2.无后效性：某状态以后的过程不会影响以后的决策 3.子问题重叠：子问题直接不独立 结尾法示例 最长上升子序列 前缀法：dp[i]dp[i]dp[i]表示111~iii处理完毕的结果，dp[i]dp[i]dp[i]就是答案 前缀法示例 最长公共子序列

6

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！

先，让我们一起深入理解题目的要求。题目描述的是在一个 𝑁 × 𝑁 N×N的网格中找到所有的山谷，并计算它们的大小之和。山谷是满足以下条件的非空区域： 区域内的所有单元格都是连续的，可以通过上、下、左、右移动到达。 区域没有洞，即它的补集（包含网格外的无限高度单元格）不是点对点连续的。 区域内的每个单元格的高度都低于其边界上的所有单元格。 接下来，我们需要关注输入和输出的描述。输入是一个 𝑁 × 𝑁 N×N的矩阵，表示网格的高度。输出是所有山谷的大小之和。 样例给出了几个例子来帮助我们理解什么是山谷和非山谷，以及什么是洞。我们可以从这些例子中看出，判断一个区域是否为山谷的关键在于检查它的边界和内部高度的关系，以及它是否是连续的。 解题步骤可以如下： 读取输入：首先，你需要读取 𝑁 N的值和高度矩阵。使用C++，你可以使用cin和二维数组来实现这个功能。 遍历网格：对于每个可能的山谷起点，你需要进行深度优先搜索（DFS）或广度优先搜索（BFS）来找到整个山谷。在这个过程中，你需要记录山谷的大小（即区域内单元格的数量）。 检查山谷条件：在搜索过程中，检查当前单元格是否满足以下条件： 高度低于相邻的边界单元格。 该区域是连续的，没有洞。这可以通过在搜索过程中标记已访问的单元格来实现，确保不会跳过任何相邻的单元格。 累加山谷大小：如果找到一个山谷，将其大小累加到总和中。 输出结果：最后，输出所有山谷大小的总和。 现在，你可以尝试根据这些步骤编写代码。在实现过程中，注意优化搜索算法，例如使用剪枝技巧避免不必要的搜索。如果遇到困难，随时告诉我，我会继续指导你。记住，关键在于理解和应用基本的图论概念，如连通性和搜索算法。 有用无用 userId_undefined 我的代码错哪了？ userId_undefined 首先，让我们一起回顾一下题目的要求。我们需要找到所有的山谷，也就是那些非空的、没有洞的、且边界上的高度大于内部所有点的高度的区域。然后，我们要计算所有这些山谷的大小（即区域内点的数量）并求和。 你的代码看起来是在构建一个树形结构来表示地形的连通性，并使用深度优先搜索（DFS）来遍历这个结构。但是，从代码中我注意到你没有直接处理题目中关于山谷的定义。你的代码似乎在构建一些农场结构，并寻找某种类型的连接，而不是直接寻找山谷。 为了更有效地解决这个问题，你可以采取以下步骤： 预处理高度数据：找出每个点的邻居，并记录下它们的高度关系。这可以通过扫描每行和每列，以及对角线来实现。 识别山谷起点：从每个点开始，如果该点的所有邻居都比它高，那么这个点可能是山谷的一部分。你需要继续向下搜索，直到找到一个点，它的某个邻居不比它高，或者你已经搜索了整个连通组件。 扩展山谷：从山谷起点开始，沿着相邻的低点扩展，直到遇到一个高度较高的点。记录下所有属于这个山谷的点。 计算山谷大小：统计每个找到的山谷包含的点数。 累加结果：对于每个找到的山谷，将它的大小（点数）加到总和中。 输出结果：最后输出所有山谷的大小之和。 你的代码可能需要进行重写以适应这些步骤。尝试将注意力集中在如何根据题目描述来识别和扩展山谷，而不是依赖于目前代码中的树形结构。这将帮助你更好地理解问题，并有助于找到解决方案。同时，注意代码的效率，因为题目中提到的矩阵大小可能会很大。在实现过程中，尽量避免不必要的计算和存储，以提高时间复杂度。

https://www.acgo.cn/contest/1762/detail?matchRoundId=1762&examId=36796&openLevel=2&teamCode=1691092370071752704

【暑期集训营】X02入营测试： 测试链接：https://www.acgo.cn/contest/1762/detail?matchRoundId=1762&examId=36796&openLevel=2&teamCode=1691092370071752704 邀请码：BPmE

我也不会

加入我们！https://www.acgo.cn/team/1781561334244745216 \0

> 欢迎来到高精度算法的第二站:高精度乘法,详情见目录:传送门 高精度乘法原理: 欢迎来到高精度算法的第二站:高精度乘法 在这之前,我们先要认识高精度乘法,高精度乘法归根结底还是要用到数学乘法的基本原理,先把一个大整数分拆成各个数位,过程: 1. 将两个大整数相乘，从低位开始逐位相乘，得到部分乘积； 2. 将每一位的部分乘积相加，考虑进位； 3. 最终得到的结果就是两个大整数的乘积。 举例说明： 假设要计算 12345 * 6789。 首先，逐位相乘得到部分乘积：59=45、49=36、39=27、29=18、1*9=9。 然后，将这些部分乘积相加考虑进位：5 + 3（进位）= 8、6 + 4 + 2（进位） = 12、2 + 7 + 1（进位） = 10、1 + 8 = 9、0（进位）= 0。 最终结果为：83965705。 通过这种方法，可以实现大整数的高精度乘法运算。 那么接下来就请看代码详解: 代码详解: 这次咱们调换一下顺序,先亮出例题和代码,接着再来讲解: 例题:A*Bproblem-洛谷 当然,这只是个母题,我们默认定义的vector数组是int类型的,所以在这里并没有处理负数的情况,如果需要支持负数的话,还需另外进行操作. 那么今天我们就讲到这儿了,离别是为了更好的相聚,希望下次的高精度除法能够再次与你同行 -Ysjt | 深 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 相关参考/引用: C++实现高精度乘法 c高精度乘法的原理及c代码讲解 感谢: 洛谷刷题平台 ACGO平台 提供例题 本文同步发布: 新浪微博 CSDN平台

https://www.acgo.cn/contest/2234/detail?matchRoundId=2234&examId=40716&teamCode=1661232050350374912&openLevel=2 cx64

AC助手：你的C#代码看起来已经很接近正确答案了，它使用了LINQ查询来找出同时获得科技创新奖和特殊贡献奖的人，并按照他们在科技创新奖名单中的顺序输出。不过，我们可以从几个方面来思考和优化你的代码： 错误处理：你的代码假设输入总是有效的，即nm、td和sd的长度都是正确的。在实际编程中，我们通常需要对可能的错误输入进行处理，比如检查数组长度是否符合预期。 效率：虽然LINQ查询简洁易读，但在处理大数据时可能会较慢，因为它涉及到多次遍历数组。对于这个问题，我们可以考虑使用更高效的数据结构，如哈希集合（HashSet），来存储和查找获奖者编号，这将大大减少查找时间。 样例测试：你可以尝试使用其他样例数据来测试你的代码，看看它是否能正确处理各种情况。例如，当没有人在两个奖项中都获奖时，或者当两个奖项的获奖者完全重合时。 代码可读性：虽然代码目前可读性不错，但可以考虑使用更具描述性的变量名，使代码更容易理解。 现在，让我们思考如何改进代码，使其更加健壮和高效。你可以尝试使用HashSet来存储特殊贡献奖的获奖者，然后遍历科技创新奖的获奖者列表，检查他们是否也在特殊贡献奖的HashSet中。这样可以减少查找的时间复杂度。同时，别忘了处理可能的边界条件和异常情况。你可以根据这些提示去修改你的代码，如果还有问题，欢迎再次提问。 https://www.acgo.cn/problemset/21178/19246?tab=discuss