A. 一只羊的新年愿景

• 题目类型： 签到题 / 坑点检查
• 一句话题意： 定义完全加法函数 $f(mn)=f(m)+f(n)$ 且 $f(p)=p$。求区间 $[1,n]$ 内第 $k$ 小的满足 $f(x)=x$ 的整数。
• 解题思路：
  • 数学推导可得解集为：$\{\text{所有素数}\} \cup \{4\}$。
  • 预处理素数筛，注意特判 $4$ 的位置（在 $2,3,4,5,\dots$ 中排第 $3$）。

B. 黑大帅的灯会

• 题目类型： 数据结构模型转化 / 计数
• 一句话题意： 给定传递规则 $i \rightarrow i + \operatorname{lowbit}(i)$ 及部分汇聚值，求满足总和限制的初始序列方案数。
• 解题思路：
  • 识别出树形结构（Fenwick Tree 的反向）。
  • 利用差分关系：$S_u - \sum S_{v_{\text{obs}}} = a_u + \sum a_{\text{unseen}}$。
  • 转化为插板法问题：$\binom{n+m-1}{m-1}$。

C. 皮老师的烟火

• 题目类型： 图论 / 经典贪心优化
• 一句话题意： 通过区间“后缀加减”操作达成目标数组，优化最大操作值与操作和。
• 解题思路：
  • 差分转移 $D_L \rightarrow D_{R+1}$，转化为基环树流量平衡。
  • 树部分拓扑消除，环部分优化：
    • $\min \max |x + c_i|$（极差中心）
    • $\min \sum |x + c_i|$（中位数）

D. 云小安的系统

• 题目类型： 交互题 / 树分治
• 一句话题意： 在树上定位未知两点 $s,t$，询问返回无序的“下一步方向”。
• 解题思路：
  • 点分治（重心分解）定位。
  • 核心难点：利用已知端点的理论方向，反推另一端点的真实方向，消除无序性。

E. 拾柒的元旦封条

• 题目类型： 复杂数据结构 / 势能分析
• 一句话题意： 自定义 $B$ 进制合并规则，区间覆盖后查询历史版本区间和。
• 解题思路：
  • ODT 维护区间颜色（势能分析保证复杂度）。
  • 整体二分处理询问，配合 BIT（需 __int128）维护前缀和。

F. 噜噜的跨年信号

• 题目类型： 数位 DP / 状态压缩 / 构造计数
• 一句话题意： 构造长度为 $N$ 的序列 $A$，元素取自 $\{-1, 0, 1\}$，满足非零元素符号交替，且总能量 $\sum a_i 2^i \in [L, R]$。
• 解题思路：
  • 状态设计： 类似于 Signed-Digit 系统的数位 DP。
  • 关键在于维护“当前前缀值”与“目标边界前缀”的差值状态。由于级数收敛，差值范围极小（$\approx \pm 2$），可状态压缩。
  • dp(bit, last_sign, diff_L, diff_R)，处理上下界及非零交替约束。

G. 九老师的新年相位

给定一个 $N \times M$ 的圆柱面网格图（行方向 $1 \sim N$ 循环首尾相接），边分为横向边与纵向边，每条边具有权值 $W$ 与相位 $P \in \{0,1\}$。

定义 $S$ 为第 $1$ 列点集，$T$ 为第 $M$ 列点集。

求一个将 $S$ 与 $T$ 分隔开的割集 $(V_S, V_T)$，使得割集中满足 $P_e=1$ 的边数恰好为奇数，并最小化割集边权之和。

数据范围：$3 \le N, M \le 120$，$1 \le W \le 10^9$。

分析

本题为典型的平面图（圆柱面）最小割问题，可转化为对偶图上的最短路问题。

原图的 $S-T$ 割对应对偶图上绕圆柱一周的环。我们将圆柱面沿行 $N$ 与行 $1$ 之间剪开，展开为 $N$ 层的平面图，并在垂直方向上复制一层以处理循环边界，形成层 $0$ 到层 $N$ 的分层图。

定义对偶图节点状态 $(r, c, p)$：

• $r \in [0, N]$：表示当前所在的行层级，$0$ 为起始剪切线，$N$ 为绕行一周后的终点剪切线。
• $c \in [0, M-2]$：表示所在的列间隙（即原图第 $c+1$ 列与第 $c+2$ 列之间）。
• $p \in \{0, 1\}$：表示当前路径累积的相位奇偶性。

边权转化：

• 原图横向边 $(i, j) \leftrightarrow (i, j+1)$ 对应对偶图在层间的垂直移动 $r \leftrightarrow r \pm 1$。
• 原图纵向边 $(i, j) \leftrightarrow (i+1, j)$ 对应对偶图在同一层内的水平移动 $c \leftrightarrow c \pm 1$。

算法流程：

由于割集环必须闭合，即起点 $(0, k)$ 和终点 $(N, k)$ 必须对应物理上的同一位置，我们需要枚举起始列间隙 $k \in [0, M-2]$。

对于每个 $k$，运行 Dijkstra 计算从 $(0, k, 0)$ 到 $(N, k, 1)$ 的最短路。

最终答案为所有 $k$ 对应的最短路长度的最小值。