1 条题解

  • 1
    @ 2021-8-7 18:17:56

    出题人:一只书虫仔 Data&验题人:w33z

    Description

    给定两个长为 nn 的序列 ai,bia_i,b_i,定义一个区间 [l,r][l,r] 是相克的当且仅当:

    $$\gcd(a_l,a_{l+1},\cdots,a_r)=\text{lcm}(b_l,b_{l+1},\cdots,b_r) $$

    求:

    • 最长的相克区间长度。
    • 相克区间的数量。

    1n1051 \le n \le 10^51ai,bi10001 \le a_i,b_i \le 1000

    Solution

    Subtask 1:我会暴力!暴力解决问题。

    Subtask 2:我会 ST 表!暴力枚举所有区间,预处理区间 gcd lcm\gcd\ \text{lcm}

    正解:正解是根据 3030 分的进一步暴力解法优化而来的。让我们先固定区间的左端点 ll,然后往右去寻找右端点。我们都知道,区间越大,gcd\gcd 只会不变或者越来越小,lcm\text{lcm} 只会不变或者越来越大,因此如果右端点越靠近 ll,那么 gcd\gcd 就会越大 lcm\text{lcm} 就会越小,反之亦然,也就是说,我们可以通过上面这个过程去二分在 [l,n][l,n] 中最大满足要求的区间 [l,r][l',r'] 的左端点和右端点,然后每一个子区间肯定都满足要求,因此第二问答案加上 rl+1r'-l'+1 即可,第一问答案与 rl+1r'-l'+1 取个 max\max

    然后预处理区间 gcd lcm\gcd\ \text{lcm} 依然是 ST 表。

    MM 为值域,预处理 O(nlognlogM)\mathcal O(n \log n\log M),枚举左端点 + 二分 O(nlognlogM)\mathcal O(n \log n\log M)

    评价:思维代码均比较简单的简单题,给良心的出题人点赞!

    • 1

    信息

    ID
    177
    时间
    2000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    6
    已通过
    2
    上传者