题目 结点的度 先序遍历 中序遍历 后序遍历 求先序遍历 结点的度 题目大意 给定一棵以 111 为根的树，共 nnn 个结点，树用 n−1n-1n−1 条边表示父子关系。你需要处理 qqq 个查询，每次询问一个结点的度数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 树是有向关系：输入中给定的是 fafafa 是 sonsonson 的父亲； * 但我们要输出的是度数，即该结点连接的边数（子结点数量）； * 因为输入的是有向边（从父到子），所以只需统计每个点作为父节点出现的次数即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 一、数组记录度数 * 用数组 deg[i]deg[i]deg[i] 表示第 iii 个结点的度； * 每读入一对边 (fa,son)(fa, son)(fa,son)，令 deg[fa]++deg[fa]++deg[fa]++； * 每个子节点 sonsonson 不需要处理（因为题目不问入度）； * 对每个查询 xxx，输出 deg[x]deg[x]deg[x] 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 建树处理 n−1n-1n−1 条边，时间 O(n)O(n)O(n)； * 查询 qqq 次，每次 O(1)O(1)O(1)； * 总体时间复杂度：O(n+q)\boxed{O(n + q)}O(n+q) ； * 空间复杂度：O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 先序遍历 题目大意 给定一个长度为 nnn 的数组，将其构造成完全二叉树的结构（根结点编号为 111，左儿子为 2x2x2x，右儿子为 2x+12x+12x+1），然后输出整棵二叉树的先序遍历结果。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 我们可以把数组想象成完全二叉树的顺序存储结构： * 树的根是数组下标 111； * 每个结点编号 xxx： * 左儿子编号为 2x2x2x； * 右儿子编号为 2x+12x+12x+1； * 当 x>nx > nx>n 时视为越界（无该结点）； * 遍历顺序为： 先序遍历=根→左子树→右子树\text{先序遍历} = \text{根} \rightarrow \text{左子树} \rightarrow \text{右子树}先序遍历=根→左子树→右子树 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 * 用数组 a[1∼n]a[1\sim n]a[1∼n] 储存树的顺序结构； * 定义一个递归函数 dfs(x)： * 若 x>nx > nx>n：越界，返回； * 否则： * 输出当前结点 a[x]； * 递归访问左儿子 dfs(2x)； * 递归访问右儿子 dfs(2x + 1)； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 树中最多访问每个结点一次； * 总时间复杂度为 O(n)\boxed{O(n)}O(n) 。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 中序遍历 题目大意 给定一个长度为 nnn 的数组，将其构造成完全二叉树的结构（根结点编号为 111，左儿子为 2x2x2x，右儿子为 2x+12x+12x+1），然后输出整棵二叉树的中序遍历结果。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 我们可以把数组想象成完全二叉树的顺序存储结构： * 树的根是数组下标 111； * 每个结点编号 xxx： * 左儿子编号为 2x2x2x； * 右儿子编号为 2x+12x+12x+1； * 当 x>nx > nx>n 时视为越界（无该结点）； * 遍历顺序为： 先序遍历=左子树→根→右子树\text{先序遍历} = \text{左子树} \rightarrow \text{根} \rightarrow \text{右子树}先序遍历=左子树→根→右子树 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 * 用数组 a[1∼n]a[1\sim n]a[1∼n] 储存树的顺序结构； * 定义一个递归函数 dfs(x)： * 若 x>nx > nx>n：越界，返回； * 否则： * 递归访问左儿子 dfs(2x)； * 输出当前结点 a[x]； * 递归访问右儿子 dfs(2x + 1)； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每个结点被访问一次； * 总时间复杂度为 O(n)\boxed{O(n)}O(n) ； * 空间复杂度为递归栈深度，最坏为 O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 后序遍历 题目大意 给定一个长度为 nnn 的数组，将其构造成完全二叉树的结构（根结点编号为 111，左儿子为 2x2x2x，右儿子为 2x+12x+12x+1），然后输出整棵二叉树的后序遍历结果。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 我们可以把数组想象成完全二叉树的顺序存储结构： * 树的根是数组下标 111； * 每个结点编号 xxx： * 左儿子编号为 2x2x2x； * 右儿子编号为 2x+12x+12x+1； * 当 x>nx > nx>n 时视为越界（无该结点）； * 遍历顺序为： 先序遍历=左子树→右子树→根\text{先序遍历} = \text{左子树} \rightarrow \text{右子树} \rightarrow \text{根}先序遍历=左子树→右子树→根 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 * 用数组 a[1∼n]a[1\sim n]a[1∼n] 储存树的顺序结构； * 定义一个递归函数 dfs(x)： * 若 x>nx > nx>n：越界，返回； * 否则： * 递归访问左儿子 dfs(2x)； * 递归访问右儿子 dfs(2x + 1)； * 输出当前结点 a[x]； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每个结点被访问一次； * 总时间复杂度为 O(n)\boxed{O(n)}O(n) ； * 空间复杂度为递归栈深度，最坏为 O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 求先序遍历 题目大意 给定一棵二叉树的： * 中序遍历字符串 * 后序遍历字符串 请根据这两种遍历结果，重建这棵二叉树的结构，并输出它的 先序遍历。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 我们利用中序和后序遍历的性质： * 后序遍历： 最后一个节点是当前子树的 根节点 * 中序遍历： 根节点左边是 左子树，右边是 右子树 通过递归不断划分左子树和右子树，就可以重建整个先序遍历。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 函数定义 设函数 func(s, t)： * 参数 sss 为当前子树的 中序遍历字符串 * 参数 ttt 为当前子树的 后序遍历字符串 * 根节点是 ttt 的最后一个字符 步骤如下： 1. 找根节点：root=t.back()root = t.back()root=t.back() 2. 在中序中定位根的位置：分出左子树、右子树 3. 递归处理左子树： * 中序：s[0,id−1]s[0, id-1]s[0,id−1] * 后序：t[0,id−1]t[0, id-1]t[0,id−1] 4. 递归处理右子树： * 中序：s[id+1,end]s[id+1, end]s[id+1,end] * 后序：t[id,end−1]t[id, end-1]t[id,end−1] 5. 先输出根，再递归左右子树（先序遍历顺序：根-左-右） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每个结点最多处理一次； * 每次字符串分割代价为 O(n)O(n)O(n)，但总的深度不超过 nnn 层； * 总体时间复杂度 O(n2)\boxed{O(n^2)}O(n2) ，对于 n≤8n \leq 8n≤8 足够。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现

题目 机器人走路 2 最小路径和 古神肥波特 最大开销子字符串 知识闯关大冒险 II 石板问题（中等版） 机器人走路 2 题目大意 一个机器人位于一个 n×mn \times mn×m 的网格左上角，只能向下或向右移动一步，终点为右下角。 网格中有障碍物，不能经过。 现在给定地图，求从起点 (1,1)(1, 1)(1,1) 到终点 (n,m)(n, m)(n,m) 的不同路径数，结果对 114514114514114514 取模。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 本题是一个经典的带障碍物的动态规划路径计数问题。 设地图为 ai,ja_{i,j}ai,j ，其中： * ai,j=0a_{i,j} = 0ai,j =0 表示可以走； * ai,j=1a_{i,j} = 1ai,j =1 表示障碍，不能走。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 一、状态设计 令 dp[i][j]dp[i][j]dp[i][j] 表示从起点 (1,1)(1, 1)(1,1) 到达位置 (i,j)(i, j)(i,j) 的路径条数。 二、状态转移方程 若当前位置 ai,j=1a_{i,j} = 1ai,j =1（是障碍），则 dp[i][j]=0dp[i][j] = 0dp[i][j]=0； 否则可以由上方或左方走来： dp[i][j]={0,如果 a[i][j]=1dp[i−1][j]+dp[i][j−1],否则dp[i][j] = \begin{cases} 0, & \text{如果 } a[i][j] = 1 \\ dp[i-1][j] + dp[i][j-1], & \text{否则} \end{cases}dp[i][j]={0,dp[i−1][j]+dp[i][j−1], 如果 a[i][j]=1否则 注意对 114514114514114514 取模。 三、初始状态 起点 (1,1)(1, 1)(1,1) 若为可通位置，则 dp[1][1]=1dp[1][1] = 1dp[1][1]=1； 其余位置可用上述转移公式逐行填充。 四、最终答案 输出 dp[n][m]dp[n][m]dp[n][m]。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 状态数为 n×mn \times mn×m； * 每个状态转移 O(1)O(1)O(1)； 总时间复杂度为 O(n×m)\boxed{O(n \times m)}O(n×m) 。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++代码实现 最小路径和 题目大意 在一个 n×mn \times mn×m 的网格中，每个格子包含一个非负整数 ai,ja_{i,j}ai,j ，表示从该格子经过的代价。 机器人从左上角 (1,1)(1,1)(1,1) 出发，每次只能向右或下走一步，目标是走到右下角 (n,m)(n,m)(n,m)。请你求出一条代价最小的路径，输出其总代价。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 状态受限于只能向右或向下； * 每个位置只能从左边或上边转移来； * 是典型的 二维动态规划路径代价最小值问题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 一、状态定义 令 dp[i][j]dp[i][j]dp[i][j] 表示走到第 iii 行第 jjj 列的最小路径和。 二、状态转移方程 从左或上转移而来： dp[i][j]=min⁡(dp[i−1][j], dp[i][j−1])+a[i][j]dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j]dp[i][j]=min(dp[i−1][j], dp[i][j−1])+a[i][j] 三、边界初始化 * dp[1][1]=a[1][1]dp[1][1] = a[1][1]dp[1][1]=a[1][1]； * 第一行只能从左走来：dp[1][j]=dp[1][j−1]+a[1][j]dp[1][j] = dp[1][j-1] + a[1][j]dp[1][j]=dp[1][j−1]+a[1][j]； * 第一列只能从上走来：dp[i][1]=dp[i−1][1]+a[i][1]dp[i][1] = dp[i-1][1] + a[i][1]dp[i][1]=dp[i−1][1]+a[i][1]。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 状态数为 n×mn \times mn×m； * 每个状态转移 O(1)O(1)O(1)； 因此总时间复杂度为 O(n×m)\boxed{O(n \times m)}O(n×m) ，空间复杂度为 O(n×m)O(n \times m)O(n×m)（可优化为 O(m)O(m)O(m)）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现（C++） 古神肥波特 题目大意 给定一个长度为 nnn 的股票价格数组 aaa，其中 aia_iai 表示第 iii 天的股价。你只能进行一次买入和一次卖出操作（卖出必须发生在买入之后），求最大可能利润。 如果无论何时买入卖出都无法盈利，输出 000。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一道典型的单次股票买卖最大利润问题。 我们希望找出一段时间 [i,j][i, j][i,j]，使得 i<ji < ji<j 且 aj−aia_j - a_iaj −ai 最大，答案即为该最大值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 我们遍历价格数组，同时维护当前最低买入价，并在每一天尝试计算“若今天卖出，利润是多少”。 一、变量定义 * minPriceminPriceminPrice：到当前为止的最小股价（买入价）； * ansansans：最大利润。 二、状态转移逻辑 遍历 i=1i = 1i=1 到 nnn： * 更新最低买入价： minPrice=min⁡(minPrice,a[i])minPrice = \min(minPrice, a[i])minPrice=min(minPrice,a[i]) * 当前卖出能得到的利润： profit=a[i]−minPriceprofit = a[i] - minPriceprofit=a[i]−minPrice * 更新最大利润： ans=max⁡(ans,profit)ans = \max(ans, profit)ans=max(ans,profit) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 仅需一次遍历数组； * 每步操作均为 O(1)O(1)O(1)； 总时间复杂度为 O(n)\boxed{O(n)}O(n) ，空间复杂度为 O(1)\boxed{O(1)}O(1) 。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码实现 最大开销子字符串 题目大意 给定： * 一个字符串 sss（仅含小写字母）； * 一个字符集 charscharschars，每个字符对应一个自定义价值 valsvalsvals； * 字符在 charscharschars 中时价值为 vals[i]vals[i]vals[i]，否则为其字母序（如 'a' = 1，'b' = 2，…）； * 定义某一子串的开销为其中每个字符的价值之和； * 要求在所有连续子串中找出最大开销。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 要对 sss 中每个字符确定其价值； * 然后问题转化为：求一个数组中的 最大连续子数组和（即经典的 最大子段和问题）； * 可使用动态规划求解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 一、预处理价值映射 * 用一个 int val[26] 数组，初始化为 'a' 到 'z' 的字母序； * 然后根据输入将 chars[i]chars[i]chars[i] 对应的值覆盖进去； * 最终我们可以 O(1)O(1)O(1) 得到任意字符的价值。 二、转换成数值数组 + 最大子段和 将字符串 sss 映射为整数数组 vvv，每个元素为对应字符的价值。 设 dpidp_idpi 为以第 iii 个字符结尾的最大开销： dpi=max⁡(dpi−1+vi, vi)dp_i = \max(dp_{i-1} + v_i, \ v_i)dpi =max(dpi−1 +vi , vi ) 更新最大值：ans=max⁡(ans,dpi)ans = \max(ans, dp_i)ans=max(ans,dpi )。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 预处理价值表：O(m)O(m)O(m)； * 映射整个字符串为价值数组：O(n)O(n)O(n)； * 最大子段和扫描：O(n)O(n)O(n)； 总时间复杂度为 O(n)\boxed{O(n)}O(n) ，适用于 n≤105n \le 10^5n≤105 的数据范围。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码实现 知识闯关大冒险 II 题目大意 有 nnn 个围成一个环的关卡，每个关卡含有 aia_iai 个知识点。你要从中选出若干个关卡来挑战，收集尽可能多的知识点，但有以下限制： * 不能挑战相邻的两个关卡； * 第一个和最后一个关卡也被认为是相邻的。 求你最多能收集的知识点总数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 与一维数组版本相比，它加了一个“首尾相邻”的限制。 由于不能同时选第一个和最后一个元素，我们可以将环“断开”，分成两个线性子问题求解： * 方案一：选择第一个，不能选最后一个 ⇒ 在 a[1∼n−1]a[1 \sim n-1]a[1∼n−1] 上做非环形最大不连续子序列和； * 方案二：不选第一个，可以选最后一个 ⇒ 在 a[2∼n]a[2 \sim n]a[2∼n] 上做同样处理； 最终答案为两者中的最大值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 状态定义 设 dp[i]dp[i]dp[i] 表示在第 iii 个关卡结束时，能收集到的最大知识点数。 状态转移方程 dp[i]=max⁡(dp[i−1],dp[i−2]+a[i])dp[i] = \max(dp[i-1], dp[i-2] + a[i])dp[i]=max(dp[i−1],dp[i−2]+a[i]) 表示当前关卡要么不选（延续上一状态），要么选（加上 i−2i-2i−2 的最优值 + 当前值）。 边界条件 * dp[1]=a[1]dp[1] = a[1]dp[1]=a[1] * dp[2]=max⁡(a[1],a[2])dp[2] = \max(a[1], a[2])dp[2]=max(a[1],a[2]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 两次线性动态规划，每次 O(n)O(n)O(n)； * 总体复杂度：O(n)\boxed{O(n)}O(n) ； * 空间优化后空间复杂度为 O(1)O(1)O(1)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码实现 石板问题（中等版） 题目大意 你站在第 111 块石板上，每次可以选择跨 111、222 或 333 块石板。 问有多少种方法恰好到达第 nnn 块石板？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 起点为第 111 块石板； * 每一步可跨 111、222 或 333 块； * 求到达第 nnn 块石板的方案总数。 注意，题目要求 恰好 到达第 nnn 块石板，因此不能超过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 本题是斐波那契式动态规划的典型模型（可以跳 1、2、3 步）。 状态定义 * 令 dp[i]dp[i]dp[i] 表示到达第 iii 块石板的方案数。 状态转移方程 * 从第 i−1i-1i−1、i−2i-2i−2、i−3i-3i−3 块跳来： dp[i]=dp[i−1]+dp[i−2]+dp[i−3]dp[i] = dp[i-1] + dp[i-2] + dp[i-3]dp[i]=dp[i−1]+dp[i−2]+dp[i−3] 边界条件 * dp[1]=1dp[1] = 1dp[1]=1：起点； * dp[2]=1dp[2] = 1dp[2]=1：只能从 111 跳一步； * dp[3]=2dp[3] = 2dp[3]=2：从 1→31 \to 31→3（跳 2 步），或 1→2→31 \to 2 \to 31→2→3（两次跳 1 步）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每个 dp[i]dp[i]dp[i] 只依赖前 333 项； * 整体复杂度为 O(n)\boxed{O(n)}O(n) ； * 空间复杂度可优化为 O(1)O(1)O(1)（滚动变量形式）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++代码实现

--Dijkstra-- 流程： (一) 定义数组: （1）dis(i)：表示原点到点i的最短路径 （2）vis(i)：标记数组 （3）mp(u,v)：邻接表 (二) 使用邻接表mp存图,mp(u,v)=w（(u,v,w):u到v的距离为w） (三) 初始化dis数组（d[s]=0 原点到自己距离为0，d[2~n]其余设为无穷大 1e9） (四) 遍历(n-1)次 (最后一个点无法更新，确认已经求出最短路径） (1)遍历dis,求出与原点距离最近的且未被标记的点k (2)在vis中标记点k (3)对与点k相连的点v进行松弛操作 （松弛操作：比较 dis(k)+w 与 dis(v),若dis(k)+w<dis(v)，将dis(v)更新为dis(k)+w） (五) 输出dis中每个点与原点的距离 代码示例： 例题： A569.单源最短路径1 A551.单源最短路径2 A24634.道路削减

注意事项1：千万不要点文本末尾的提交按钮（20人提交问卷会被自动关闭，我得手动清理答卷） 注意事项2:答题选择选项后就会有结果！！！ 最后： 试卷链接

111111111111111111111111111111111111111111111111111111111111111111111666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666

可以通过以下网址加入： https://www.acgo.cn/application/1919219649596952576

本团队：Constexpr Crushers Team 推荐团队/合作团名称 队长/简介 南开大学 队长：༺ཌༀ我要上南开ༀད༻ 写c++还是吃皮皮虾 队长：忘川秋库 天之神 队长：🐱‍🚀 滚蛋吧c++ 队长：滚蛋吧c++ 中国国际航空 Air China飞友之家 队长：Air China-胖安达 扫帚世界 队长：阿基米哲V(＾－＾)V 刷题出奇迹，大家一起AC起来呀 队长：阿基米哲V(＾－＾)V 复仇者联盟理事会 Scuderia Ferrari 快点AC！ 我 AC && C++语言 创码魔方 阿基米哲V(＾－＾)V 中华HJSWA共和国 并 c++ ☭中华☭c++ HP 蠢泰大帝国 ༺ཌ𝓒𝓾𝓷𝓽𝓪𝓲ད༻ 附属团/分支 简介 CCT Lite CCT分支团队 负责人： · 广招合作团队与附属团队，有意者请私信

T1钞票问题 T2数字三角形 T3不同的路径 T4传球游戏 T5最长上升子序列 T6最长公共子序列 T7合唱队形 T8挖地雷

点这里 点进题后看题解“刷空间掌握者的看这里内存消耗1.25MB”复制到自己的代码上就行啦！ 对你有帮助的就点个赞吧！

void _start() { const char msg[] = "Hello ACGO\n"; asm volatile( "mov $1, %%rax\n" "mov $1, %%rdi\n" "mov %0, %%rsi\n" "mov $11, %%rdx\n" "syscall\n" "mov $60, %%rax\n" "xor %%rdi, %%rdi\n" "syscall" : : "r"(msg) ); }

> 海岛生存游戏·重制 BETA0.035 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 公告：海岛生存游戏开始重置了！重置版将会修复更多的BUG，更好的游戏体验，以及更刺激的战斗！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ -- -- -- 本版本更新 -- -- -- 1.加入了制作面板 2.加入了奸商 3.修复了对战界面跳转异常的BUG ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点击此处下载海岛生存·重制 BETA0.012 文件下载密码：F47J ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 点击此处下载海岛生存·重制 BETA0.035 文件下载密码：F4GF ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 某些浏览器（如谷歌）可能会报毒，不管它就行 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 团队招人广告

#include<bits/stdc++.h> using namespace std; int main() { cout<<"###.###\n#...#.#\n###.#.#\n..#.#.#\n###.###"; }

黑影如潮水般涌来时，陈默突然将钢笔刺入地面。金色符文以笔尖为中心扩散，形成一道屏障暂时挡住攻击。林深注意到红裙少女指尖缠绕着透明丝线，那些丝线正连接着地下室的所有黑影，原来她才是操控一切的傀儡师。 “切断丝线！” 林深捡起破碎的玻璃片冲上前。苏棠则在一旁翻找容器中的物品，终于在某个浸泡着 1970 年代校服的容器底部，摸到一把刻着蛛网纹路的钥匙。然而当她握住钥匙的瞬间，无数记忆涌入脑海 —— 当年有个女学生发现了图书馆的秘密，被管理员制成了第一具红衣傀儡。 红裙少女察觉到危险，丝线突然暴涨，将三人死死缠住。林深用玻璃片切割丝线，却发现伤口处会立刻长出新的细丝。陈默咬破手指在钢笔上画出血符，符文化作利剑斩断缠绕苏棠的丝线，她趁机将钥匙插入地下室深处的锁孔。 古老的机关启动，地面裂开一道缝隙，露出向下延伸的阶梯。阶梯尽头传来书页翻动的巨响，仿佛有一本巨著正在苏醒。红裙少女发出尖锐的尖叫，她的身体开始变得透明，丝线也随之消散。“你们以为能找到《永夜典章》？” 她的声音带着不甘，“那本书会吞噬所有靠近者的灵魂。” 三人顺着阶梯向下，墙壁上的油灯自动亮起，照亮了两侧的浮雕。浮雕描绘着历代图书馆管理员献祭学生的场景，最后一幅画面中，白发管理员将自己的心脏献给了一本漂浮在空中的黑色巨书。苏棠突然抓住林深的胳膊：“你们听，有心跳声......” 下方传来震耳欲聋的心跳声，每一次跳动都让阶梯震颤。当他们终于抵达底部时，看到一个巨大的血池，池中央漂浮着那本传说中的《永夜典章》。书籍表面布满血管状的纹路，随着心跳声不断起伏，而在血池边缘，白发管理员正背对着他们，手中握着献祭用的匕首。

回到图书馆的主厅，三人发现所有书架都开始自动移动，拼凑成通往地下室的阶梯。阶梯由泛黄的书页堆砌而成，每走一步都能听见压抑的啜泣声从书页间传来。苏棠的手掌按在某块 “台阶” 上，上面突然浮现出一张学生的脸，那人正是照片里瞳孔空洞的少年。 “他们都被困在建筑本身里了......” 林深声音发颤。地下室的铁门紧闭，门上刻着扭曲的规则： 守门者只回答三个问题 它的眼睛是打开门的钥匙 若回答错误，将永远成为守门者的一部分 陈默深吸一口气，叩响铁门。门缝中伸出一只布满皱纹的手，掌心是一颗浑浊的眼球。眼球转动着打量三人，一个沙哑的声音响起：“问题。” “《永夜典章》藏在哪里？” 林深问。眼球突然充血，门内传来怒吼：“触犯禁忌的问题！” 陈默眼疾手快按住即将关闭的门，“第二个问题，如何安全离开图书馆？” 眼球渗出黑色黏液，“遵守不存在的规则。” 苏棠看着不断逼近的触手，急中生智：“最后一个问题，守门者的真名是什么？” 眼球剧烈颤动，铁门缓缓打开，露出里面蜷缩着的人形生物 —— 那是一个被书页包裹的躯体，唯有脸上露出半张白发管理员年轻时的脸。 地下室里摆满玻璃容器，每个容器都浸泡着不同年代的校服。林深在角落发现一本破旧的日记，泛黄的纸页记载着：“1943 年，我用学生的灵魂完成第一次献祭，图书馆开始拥有生命......” 日记的最后一页被血覆盖，隐约能看见 “红衣傀儡” 四个字。 穿红裙的少女不知何时出现在容器顶端，她伸手触碰玻璃，里面的校服突然化作黑色雾气。“你们以为找到了真相？” 她咯咯笑着，“地下室的每具尸体，都是试图成为守门人的失败者。” 话音未落，所有容器同时爆裂，无数黑影朝着三人扑来。

四舍五入的标准方法： round() 函数，正负数都正确 需要包含 <cmath> 头文件 。

题目 石板问题 石板问题（通用跳跃版） 机器人走路 股票投资决策问题 知识闯关大冒险 最小花费爬楼梯 三角形路径挑战 石板问题 题目大意 你站在第 1 块石板上，每次可以走 1 块或 2 块石板，问你有多少种方法恰好走到第 nnn 块石板上。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 起点固定在第 1 块石板； * 目标是第 nnn 块石板； * 每步可以跳 1 或 2 格； * 问一共有多少种合法路径能走到第 nnn 块石板。 这实际上是一个变形的 爬楼梯问题，标准动态规划模型。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路（动态规划） 状态设计 设 f[i]f[i]f[i] 表示恰好走到第 iii 块石板的方案数。 状态转移方程 因为每一步可以从 i−1i-1i−1 或 i−2i-2i−2 跳到 iii，所以有： f[i]=f[i−1]+f[i−2]f[i] = f[i-1] + f[i-2]f[i]=f[i−1]+f[i−2] 初始条件 * f[1]=1f[1] = 1f[1]=1：站在第 1 块，就是 1 种方案。 * f[2]=1f[2] = 1f[2]=1：从 1 → 2，也只有一种方法。 答案 输出 f[n]f[n]f[n] 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 状态数：O(n)O(n)O(n) 个状态； * 每个状态转移耗时 O(1)O(1)O(1)； * 整体时间复杂度为 O(n)O(n)O(n)； * 空间复杂度也是 O(n)O(n)O(n)，若用滚动数组可降至 O(1)O(1)O(1)（但这不是本题重点）。 数据范围 n≤45n \le 45n≤45，故该解法非常高效。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 石板问题（通用跳跃版） 题目大意 你站在第 1 块石板上，每一步可以跨越 111 到 kkk 块石板，问你一共有多少种方法可以恰好走到第 nnn 块石板上，答案对 114514114514114514 取模。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个变种爬楼梯问题，允许步长为 111 到 kkk。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 设 f[i]f[i]f[i] 表示从第 1 块石板恰好走到第 iii 块石板的方案数。 则状态转移为： f[i]=∑j=1kf[i−j]当 i−j≥1f[i] = \sum_{j=1}^{k} f[i-j] \quad \text{当 } i-j \geq 1f[i]=∑j=1k f[i−j]当 i−j≥1 注意： * 初始时 f[1]=1f[1] = 1f[1]=1（从第1块出发，不动就是1种方式） * 对于所有 iii，我们只从之前 kkk 步内的状态转移过来。 * 所有计算均取模 114514114514114514。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 外层循环 O(n)O(n)O(n)； * 内层最多循环 kkk 次； * 整体时间复杂度：O(nk)O(nk)O(nk)； * 空间复杂度：O(n)O(n)O(n)； * 数据范围：1≤n≤105, 1≤k≤1001 \leq n \leq 10^5,\ 1 \leq k \leq 1001≤n≤105, 1≤k≤100，在时间限制内可以通过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 机器人走路 题目大意 给一个 n×mn \times mn×m 的网格，机器人从左上角 (1,1)(1,1)(1,1) 出发，每次只能向右或下走一步，求走到右下角 (n,m)(n,m)(n,m) 的不同路径总数，答案对 114514114514114514 取模。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个典型的动态规划（DP）路径计数问题。本质上是求从左上角走到右下角的组合数路径问题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 状态表示： 令 dp[i][j]dp[i][j]dp[i][j] 表示从 (1,1)(1,1)(1,1) 走到 (i,j)(i,j)(i,j) 的路径总数。 状态转移： 每个位置 (i,j)(i,j)(i,j) 的路径数等于其上方和左方的路径数之和： dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1] 因为： * 从 (i−1,j)(i-1,j)(i−1,j) 向下可以到 (i,j)(i,j)(i,j)； * 从 (i,j−1)(i,j-1)(i,j−1) 向右可以到 (i,j)(i,j)(i,j)。 边界条件： * dp[1][1]=1dp[1][1] = 1dp[1][1]=1，表示起点的路径数为 1； * 对于边界第一行和第一列，只能从一个方向走。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 状态数量：O(n⋅m)O(n \cdot m)O(n⋅m)； * 每个状态转移：O(1)O(1)O(1)； * 总时间复杂度：O(n⋅m)O(n \cdot m)O(n⋅m)； * 空间复杂度：O(n⋅m)O(n \cdot m)O(n⋅m)； * 在 n,m≤1000n, m \leq 1000n,m≤1000 的情况下，可以通过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 股票投资决策问题 题目大意 给定一个长度为 nnn 的整数数组 aaa，其中 aia_iai 表示第 iii 天股票价格的涨跌幅度（正数表示涨，负数表示跌）。你需要选择一个连续子数组，使得子数组的元素和最大。输出这个最大收益值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 可以看成一个一维数组求最大子段和的问题。 * 需要找一个连续区间 [l,r][l, r][l,r]，使得 ∑i=lrai\sum_{i=l}^{r} a_i∑i=lr ai 最大。 * 即便所有数都是负数，也要选择一个最小的负数（至少要选一天）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 状态表示： * 令 dp[i]dp[i]dp[i] 表示以第 iii 天为结尾的连续区间的最大收益。 状态转移： * dp[i]=max⁡(dp[i−1]+a[i], a[i])dp[i] = \max(dp[i-1] + a[i],\ a[i])dp[i]=max(dp[i−1]+a[i], a[i]) 意思是：要么接上前面的最大段（继续累计），要么重新开始从第 iii 天开始。 初始值： * dp[1]=a[1]dp[1] = a[1]dp[1]=a[1]，因为第一个数只能自己成段。 最终答案： * 所有 dp[i]dp[i]dp[i] 中的最大值，即 max⁡(dp[1∼n])\max(dp[1 \sim n])max(dp[1∼n]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 时间复杂度：O(n)O(n)O(n)，只需遍历一次数组； * 空间复杂度：O(n)O(n)O(n)，但可进一步优化为 O(1)O(1)O(1)（只记录上一个状态和答案）； ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 知识闯关大冒险 题目大意 给出一个整数数组 aaa，其中 aia_iai 表示第 iii 个关卡可以获得的知识点数。你最多可以选取一些不相邻的关卡，使得获得的知识点总和最大。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 不能选相邻关卡，意味着如果选了第 iii 个关卡，就不能选 i−1i-1i−1。 * 本质是一个子序列选择问题，但有相邻元素限制。 * 动态规划是最自然的思路。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 定义状态： * dp[i]dp[i]dp[i] 表示前 iii 个关卡中，在不挑战相邻关卡的前提下最多可以收集的知识点数量。 状态转移： * 对于第 iii 关，有两种情况： 1. 不选第 iii 个：那最多是 dp[i−1]dp[i-1]dp[i−1] 2. 选第 iii 个：那第 i−1i-1i−1 个不能选，总和为 dp[i−2]+a[i]dp[i-2] + a[i]dp[i−2]+a[i] * 所以状态转移方程为： dp[i]=max⁡(dp[i−1], dp[i−2]+a[i])dp[i] = \max(dp[i-1],\ dp[i-2] + a[i])dp[i]=max(dp[i−1], dp[i−2]+a[i]) 初始值： * dp[1]=a[1]dp[1] = a[1]dp[1]=a[1] * dp[2]=max⁡(a[1],a[2])dp[2] = \max(a[1], a[2])dp[2]=max(a[1],a[2]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 时间复杂度：O(n)O(n)O(n)，一次遍历计算所有状态； * 空间复杂度：O(n)O(n)O(n)，如果使用数组存储全部状态；可以优化成 O(1)O(1)O(1) 空间。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最小花费爬楼梯 题目大意 给定一个长度为 nnn 的数组 aaa，其中 aia_iai 表示踩在第 iii 个台阶上的花费。你从第 000 层出发，每次可以跳一阶或两阶，问最小花费爬到第 nnn 层（楼顶，不用支付代价）是多少。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 台阶编号为 0∼n−10 \sim n-10∼n−1； * 终点是第 nnn 层，不需要付费； * 起点可以从第 0 或第 1 个台阶起跳； * 每次只能跳 1 或 2 阶； * 最后一步可以从 n−1n-1n−1 或 n−2n-2n−2 跳到楼顶。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 令 dp[i] 表示跳到第 iii 个台阶所需的最小花费，则： * 初始状态： dp[0]=a[0],dp[1]=a[1]dp[0] = a[0],\quad dp[1] = a[1]dp[0]=a[0],dp[1]=a[1] * 状态转移方程： dp[i]=min⁡(dp[i−1], dp[i−2])+a[i]dp[i] = \min(dp[i-1],\ dp[i-2]) + a[i]dp[i]=min(dp[i−1], dp[i−2])+a[i] * 注意：我们的目标是跳到“第 n 层（楼顶）”，不需要再支付费用，因此最终结果是： min⁡(dp[n−1], dp[n−2])\min(dp[n-1],\ dp[n-2])min(dp[n−1], dp[n−2]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 时间复杂度：O(n)O(n)O(n) * 空间复杂度：O(n)O(n)O(n)（可优化到 O(1)O(1)O(1)） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三角形路径挑战 题目大意 给你一个数字三角形，从顶端出发，每一步只能向下一行的相邻两个位置之一走，问从顶到底的最小路径和是多少。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 本质是一个有结构限制的路径最优化问题。 * 如果当前在第 iii 行第 jjj 个位置，则下一步只能走到第 i+1i+1i+1 行的第 jjj 或第 j+1j+1j+1 个位置。 * 求从顶部到底部的路径总和最小值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用动态规划（DP），核心思想是自顶向下或自底向上进行状态转移。 令 dp[i][j] 表示从顶端走到第 iii 行第 jjj 个位置的最小路径和。 * 状态转移方程： dp[i][j]=min⁡(dp[i−1][j],dp[i−1][j−1])+a[i][j]dp[i][j] = \min(dp[i-1][j], dp[i-1][j-1]) + a[i][j]dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+a[i][j] * 边界情况： * dp[1][1] = a[1][1] * 为防止访问越界，可以在初始化 dp[i][j] 时全部赋值为一个很大值（如 10910^9109），然后只在合法下标内转移。 * 最终答案： * 是最底层的所有 dp[n][i] 中的最小值，即： min⁡(dp[n][1],dp[n][2],...,dp[n][n])\min(dp[n][1], dp[n][2], ..., dp[n][n])min(dp[n][1],dp[n][2],...,dp[n][n]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 状态数：每层 iii 有 iii 个元素，总状态数为 O(n2)O(n^2)O(n2)； * 每个状态计算复杂度为 O(1)O(1)O(1)； * 总时间复杂度为 O(n2)O(n^2)O(n2)，可接受。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示

题目 求和 桐桐撒金币 【前缀和与差分】小码君的荣耀 投票箱 卡牌 暴躁的病人 求和 题目大意 给定 nnn 个整数 a1,a2,…,ana_1, a_2, \dots, a_na1 ,a2 ,…,an ，要求计算所有两两不同的乘积之和，即： S=∑1≤i<j≤nai⋅ajS = \sum_{1 \le i < j \le n} a_i \cdot a_jS=∑1≤i<j≤n ai ⋅aj 例如，当 a=[1,2,3]a = [1, 2, 3]a=[1,2,3] 时： S=1⋅2+1⋅3+2⋅3=11S = 1 \cdot 2 + 1 \cdot 3 + 2 \cdot 3 = 11S=1⋅2+1⋅3+2⋅3=11 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 本题目要求计算 ai⋅aja_i \cdot a_jai ⋅aj 的总和，满足 1≤i<j≤n1 \le i < j \le n1≤i<j≤n。 直接做法是使用两层循环枚举所有的 i,ji, ji,j，时间复杂度为 O(n2)O(n^2)O(n2)，当 nnn 较大时会超时。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 我们可以利用数学变形将其优化为线性算法。 观察下面的展开形式： S=a1⋅(a2+a3+⋯+an)+a2⋅(a3+⋯+an)+⋯+an−1⋅anS = a_1 \cdot (a_2 + a_3 + \dots + a_n) + a_2 \cdot (a_3 + \dots + a_n) + \dots + a_{n-1} \cdot a_nS=a1 ⋅(a2 +a3 +⋯+an )+a2 ⋅(a3 +⋯+an )+⋯+an−1 ⋅an 即： S=∑i=1n−1ai⋅(∑j=i+1naj)S = \sum_{i=1}^{n-1} a_i \cdot \left( \sum_{j=i+1}^{n} a_j \right)S=∑i=1n−1 ai ⋅(∑j=i+1n aj ) 因此，我们可以： 1. 先计算前缀和数组 prei=∑k=1iakpre_i = \sum_{k=1}^{i} a_kprei =∑k=1i ak ； 2. 对于每个 aia_iai ，它的贡献是 ai⋅(pren−prei)a_i \cdot (pre_n - pre_i)ai ⋅(pren −prei )； 3. 将所有这些贡献累加得到答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 计算前缀和：O(n)O(n)O(n)； * 枚举每个 iii 计算贡献：O(n)O(n)O(n)； * 总时间复杂度为 O(n)O(n)O(n)； * 空间复杂度为 O(n)O(n)O(n)（用于存储数组和前缀和）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 桐桐撒金币 题目大意 桐桐在一条公路上撒金币，每一公里都有一些金币。你需要处理 kkk 次询问，每次询问某一段区间 [l,r][l, r][l,r] 上金币的总和。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 本题本质是一个经典的区间和查询问题。 给定一个长度为 nnn 的数组 aaa，和 kkk 个区间 [l,r][l, r][l,r]，每次要回答： 区间和=al+al+1+⋯+ar\text{区间和} = a_l + a_{l+1} + \dots + a_r区间和=al +al+1 +⋯+ar 直接每次遍历 [l,r][l, r][l,r] 会超时，最坏情况下时间复杂度 O(nk)O(nk)O(nk)。 我们考虑使用前缀和优化查询，将每次查询降为 O(1)O(1)O(1)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用前缀和数组 preprepre： * 定义 pre[i]=a1+a2+⋯+aipre[i] = a_1 + a_2 + \dots + a_ipre[i]=a1 +a2 +⋯+ai * 则有： 区间[l,r]的和=pre[r]−pre[l−1]\text{区间} [l, r] \text{的和} = pre[r] - pre[l - 1]区间[l,r]的和=pre[r]−pre[l−1] 实现步骤： 1. 输入数组并构建前缀和； 2. 对每个区间查询，使用前缀和快速计算答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 构建前缀和数组：O(n)O(n)O(n)； * 每次查询使用 O(1)O(1)O(1)，共 kkk 次，总计 O(k)O(k)O(k)； * 总时间复杂度为 O(n+k)O(n + k)O(n+k)； * 空间复杂度 O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 投票箱 题目大意 有 NNN 个城市，总共 BBB 个投票箱。第 iii 个城市有 aia_iai 名选民。现需为每个城市分配至少一个投票箱，且每位选民必须在其城市被分配的投票箱中投票。每个投票箱可以服务一定数量的选民。 目标是通过合理分配投票箱，使得“单个投票箱服务的最大人数”尽可能小。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一道最小化最大值的优化问题。 * 每个城市必须分至少一个箱子。 * 每个城市内，可以将人口均匀分配到多个箱子中，向上取整即为该城市所需投票箱数。 * 我们要找的是一个值 xxx，使得所有城市中，任意一个投票箱服务的人数不超过 xxx，且所需的总投票箱数量不超过 BBB。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 二分答案 我们可以二分答案 xxx（即单个投票箱服务的人数），判断是否存在一个分配方案使得所有选民都能完成投票且不超过 BBB 个箱子。 2. 检查函数 CHECK(X) 对于当前猜测的最大投票箱负载 xxx，我们要判断是否可以在不超过 BBB 个投票箱的前提下覆盖所有人口： * 每个城市 iii 至少需要 ⌈aix⌉\left\lceil \frac{a_i}{x} \right\rceil⌈xai ⌉ 个箱子； * 累加所有城市所需的箱子数是否小于等于 BBB。 如果可以，说明 xxx 还可以继续减小；否则 xxx 太小了，不能满足要求。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 每组数据最多有 555 组。 * 二分最多查找 log⁡2(5×106)≈23\log_2(5 \times 10^6) \approx 23log2 (5×106)≈23 次； * 每次判断 O(N)O(N)O(N)，所以总复杂度约为 O(T⋅Nlog⁡M)O(T \cdot N \log M)O(T⋅NlogM)，可以接受。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 卡牌 题目大意 有 nnn 种卡牌，第 iii 种卡牌已有 aia_iai 张。还有 mmm 张空白卡牌可以涂写，但第 iii 种卡牌最多可以涂写 bib_ibi 张。现在你要尽可能多地组成“完整套牌”，即每套包含每种卡牌各一张。问：最多能组成多少套完整的卡牌？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 每组成一套完整的卡牌，需要每种卡牌各一张。若某种卡牌数量不够，可使用空白卡牌进行补充，但不能超过该种牌可手写上限 bib_ibi ，总手写卡牌数量不能超过 mmm。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用二分答案来判断最多能组成多少套完整的卡牌： 1. 枚举可以组成的套数 xxx； 2. 对于每个种类的卡牌： * 如果已有 ai≥xa_i \ge xai ≥x，无需补； * 如果 ai<xa_i < xai <x，需要补 x−aix - a_ix−ai 张，且不能超过 bib_ibi ； 3. 所有需要补的数量不能超过总空白卡牌数 mmm。 为了保证复杂度最优，采用倒序线性判断（f_20() 函数）或 二分查找（f() 函数）都可以。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 最坏情况每次判断 O(n)O(n)O(n)； * f_20() 复杂度为 O(n⋅A)O(n \cdot A)O(n⋅A)，其中 A=m/n+max⁡(ai)A = m/n + \max(a_i)A=m/n+max(ai )； * f() 为 O(n⋅log⁡A)O(n \cdot \log A)O(n⋅logA)，推荐在数据范围较大时使用； * 对于 n≤2×105n \le 2 \times 10^5n≤2×105，m≤5×106m \le 5 \times 10^6m≤5×106 是可接受的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 暴躁的病人 题目大意 有 NNN 个病房，坐标分别为 x1,x2,…,xNx_1, x_2, \dots, x_Nx1 ,x2 ,…,xN ，共 CCC 个病人。 需要将这 CCC 个病人安置在病房中，使得任意两个相邻病人的距离尽可能大。 求这个“最大化的最小相邻距离”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 这是一个典型的最大化最小间距问题，类似于“放置C个元素，使它们之间的最小距离最大”。 * 约束： * 每个病人占一个病房； * 病房的坐标可能无序，需要先排序； * 目标是找到一个最小距离 ddd，使得能把 CCC 个病人安排进病房，使得任意两人之间距离至少 ddd。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 先排序 将病房坐标 xix_ixi 按升序排序。 2. 二分距离 用二分法枚举最小距离 midmidmid： * 判定函数 check(mid) 判断能否安排 CCC 个病人在病房中，使得任意两人距离至少为 midmidmid。 * 方法： * 第一个病人安排在第一个病房（下标1）； * 遍历后续病房，若当前病房和上一个安排病人的病房距离 ≥mid\ge mid≥mid，则安排一个病人； * 统计安排了多少病人，若 ≥C\ge C≥C，则说明可以用 midmidmid 距离安排，返回真。 3. 二分调整 * 初始左右边界：l=0l=0l=0，r=max⁡(x)−min⁡(x)r= \max(x) - \min(x)r=max(x)−min(x)（最大坐标差）。 * 若 check(mid) 成功，更新答案，尝试更大距离 l=mid+1l=mid+1l=mid+1； * 否则缩小距离 r=mid−1r=mid-1r=mid−1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示

题目 小蚂蚁吃米 连续自然数和 差分 语文成绩 买凤梨 小蚂蚁吃米 题目大意 有一个长度为 nnn 的数组，表示小蚂蚁每天吃的白大米数量。现在有 qqq 次查询，每次查询给出区间 [L,R][L, R][L,R]，要求输出小蚂蚁这段时间内吃的大米总数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 需要多次快速求数组区间和。 * 由于 n,qn, qn,q 可以较大，使用前缀和数组预处理。 * 查询复杂度可以降到 O(1)O(1)O(1)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 预处理前缀和数组 preprepre，其中 pre[i]=a1+a2+⋯+aipre[i] = a_1 + a_2 + \cdots + a_ipre[i]=a1 +a2 +⋯+ai 1. 对于查询 [L,R][L, R][L,R]，结果为 pre[R]−pre[L−1]pre[R] - pre[L-1]pre[R]−pre[L−1] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 连续自然数和 题目描述 给定一个正整数 MMM，找出所有连续正整数区间，区间长度至少为2，且区间内所有数之和等于 MMM。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 输入格式 一个整数 MMM。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 输出格式 按起始数字从小到大，输出所有满足条件的区间，每行两个整数，表示起始数和结束数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 利用前缀和数组快速计算区间和； * 枚举左端点 lll，对每个 lll 从 l+1l+1l+1 开始枚举右端点 rrr； * 当区间和等于 MMM 输出结果； * 当区间和超过 MMM 立即跳出该轮循环（剪枝）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 差分 题目描述 给定一个长度为 nnn 的整数序列，进行 mmm 次区间加法操作，每次操作给区间 [l,r][l, r][l,r] 上的所有元素加上一个整数 ccc。最后输出操作后的序列。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 利用差分数组可以将区间加法的操作转化为两端点的加减操作，从而实现 O(1)O(1)O(1) 时间内完成区间修改，最后再根据差分数组恢复出最终序列。 具体步骤： 1. 初始化差分数组 ddd，长度为 nnn： d[1]=a1,d[i]=ai−ai−1(2≤i≤n)d[1] = a_1, \quad d[i] = a_i - a_{i-1} \quad (2 \le i \le n)d[1]=a1 ,d[i]=ai −ai−1 (2≤i≤n) 2. 对于每个操作 [l,r,c][l, r, c][l,r,c]： d[l]+=cd[l] += cd[l]+=c 如果 r+1≤nr+1 \le nr+1≤n，则： d[r+1]−=cd[r+1] -= cd[r+1]−=c 3. 对差分数组做前缀和还原序列： ai=∑k=1id[k]a_i = \sum_{k=1}^i d[k]ai =∑k=1i d[k] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码示范 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 语文成绩 题目大意 有 nnn 个学生，给出每个学生的初始语文成绩。老师将对多个区间进行加分操作，每次给第 xxx 到第 yyy 个学生的成绩都加上 zzz 分。你需要输出所有操作完成后，全班学生的最低分。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 这是一个典型的 区间加法操作 问题，使用朴素做法每次遍历 [x,y][x, y][x,y] 区间将会导致 O(pn)O(pn)O(pn) 的复杂度，显然超时。可以使用 差分数组 优化为 O(n+p)O(n + p)O(n+p) 时间。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 设数组 aaa 表示成绩数组，差分数组 ddd 定义为： * d[1]=a[1]d[1] = a[1]d[1]=a[1] * d[i]=a[i]−a[i−1](2≤i≤n)d[i] = a[i] - a[i - 1] \quad (2 \le i \le n)d[i]=a[i]−a[i−1](2≤i≤n) 对于区间加法 [x,y][x, y][x,y] 加 zzz，只需： * d[x]+=zd[x] += zd[x]+=z * d[y+1]−=zd[y + 1] -= zd[y+1]−=z 操作完后，再通过前缀和还原原数组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 构造差分数组：O(n)O(n)O(n) * 处理 ppp 次加法操作：O(p)O(p)O(p) * 还原数组并找最小值：O(n)O(n)O(n) 总时间复杂度为：O(n+p)O(n + p)O(n+p)，完全可以应对 n,p≤5×105n, p \leq 5 \times 10^5n,p≤5×105 的数据范围。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 买凤梨 题目大意 你有 nnn 本美食书，每本书推荐了一个甜度区间 [l,r][l, r][l,r]。 如果一个甜度被 不少于 kkk 本书推荐，则这个甜度是“合适”的。 现在有 qqq 次询问，每次询问一个区间 [l,r][l, r][l,r]，你需要回答这个区间中有多少个“合适”的甜度。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 本质上是区间统计问题。 * 每本书推荐了一个甜度区间 → 相当于这个区间里的每一个甜度值 xxx 被推荐了一次。 * 若一个甜度值 xxx 被推荐的次数 ≥k\ge k≥k，则称它是合适甜度。 我们需要支持： * 快速判断一个甜度是否合适； * 快速查询某一甜度区间中有多少个甜度是合适的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用 差分数组 + 前缀和优化： 1. 使用差分数组 a[i]，对每个推荐区间 [l,r][l, r][l,r]： * a[l]+=1a[l] += 1a[l]+=1 * a[r+1]−=1a[r+1] -= 1a[r+1]−=1 2. 遍历一遍求前缀和 a[i]a[i]a[i]，得到每个甜度值被推荐了多少次。 3. 另设一个数组 ok[i]，如果 a[i]≥ka[i] \ge ka[i]≥k，则令 ok[i] = 1，否则为 000。 4. 再对 ok[i] 求前缀和。 5. 对于每次询问 [l,r][l, r][l,r]，答案就是 ok[r] - ok[l-1]。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 差分与前缀和：O(MAX)O(\text{MAX})O(MAX)，其中 MAX=2×105\text{MAX} = 2 \times 10^5MAX=2×105 * 每次询问时间复杂度：O(1)O(1)O(1)，共 qqq 次，总代价 O(q)O(q)O(q) * 总时间复杂度：O(n+MAX+q)=O(2×105)O(n + \text{MAX} + q) = O(2 \times 10^5)O(n+MAX+q)=O(2×105) 级别 可以应对所有数据范围。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现

代码有的是AI编写，有的是我自己的，出现错误可提建议 六月二十五日肝到10点，六月二十六日发布 第二章 九又四分之三站台的异常 雨水像破碎的代码般从伦敦铅灰色的天空倾泻而下，打在国 王十字车站的玻璃穹顶上发出密集的敲击声。哈利拖着阿不思的行李车穿梭在拥挤的人群中，每走一步都感觉有什么东西在监视着他们。 "你真的确定是第九和第十站台之间？"阿不思小声问道，手指紧紧攥着崭新的霍格沃茨特快车票。他的眼睛不时瞟向周围拿着智能手机的麻瓜，生怕有人注意到他们正朝一堵坚实的砖墙前进。 哈利没有立即回答。他的目光锁定在站台中央巨大的电子时刻表上——那些滚动的黄色文字突然停滞，然后扭曲成诡异的符号： "别看那个。"哈利迅速挡住阿不思的视线，同时抽出魔杖在袖子里轻轻一抖。一个隐蔽的"混淆视听"咒语飞向时刻表，屏幕闪烁几下恢复了正常。但哈利注意到，在恢复正常的最后一帧，屏幕上闪过一行小字： "爸爸？"阿不思拽了拽哈利的袖子，"你脸色好苍白。" "只是...想起我第一次去霍格沃茨的情景。"哈利勉强挤出一个微笑，把行李车调整到冲刺角度。"记住，要全速冲过去，别犹豫。如果你害怕，可以闭上眼睛——" 他的话戛然而止。整个车站的电子设备突然同时发出刺耳的蜂鸣声。安检仪器的屏幕、自动售货机的显示屏、甚至旅客们的手机——全都闪烁着血红色的警告： "趴下！"哈利本能地将阿不思护在身下。但预想中的爆炸没有发生，取而代之的是一个轻柔的电子女声从车站广播系统传出： "系统通知：九又四分之三站台正在进行魔法升级，请旅客改由七又二分之一站台登车。重复，这不是系统错误..." 哈利倒吸一口凉气。七又二分之一站台？魔法世界根本没有这个站台！ "爸爸，那是什么？"阿不思指着他们原本要冲向的那堵墙。砖块表面正在蠕动重组，逐渐形成一个巨大的二进制时钟，显示着： 更可怕的是，时钟下方浮现出一行小字： "我们得立刻离开这里。"哈利压低声音说，同时快速环顾四周寻找其他巫师家庭。但整个车站仿佛只剩下他们父子二人，就连刚才还熙熙攘攘的人群也消失得无影无踪。 就在这时，阿不思的行李箱突然自动弹开。里面崭新的《标准咒语，初级》飘到空中，书页疯狂翻动，最后停在空白页面上。羽毛笔自己跳出来，在纸上潦草地写下一段信息： "这是陷阱。"哈利立刻用魔杖点燃了那张纸。灰烬落地的瞬间，整个车站的灯光开始频闪，在明暗交替中，哈利看到十几个模糊的身影正从四面八方缓缓逼近——那些"旅客"的身体由流动的代码组成，面部是空白的显示屏。 "跑！"哈利抓起阿不思的手冲向男厕所方向。身后传来机械的合成音： "目标拒绝更新。执行强制协议..." 男厕所的门在哈利一个"阿拉霍洞开"下猛地弹开。第三隔间的门上有用荧光涂料画的死亡圣器标志，但三角形里嵌套的是一个像素化的骷髅头。 "阿不思，进去！快！"哈利推着儿子进入隔间，自己转身对着追来的代码人形举起魔杖："障碍重重！" 咒语产生的透明屏障上立刻爬满了蠕动的绿色病毒图案，迅速腐蚀着魔法防御。 "口令！"隔间墙壁上突然弹出一个老旧的机械键盘。 阿不思颤抖着输入：" 键盘发出刺耳的确认音，抽水马桶突然分裂成两半，露出一个向下延伸的螺旋楼梯，散发着诡异的蓝光。 "跳下去！"哈利喊道，同时对着即将冲来的屏障补了一个铁甲咒。这次咒语完全失效——魔杖尖端喷出的不是银色护盾，而是一串乱码： 父子俩跌入通道的瞬间，哈利听到上方传来冰冷的宣告： "逃逸进程检测。启动追踪协议： 螺旋楼梯像DNA链般旋转下降，墙壁上镶嵌的不是火把，而是闪烁着命令行的LED面板。阿不思在坠落中紧紧抓住哈利的胳膊："这是去霍格沃茨的路吗？" "我不确定这是去哪的路。"哈利诚实回答。他注意到某些命令行中反复出现的函数调用： 突然，他们跌入一个宽敞的圆形石室。这里像是某个古老地铁站和现代数据中心的结合体——石墙上刻满古代如尼文，但地面上铺设着光纤电缆，汇聚到中央一个发光的池子里。 "欢迎来到第0x7F层。"一个熟悉的声音从阴影处传来。德拉科·马尔福缓缓走出，不再是哈利记忆中那个趾高气扬的少爷。现在的马尔福面色灰白，左眼戴着单片数据分析镜，右手握着一根通体透明的魔杖，内部可见电流般的代码流动。 "马尔福？"哈利立刻将阿不思护在身后，"你参与了这个？" "参与？"马尔福冷笑一声，单片镜上快速滚动着数据流，"波特，你还是这么自以为是。我是来阻止它的。" 他举起那根透明魔杖，在空中画出一个复杂的符号。石室突然亮起，展现出令人毛骨悚然的景象——数十个玻璃培养舱排列在四周，每个舱内都漂浮着一个沉睡的孩童，他们太阳穴连接着数据线，头顶投影着各自的魔杖核心结构图。 "他们在利用小巫师的魔力调试诅咒代码。"马尔福的声音低沉而急促，"我儿子差点成为下一个实验品。" 阿不思倒吸一口凉气："斯科皮在哪？" "安全了，暂时。"马尔福走向中央光池，"但整个魔法界的魔杖都面临感染风险。包括你的，波特。" 哈利突然意识到自己的冬青木魔杖正在微微发热。他举起一看，杖身上不知何时出现了细如发光的裂纹，里面透出诡异的蓝光。 "这是什么？"哈利震惊地问。 "第一阶段感染。"马尔福在光池上轻点几下，调出一个全息投影——霍格沃茨的3D模型，但城堡被密密麻麻的红色网络包裹，"诅咒会在月蚀之夜全面激活，将所有魔杖变成远程执行终端。" 投影切换成一段代码： 阿不思突然指着其中一个培养舱："爸爸，看！" 哈利转头，血液瞬间冻结——舱体标签上写着"哈利·詹姆·波特 - 第7次扫描"。里面的男孩约莫十一岁，额头上有一道闪电形伤疤。 "他们复制了你的魔法签名。"马尔福说，"用你对抗黑 魔 王的经历作为武器测试平台。" 刺耳的警报突然响彻石室。光池上浮现警告： "没时间了。"马尔福塞给哈利一片晶体，"这是反向工程出的净化代码。找到赫敏，告诉她查找'马沃罗的戒指'里的调试后门。" 石室开始摊塌，代码人形从墙壁渗出。马尔福举起透明魔杖，射出一道银色光芒打开新的通道："走！这通向真正的九又四分之三站台！" 哈利拉着阿不思冲向通道，最后回头看了一眼。马尔福正被数十个代码人形包围，他的单片镜已经碎裂，但依然在输入着什么。哈利清晰地看到他用魔杖在空中写下最后一行代码： 通道关闭的最后一刻，哈利父子跌入熟悉的九又四分之三站台。蒸汽机车喷出的浓烟，学生们的喧闹声，推着行李车的家长们——一切都正常得令人心痛。 "爸爸，那是..."阿不思脸色苍白如纸。 "别告诉任何人我们看到的。"哈利低声警告，同时悄悄检查自己的魔杖——那些发光的裂纹已经消失，但杖尖偶尔会迸出异常的火花。 霍格沃茨特快列车的汽笛声响起。哈利与阿不思登上列车，在关门上的最后一刻，他注意到站台边缘的阴影里，一个戴兜帽的身影正用平板电脑对准他们。屏幕上清晰显示着： [接下来的故事将揭示：分院帽隐藏的编程秘密、霍格沃茨城堡突然出现的异常区域、以及阿不思在列车上遇到的神秘女孩似乎知道关于代码诅咒的真相...] 附：为什么我写的马尔福变好了

不一定要做出来，偏分就行（除不想偷懒的人)