A. 欢迎参加 2025 HZCU 校赛

直接输出 "Welcome to 2025 HZCU Contest" 即可。

B. 寻找传说中的"丰饶地带"

• 单调性：判断“是否存在平均值 的区间”具有单调性。通过二分查找逼近最大平均值。

• 数学变形：将 转化为 。

• 前缀和：令 为数组 的前缀和。判定条件变为寻找 使得 且 。

• 贪心维护：遍历右端点 ，维护左端点集合 的最小值 。若 则 合法。

• 时间复杂度：，通常迭代 100-200 次。

C. 邦邦邦邦

对于每一位 ，构造向量 ，其中 表示第 个输入数字的第 位的值。

在位集合上定义偏序 ：

这意味着在所有原始数据中，第 位为 1 蕴含第 位为 1。

对每个数按位判断是否可以合法生成

D. 三角洲行动

1. 问题转化

• 设 为最终摸取的大红编号集合。每次魔法可以从当前排名前 的元素中选取任意子集，总共操作 次。
• 令 表示在 次操作中，从“当前排名第 位”这个位置摸取物品的总次数。
• 由于每次操作只能从每个位置摸取最多一个物品，且总操作次数为 ，显然有：

2. 双射关系

• 每一个不同的集合 唯一对应一个序列 。给定序列 ，我们可以通过模拟唯一确定 。
• 给定集合 ，我们可以通过贪心策略（每次尽可能从靠前的通道取）唯一确定对应的 。计算总数：由于每个 的取值范围是 ，共有 种可能。
• 根据乘法原理，总的不同集合数量为：
• 最终结果：我们需要输出 。使用快速幂算法即可在 的时间内完成计算。

E. 何意味，贵校是异或王国吗？

遍历字符串，把所有"hyw" 的起始下标异或和输出即可

复杂度

F. 字节拼图

使用 map 维护已经收到的区间，每次收到一个新的区间 先缩小区间，然后使用 upper_bound 找到上一个区间即 左边界小于等于 然后开始遍历 map 合并区间 即可

复杂度分析一个区间只会进入 map 一次 和被 erase 一次

复杂度

G. 搞半天还要自己拼

1. 分形性质

• 自相似性：对于任意一级的方阵，其必然可以分为 个方阵，这些方阵与基础方阵 的每一个点一一对应（即这些方阵是由这些点生成的）。
• 判定逻辑：因此只要坐标在任意一级分解中落入 所对应的区域，该坐标必然也是 。反之，只有当该坐标在每一级分解中都落入 所对应的区域，且最终在最后一级的 矩阵中对应位置也是 （或者说从未遇到过 ），它才可能为 。

2. 坐标归约

• 从最高级 开始，计算当前块大小 。
• 确定当前下标 在 中的值：
  • 若为 '1'，直接返回 1。
  • 若为 '0'，令 ，递归进入下一级。
• 若递归至 仍未遇 1，返回 0。

3. 实现细节

• 坐标 最高可达 ，必须使用 long long

• 提前计算并存储 ，注意判断乘法溢出。当 超过坐标上限时

  

H. 故障机器人

1. 算法：全排列 TSP

• 点集抽象：关键点为起点 和所有 （总数 ）。
• 预处理：对每个关键点跑一次 BFS，求出两两间最短路 。复杂度 。
• 搜索：枚举关键点的全排列 ，计算回路总长 取最小值。

2. 复杂度和实现细节

• 。对于 ，，完全可行。
• 若 BFS 无法到达某个 ，或无法返回 ，则输出 。
• 若 ，直接返回 。

I. 永恒之诗

简单题面回顾

给一个 0-based 字符串S（字符串下标从0开始），q次操作，操作分三种：

1. I i c ：在位置 i 前插入 字符c（特别的，当i = 0时，在字符串S最前插入字符c；当i=|S|时，在字符串S最后插入字符c）
2. D i：删除位置 i 的字符
3. Q：查询当前字符串中，有多少个本质不同的子串，满足这个子串在S的所有历史版本中都出现过

算法

字符串-SAM自动机

解析

（前置知识：SAM、SAM自动机）

从查询操作入手，因为一开始的串S已经给定了，所以答案不会超过，只需要判断原始S中的这些本质不同子串是否在之后的串中均出现。假如没有修改操作，那么直接是建SAM自动机，根据它的fail可以建出一棵parent树，答案就是这棵树，每个点的maxlen-父亲的maxlen之和。

现在我们有这棵原始串S的parent树（后续一直需要使用）。我们给每个节点记一个tag，初值为maxlen。表示在之后的操作中，maxlen被缩小到了多少，因为所有历史串中均出现的一定是一个前缀长度。

对于每次修改操作（插入/删除）会获得一个新串S'，其长度一定小于(n+q)，我们拿原串 S 加一个特殊字符加当前串 S'，即 S + # + S' 这整一串放进SAM，建出新的parent树。我们观察endpos，在遍历这个parent树的时候，因为我们塞入过原始串S，所以可以保证跟一开始的parent树对应上，当发现某个节点的endpos集合只有在S中的下标但没S'中的下标时，说明到头了，S'中没这一些串，然后去更新原来parent树对应节点的tag。

查询操作就是遍历原始的parent树，根据当前节点的tag-父亲的maxlen就行。

时间复杂度

因为SAM节点数是线性的，所以是时间复杂度为 O(q(q+n))

J. 小Z擦黑板

简单题面回顾

给定一个长度为 N 的整数序列 A ，问有多少种划分方案可以将 A 划分成连续的子区间，且每个子区间在值域上连续。

核心性质

定义为区间 内的值域连通块数量。 首先需要转化 的计算方式。 将区间内的数值看作图中的节点。对于区间内存在的任意数值 ，如果 也存在，则在 和 之间连一条无向边。 根据欧拉公式（对于森林）：连通块数 = 点数 - 边数 。 即：

题目要求 。由于非空区间至少有 1 个连通块，我们实际上是在寻找 的最小值为 1 的情况。

动态规划与线段树优化

设 为前缀 的合法划分方案数。 转移方程： 其中 。

直接计算复杂度为 ，不可接受。我们需要使用线段树来加速转移。 线段树的下标 维护的是：当当前右端点为 时，以 为左端点的区间 的值及其对应的值。 这样问题就转化为了线段树上的最值问题。

算法流程：

1. 初始化线段树，位置 的初始值为 （便于后续加 变成 ），其余位置为无穷大。设置 并插入线段树位置 。
2. 遍历 从 到 ：
   • 设当前数字为 。
   • 更新点数（不同数值个数）： 的加入使得从上一次 出现的位置之后开始的所有区间，不同数值个数 。
     • 范围：，操作：区间加 。
   • 更新边数（相邻数值对）： 检查 和 。
     • 以 为例，如果 曾在之前出现过，那么对于那些“包含了 但尚未包含 ”的区间，新的一对 形成了，边数 （即 值 ）。
     • 这些区间是左端点在 之后，但在 之前的区间。
     • 范围：，操作：区间减 。
     • 注意：前提是 。
   • 统计答案： 查询线段树全范围 的最小值。
     • 如果最小值为 ，则 。
     • 否则 。
   • 维护状态：
     • 更新 。
     • 将 插入线段树位置 ，初始权值设为 （因为下一轮循环 时，它作为左端点会被“点数更新”加 ，从而正确变为 ）。

复杂度

时间复杂度：。 空间复杂度：。

K. 不平衡的毛毛虫树

1. 简明题意

你需要构造一棵包含 个节点的毛毛虫树。

• 结构：树由一条长度为 的脊柱（）和若干挂载在脊柱上的叶子节点组成。
• 代价：若在脊柱的第 个节点挂载一个叶子，代价为 。脊柱本身不消耗代价。
• 目标：使得脊柱两端点的距离势能之差 ，且总构造代价最小。
  • 其中 。
• 规模：，时限 3 秒。

2. 解法分析

这道题的核心在于将抽象的树上距离势能差 转化为具体的数量约束。

对于树上任意相邻两点 ，若我们将边 断开，设 所在的连通块大小为 ，则有经典结论：

对于毛毛虫的脊柱 ，总差值等于沿途所有边的差值之和：

经过数学推导（求和变换），可以得到核心约束公式：

为了满足条件，我们需要找到一组非负整数 满足：

1. 节点总数约束：（剩余可用节点数）。
2. 权值和约束：。
   • 其中 。
3. 目标：最小化 。

我们枚举脊柱的长度 （从 到 ）。 对于固定的 ，问题转化为一个二维费用的完全背包问题：

• 背包容量：需要恰好填满 个节点。
• 背包载重：权值和恰好为 。
• 物品：脊柱上的位置 。
  • 物品 的体积为 （消耗1个节点）。
  • 物品 的重量为 （贡献权值）。
  • 物品 的价值为 （代价）。
  • 每个物品可选无限次。

注意：第 个位置的权系数为 0，它只消耗节点数，不贡献 。因此它相当于一个“垃圾桶”，用于填充剩余的节点数。

状态定义： 表示使用了 个额外节点，凑出权值和 的最小代价。

转移方程： 为了优化常数，我们直接在外层遍历物品 ，内层遍历 和 （完全背包顺序）。

最后，检查 ，若 ，则剩余的 个节点全部挂在位置 上（代价为 ），更新答案。

3. 复杂度分析

• 外层循环：枚举 ()。
• 内层 DP 状态：
  • 节点数 最多为 。
  • 权值和 最大约为 。
  • 状态总数 。
• 状态转移：对于每个固定的 ，我们有 个物品，每个物品遍历一次整个 DP 表。
• 总复杂度：

为什么能过？

1. 常数极小：运算核心仅为简单的加法和取最小值，且积分计算表明系数约为 。当 时，计算量约为 ，在 3 秒时限内非常充裕。
2. 有效剪枝：
   • 若计算出的 或不是整数，直接跳过。
   • 很多 DP 状态是不可达的（INF），实际访问状态数远小于理论上限。

L. 魔法扑克牌

1. 简要题意

给定一个包含 张牌的堆栈（自底向上编号 ），每张牌有类别 ()。给定一个取牌类别的顺序 （计划）。 你需要计算满足以下条件的操作序列数量：

1. 最小代价：操作包括“分割”（切牌）和“取牌”。切割操作消耗 1 魔力。必须以最少的总魔力消耗取走所有牌。
2. 顺序限制：必须按照计划 的顺序，取完一类再取下一类。
3. 取牌规则：只能取走处于堆顶的牌，且该类牌所有牌都必须处于堆顶（裸露）或已被取走。

2. 问题分析

我们需要分析在什么情况下必须进行分割： 考虑相邻的两张牌：下方的 和上方的 。 设 为牌 的类别在计划中的优先级（越小越早取）。

• 情况 A：：必须在 和 之间切一刀。这不仅是必须的，而且为了代价最小，我们只在必须的时候切。
• 情况 B：：不需要在它们之间分割。

结论：最小分割次数 。每一个满足条件的 对应一个唯一的分割操作（即分割位置 和 之间）。

我们将操作分为 个阶段，第 阶段对应取走类别为 的所有牌。 在构建操作序列时，我们维护一个“当前已确定的操作序列”，长度为 。初始 。

按阶段 依次考虑：

1. 插入分割操作：

   • 找出所有属于该阶段的必要分割。
   • 定义：如果 且 ，那么在 和 之间的分割必须在第 阶段取牌开始之前完成（否则 无法裸露）。
   • 设本阶段必须新增的分割数量为 。
   • 这些分割操作可以插入到此前已经排好的任意位置（只要在取当前阶段牌之前即可），也可以插在当前序列的末尾。
   • 这等价于将 个不同的元素插入到长度为 的序列中。
   • 方案数：。
   • 更新序列长度：。

2. 追加取牌操作：

   • 设类别 共有 张牌。
   • 根据题目要求，这些取牌操作必须排在所有前序阶段之后，且在后序阶段之前。因此只能追加在当前序列末尾。
   • 这 张牌内部的取牌顺序可以是任意的（因为一旦该类牌全部裸露，取谁都行，题目视编号不同为不同操作）。
   • 方案数：。
   • 更新序列长度：。

总方案数 = 其中 是处理完第 阶段后的总操作数。

3. 复杂度分析

• 时间复杂度：。我们需要遍历一次牌堆统计 和 ，然后遍历 个阶段计算组合数。
• 空间复杂度：，用于存储映射关系和阶乘预处理。

M. 最大圆锥

1. 简明题意

给定三维空间 个点 及限制 。求一个圆锥的最大体积，要求至少有两个点 位于底面圆周上，且它们到锥顶的距离分别不超过 。

2. 题目解析

枚举每对点 ，设它们之间的距离为 。 这对点确定的圆锥需满足两个关键参数：

1. 母线长 ：受 限制，最大取 。若 则无法构成圆锥，跳过。
2. 底面半径 ：两点在圆周上，故直径 ，即 。

圆锥体积关于高 的函数为 。 通过求导可知该函数在 处取得理论最大值。 同时，由 推导出高度的几何限制：。

决策逻辑：

• 若 ：取 ，此时体积为 。
• 若 ：受弦长限制，取最大可行高度 （即 ），代入公式计算体积。

遍历所有点对，取最大值即为答案。

3. 时间复杂度

枚举点对需 ，内部计算为 。 总时间复杂度：。