1 条题解

  • 0
    @ 2026-11-15 22:43:20

    B 禁忌的联盟 (lol) 题解

    Step 1: 忽略 aia_i 颜色限制,只处理 bib_i 不互质

    定义DP状态

    定义一个DP状态:f[p],表示以质因数 pp 为最后一位因子的最长子序列长度。

    转移方式

    观察到,如果两个数 bi,bjb_i, b_j 有公共质因数 pp,那么它们之间可以相连。

    对于每个 bib_i,我们枚举它所有的质因数 pp,找到所有 f[p]f[p] 中的最大值 max_valmax\_val,然后令当前元素作为结尾的子序列长度为 max_val+1max\_val + 1;然后反向更新所有这些质因数的 f[p]←max⁡(f[p],dpi)f[p] \leftarrow \max(f[p], dp_i)。

    这个部分的复杂度是 O(n⋅log⁡bi)O(n \cdot \log b_i),因为对每个 bib_i 做质因数分解。

    Step 2: 引入 aia_i 不同的限制(颜色限制)

    每个质因数 pp 下,维护两个记录:

    • f[p].max1:最大的子序列长度,以及对应的 aia_i
    • f[p].max2:第二大的子序列长度(必须与 max1 的 aia_i 不同)

    转移逻辑

    对于当前元素 (ai,bi)(a_i, b_i),设 bib_i 的所有质因数集合为 PP,我们尝试从这些质因数对应的最长记录中转移:

    $$dp[i] = \max_{p \in P} \begin{cases} f[p].\text{max1}.\text{value} & \text{if } f[p].\text{max1}.\text{color} \neq a_i \\ f[p].\text{max2}.\text{value} & \text{if } f[p].\text{max1}.\text{color} = a_i \end{cases}$$

    然后将 dp[i]dp[i] 更新回所有 p∈Pp \in P 的 f[p] 中对应的位置。

    总复杂度:O(nlog⁡bmax⁡)O(n \log b_{\max}),其中 bmax⁡=105b_{\max} = 10^5

    信息

    ID
    218
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    2
    已通过
    1
    上传者