题目链接  BISHI51 低买高卖  题目描述 给定预测的天数  和股票第  天的收盘价 ，每天最多可操作一次，每次可以买入或卖出一股，或不操作。初始时无持仓，且不能做空；第  天收盘时必须清空所有持仓。请设计买卖策略，使得最终获得收益最大，并输出该最大收益。 解题思路 我们使用“反悔贪心”策略：维护一个最小堆来存储已买入的股价。遍历每一天的股价 ：  将  入堆。 若堆顶价格小于当前价格 ，说明可以用最低买入价“反悔”并在当前价卖出一股，获得收益 ：  弹出堆顶，累加收益  再将  入堆，保持与之后交易的衔接。 最终堆中元素会对应未被卖出的买入记录，变量 profit 为最大收益。该算法时...

题目链接  【模板】马拉车算法  题目描述 给定一个仅由小写字母组成的字符串 ，长度为 。请计算  的最长回文子串的长度。 解题思路  马拉车（Manacher）算法：在线性时间  求最长回文子串。 预处理：将原串插入分隔符，形如：  再在两端加上哨兵（如 ^ 与 $），统一奇偶长度回文的处理。设新串长度为 。 核心变量：  ：当前已知回文最长右边界对应的中心； ：该回文的最右端位置； ：以位置  为中心的“回文半径”（包含分隔符的半径）。   线性扩展：对每个 ，若 ，可先取  作为初值，再向两侧继续匹配扩展。若超出，则更新 。 答案换算：最终结果为 （减去分隔符的影响）。  代码   c+...

题目链接  【模板】Trie 字典树  题目描述 给定  个模式串  与  次查询。每次给定一个字符串 ，需要统计使得  为  的前缀的模式串个数（区分大小写，字母范围为大小写英文字母）。 解题思路  用 Trie 逐字符插入每个 ，在每个节点维护通过该节点的计数 （即有多少模式串以该节点路径为前缀）。 回答查询 ：沿 Trie 匹配 。若中途不存在边，则答案为 ；否则返回终止节点的 。 字母表大小为 （先小写后大写或反之均可），用数组下标映射字符以获得线性时间。  代码   c++   java   python   #include <bits/stdc++.h> using ...

题目链接  【模板】前缀函数（kmp）  题目描述 给定字符串  的多个查询。对每个查询字符串（长度为 ），定义其前缀函数 ： 为  的最长相等真前缀与真后缀的长度（可为 ）。你需要输出整串的前缀函数：。 解题思路  记 。对 ，令 ，不断回退  直到  或 。 若匹配则 ，令 。该算法按字符线性推进，每个位置的指针最多回退若干次，总体 。 多组数据独立处理，保证所有  之和约束内可在线性时间完成。  代码   c++   java   python   #include <bits/stdc++.h> using namespace std; int main() { ios::...

题目链接  货物堆放  题目描述 有  种商品，每种有三元组 ：重量、初始体积、压缩系数。将它们自上而下堆成一条竖直货堆。设商品  上方（不含自身）的总重量为 ，则其实际体积为 。希望通过调整堆放顺序，使所有商品实际体积之和最小。 解题思路  目标函数为  因此等价于最大化 。 若堆放顺序为 （自上而下），则 ，从而  对任意两件商品 ，若令  在  上方，则对这对商品贡献为 ；反之为 。为了使总贡献最大，应当让较大的一个作为“在上方”的次序成立：   结论：按比值  从大到小排序（实现时用交叉乘比较  与  以避免精度），自上而下堆放，即可使总实际体积最小。 扫描计算答案：维护前缀重量 （表...

题目链接  BISHI53 [P1080] 国王游戏(简化版)  题目描述 国王左、右手分别写下两个整数 ；共有  位大臣，第  位大臣左、右手写下 。国王站最前，其余大臣可任意排序。若某位大臣在队列中的相对位置为 ，则他获得的金币数为  其中  为队列中大臣的编号顺序。目标是通过调整大臣顺序，使“获得金币最多的大臣”的金币数尽可能小，并输出该最小值。 （本题为简化版， 不参与计算，仅作为题面设定。） 解题思路  记前缀乘积 。第  位大臣的金币为 。 只需最小化 。对任意相邻两位大臣 ，比较先后次序对“二者的最坏值”的影响，可得应按  的升序排序（交换论证标准结论）。 排序后，从前到后维护前...

题目链接  BISHI50 [JSOI2007]建筑抢修  题目描述 有  座受损建筑。维修工可忽略移动时间，但同一时刻只能维修一座建筑。维修第  座建筑需要时间 ，且必须在截至时间  之前全部完成，否则报废。请安排维修顺序，使最终在各自时限内完成的建筑数量最大，并输出最大数量。 解题思路   贪心 + 优先队列（最大堆）：按截止时间从小到大排序所有建筑对 。维护当前选择集合的总工时  与一个存放所选建筑工时的最大堆。  依次处理每个建筑：将  加入集合（入堆），并令 。 若 ，说明在当前截止时间  前无法完成所有已选建筑，应当删除集合中工时最大的那座（从最大堆弹出），并从  中减去该最大工时...

题目链接  邮递员送信  题目描述 有  个路口与  条单向道路（均为单行道）， 号路口为邮局， 号路口各有一件包裹待投递。邮递员一次只能携带一件包裹，每次需从邮局取件出发，将包裹送达目的地后必须返回邮局，方可取下一件。已知任意两点间互相可达，求完成全部  件投递并最终回到邮局所需的最短总时间。 解题思路  对每个目的地 ，本次往返的最短时间为“邮局到  的最短路”与“ 回邮局的最短路”之和。 记  为从  号点到  的最短路距离；将图反向后，再求从  出发的最短路，得到  为从  到  的最短路距离（在原图中）。 答案为   因边权为非负整数，采用堆优化 Dijkstra，分别在正图与反图各...

题目链接  最优乘车  题目描述 有  条单向巴士线路与  个站点。第  条线路依次经过若干站点，方向与输入次序一致，旅客可在同一站点即时换乘到另一条线路。设站点编号为 ，从  号站到  号站，最少需要换乘多少次？若无法到达，输出 ；若无需换乘，换乘次数为 。 解题思路   建图思想（0-1 BFS）：  建立两类节点：  站点节点：。 线路位置节点：对每条线路  的第  个站位建节点 （表示“在  线上处于第  个站位”）。   加边规则：  登车：（当该站位即为站点 ），费用 （一次上车，对应一次“潜在换乘”）。 沿线前进：，费用 （同一线路内前进不增加换乘）。 下车：（该站位对应站点 ）...

题目链接  【模板】最小生成树  题目描述 给定一张包含  个顶点、 条无向加权边的连通图，边权为整数。请你求出该图的最小生成树（MST）：选出  条边使其连通所有顶点且边权和最小。 需要输出：  第一行：MST 的边权总和； 第二行： 个互不相同的整数，表示所选边的编号（编号从  开始，边编号按输入次序定义）。若 MST 不唯一，可输出任意一种方案。  解题思路   Kruskal + 并查集：将所有边按边权从小到大排序，依次尝试加入生成树；若当前边两端点不在同一连通块，则合并并将其计入答案。   并查集（DSU）：维护每个顶点所在连通块，支持  与 （路径压缩 + 按秩/按大小合并）。  ...

题目链接  【模板】单源最短路Ⅲ ‖ 非负权图  题目描述 给定由  个顶点、 条边构成的有向赋权图（不一定连通），边权为非负整数。给定起点 ，依次输出从  到每个顶点的最短路径长度；若不可达输出 ，到自身输出 。允许重边，无自环。 解题思路  非负权最短路 = 堆优化 Dijkstra：对于非负边权，采用 Dijkstra 算法配合优先队列（小根堆）可在  时间内求出单源最短路。 做法：  建邻接表。距离数组  初始为 ，。 用小根堆按当前最短距离取出顶点 ，若弹出的距离大于已知  则跳过；否则对每条出边  进行松弛：若 ，则更新并入堆。 结束后， 的顶点输出 。   细节：  边权可能为 ...

题目链接  【模板】单源最短路Ⅰ ‖ 无权图  题目描述 给定由  个顶点、 条边构成的有向无权图（不一定连通，允许重边，无自环）。给定起点 ，需要输出从  到每个顶点的最短路径长度；若不可达则输出 。 解题思路  无权图最短路 = BFS：在无权图中，从单源  到各点的最短路长度可用广度优先搜索（BFS）在线性时间求出。 具体做法：  建立邻接表，距离数组  初始化为 ，令 。 用队列按层推进：弹出当前点 ，遍历所有出边 ，若 ，则令  并入队。 结束后按顶点编号从  到  输出 。   正确性：BFS 按“层数”逐层扩展，首次到达某点即为最短路。 复杂度：时间 ，空间 。  代码   c+...

题目链接  【模板】非质模数下的乘法逆元  题目描述 给定若干组正整数对，每组为两个整数 ，要求计算乘法逆元，即找到满足  的最小非负整数 。注意： 不保证为质数。 解题思路   判定存在性：当且仅当  时， 在模  意义下存在逆元。   方法一（推荐，扩展欧几里得）：利用扩展欧几里得算法求解整数  使  若 ，则上式化为 ，两边对  取模可得 ，因此  对  取非负最小剩余即可作为逆元：。   方法二（了解）：若 ，也可用欧拉定理  得  为逆元，但需要分解  求 ，整体不如扩欧稳定简洁。   边界与细节：  若 ，逆元不存在；通常输出 （如评测无特例声明）。 计算中注意将结果规范到 ：。 ...

题目链接  【模板】欧拉函数Ⅰ ‖ 单个整数  题目描述 给定多次询问，每次输入一个正整数 ，输出欧拉函数 ，即区间  内与  互质的整数个数。 解题思路   欧拉函数公式：若  的不同质因子集合为 ，则    做法（试除分解质因子）：  设答案 。从  开始试除，直到 。 一旦发现质因子 ，就把  中的  全部除尽，并令 。 试除结束后，若剩余的 ，说明  本身是一个质因子，同样令 。    边界： 时 。 为质数时 。   复杂度：单次询问试除到 ，时间复杂度 ，空间复杂度 。多次询问可逐个独立处理。   代码   c++   java   python   #include <bi...