A.hm的难题

预测难度：思维难度：1，代码难度：1

预计通过人数：

题意：

判断字符串中有多少个 。

题解：

签到。读入字符串后，直接数有多少个 。

时间复杂度

B.算法竞赛猫娘太多了喵

预测难度：思维难度：2，代码难度：1

预计通过人数：

题意：

构造一个 的数组符合题意。

题解：

注意到 所以只需要构造 。注意精度要求。

同时又注意到 所以只用 其他都为 也可。

时间复杂度

C.鸟白岛杂货铺

预测难度：思维难度：3，代码难度：1

预测过题人数：

题意：

每次可以选择多堆数量相同的堆一起减一，问最少多少次可以使得所有数字相同。

题解：

贪心，每次都操作最大的一堆数，答案为最大值减去最小值。

时间复杂度

D.棉花娃娃

预测难度：思维难度：3，代码难度：2

预测过题人数：

题意：

构造一个排列 p 使得贡献 最大， 。

题解：

注意到

按 排序即可。

时间复杂度

E.价格监视

预测难度：思维难度：4，代码难度：7

预测过题人数：

题意：

每次有一个修改指令以及一个输出指令。

模拟修改和输出加权中位数。

题解：

用平衡树维护滑动窗口，直接找中位数即可。

动态开点线段树上二分，对顶堆也可以做。

这里给出对顶堆解法：

• 维护两个堆：
  • 大根堆（正序堆） pn：存放价格较小的一半，按价格从小到大排序。
  • 小根堆（逆序堆） px：存放价格较大的一半，按价格从大到小排序。
• 同时维护两个堆的总权值 wpn 和 wpx，并通过平衡操作使 wpn 与 wpx 尽量接近且 wpn >= wpx，此时 pn 的堆顶即为加权中位数。
• 滑动窗口：每向右移动一格，删除窗口最左侧的装备，添加新进入的装备。
• 修改操作：如果在当前窗口内则先删除旧装备，再插入新装备。
• 懒标记：记录待删除的元素，当需要删除的元素在堆顶时删除。

每次插入、删除后调用平衡函数，保证 pn 的堆顶为加权中位数。

时间复杂度

F.想要成为旮旯给木大神

预测难度：思维难度：7，代码难度：7

预测过题人数：

题意：

给定一个有根树，树的叶子节点通往角色结局，定义节点代价为从该节点向下能通往的叶子节点的数量，，现在有多次询问，每次询问给出多位角色编号，要找到一个节点，要求从该节点向下能够到达所有询问的角色编号，且只能到达询问的角色编号，同时要求节点代价最小，如若有多个节点符合要求输出最小的节点编号。

题解：

观察数据范围，可以发现只有60位不同的角色，可以使用状态压缩，把每一个点用一个数字进行表示。

如若能通往编号 的角色则数字的二进制第 位为 ，这样我们在转移的时候就可以通过位运算的按位或操作进行快速转移，同时在转移的时候预处理答案对应编号即可。

因为数字可能过大可以使用map来存，最后对于每次询问都可以 查询答案。

时间复杂度

G.开启全舰防御系统

预测难度：思维难度：5，代码难度：5

预测过题人数：

题意：

每次给出一个区域，打击这个区域的所有未知生命体，判断最后有多少个未知生命体被彻底消灭。

题解：

简而言之就是极角排序后区间加。

实现上，将所有点极角排序后，将每次打击的扇形区间拆分为环形事件（ 于左边界， 于右边界），与点混合排序，线性扫描同时维护当前覆盖数，直接统计能量耗尽点数。

时间复杂度

H.AAA虎哥的三进制

预测难度：思维难度：8，代码难度：8

预测过题人数：

题意：

询问是否存在一个多重集合 ，使得将 中所有元素的平衡三进制表示进行位乘运算后，得到的平衡三进制数对应的十进制值等于 。

题解：

把一个数视为两个二进制：

• 第一个二进制的第 位为 当且仅当该数平衡三进制第 为 。
• 第二个二进制的第 位为 当且仅当该数平衡三进制第 为 。

选出来的数第一个二进制异或和为 的第一个二进制，第二个二进制或起来要为 的第二个二进制。

由于每个数可以选两次，可以贪心先满足第二个条件，然后线性基判断能否满足第一个条件。

时间复杂度

I.偏导树

预测难度：思维难度：4，代码难度：8

预测过题人数：

题意：

对一棵树求偏导，大模拟题。

题解：

1. 建树：将表达式解析成一棵树，每个节点记录名字、类型（函数/变量）以及子节点列表，同时记录每个节点在父节点中的参数下标（从 1 开始）。
2. 预处理：将所有变量名的叶子节点分组，方便快速查找。
3. 回答询问：
   • 对每个询问变量 (x)，找到所有名为 (x) 的叶子节点。
   • 对每个叶子，从该节点向上走到根，沿途收集每个函数节点的“函数名+下标”（如 f1），然后将收集的片段反转得到从根到叶的字符串。
   • 将所有叶子得到的字符串用加号连接，末尾加上 : 和变量名。若无叶子，则输出 0:变量名。

关键点

• 解析时利用栈，通过 ( 区分函数与变量。

• 每个节点存储父节点和子节点顺序，便于回溯时确定下标。

• 由于节点数少，直接对每个询问遍历所有叶子即可。

• 输出顺序任意，SPJ 会自动排序比对。

J.矩阵轮换

预测难度：思维难度：4，代码难度：5

预测过题人数：

题意：

给定一个 的九宫格，初始状态为

每次操作可以选择四个 子块之一，将其中的四个数字顺时针旋转 90 度。
询问到达某个目标状态（为 的排列）的最少操作次数，若无法到达则输出 (-1)。

题解：

• 状态总数只有 (9! = 362880)，完全可以用 BFS 预处理出所有状态到初始状态的最短距离。
• 用 康托展开 将每个排列映射为一个唯一的整数编号，作为 BFS 的节点。
• BFS 从初始状态开始，每一步枚举四种可能的旋转操作，得到新状态，记录步数。
• 对于每个询问，直接输出该状态对应的步数（若未被访问则输出 (-1)）。

时间复杂度

K.树上同或

预测难度：思维难度：9，代码难度：9

预测过题人数：

题意：

给定一棵 个节点的树，每个节点有一个 位二进制权值 （）。
定义一条路径的权值为路径上所有节点权值的**按位同或（XNOR）**结果。
同或运算 满足：。

共有 个询问，每个询问给出一个点集 （大小 ）。
对于每个 ，你需要统计有多少无序对 （，）使得从 到 的简单路径权值等于 ，答案对 取模。

题解：

1. 转化同或
   同或运算可表示为 。
   对于一条路径 ，设 LCA 为 ，可推导出：

   

   其中 仅由根到 的异或和及深度奇偶性决定，可预处理。

2. 虚树 + 异或卷积
   由于所有询问的 之和 ，对每个询问构建虚树。
   在虚树上 DP：每个节点维护其子树中关键点的 值频数（经沃尔什变换）。
   合并两个子树的频数时，在变换域点乘，再逆变换得到异或卷积，此卷积结果即为以当前节点为 LCA 的点对 的分布，再异或上当前节点权值即可得到路径权值。

3. 统计答案
   最终加上所有单点路径的贡献（即每个关键点自身的权值）。

时间复杂度

L.手心手背

预测难度：思维难度：1，代码难度：1

预测过题人数：

题意：

签到模拟。唉看乐队番的，唉。

题解：

签到。读入输入后，进行判断即可。

时间复杂度

M.喜欢贪心怎么你了？

预测难度：思维难度：2，代码难度：2

预测过题人数：

题意：

给你一个字符串，需要按题意模拟把字符串变成新的字符串。

题解：

手把玩一下或暴力预处理一下每个字母会变成什么样即可。

时间复杂度