题解：P14781 [COCI 2025/2026 #3] 尺子 / Ravnalo

· · 题解

题解：P14781

思路

画水平线段和垂直线段。由于柱子紧挨着，垂直线段共有 n+1 条（从左到右的边界），且每条垂直线段都是连续的，所以垂直线段数固定为 n+1。

水平线段包括：每根柱子的底部、顶部以及内部的 b_i-1 条等分线。这些水平线段可能位于相同的高度，且相邻柱子在相同高度上的水平线段可以合并成一条更长的水平线段。因此，问题转化为求最少需要画多少条水平线段。

最少水平线段数个数

设每根柱子的水平线条数为 b_i+1（包括底部和顶部），则初始线段总数为 \sum_{i=1}^n (b_i+1) = n + \sum b_i。当相邻两根柱子在某个高度都有水平线段时，这两条线段可以合并为一条，从而减少一条线段。对于高度 h，若相邻柱子 i 和 i+1 在 h 处都有水平线段，则称它们在该高度“匹配”。

定义相邻对 (i, i+1) 的匹配高度数为 C_i，即两个柱子在多少个相同的高度处都有水平线段。则所有相邻对的匹配高度数之和 R = \sum_{i=1}^{n-1} C_i 就是总共可以合并的次数。因此，最少的水平线段数为：

\text{水平线段数} = n + \sum b_i - R

计算 C_i

对于相邻柱子 i 和 i+1，它们的高度分别为 a_i 和 a_{i+1}，等分数为 b_i 和 b_{i+1}。柱子 i 的水平线高度为 k \cdot a_i / b_i（k=0,1,\dots,b_i），柱子 i+1 的水平线高度为 l \cdot a_{i+1} / b_{i+1}（l=0,1,\dots,b_{i+1}）。两者相等的条件为：

k \cdot a_i / b_i = l \cdot a_{i+1} / b_{i+1} \quad \Rightarrow \quad k \cdot a_i \cdot b_{i+1} = l \cdot a_{i+1} \cdot b_i

记 A = a_i \cdot b_{i+1}，B = a_{i+1} \cdot b_i，g = \gcd(A, B)。则上式等价于：

k \cdot \frac{A}{g} = l \cdot \frac{B}{g}

因为 \frac{A}{g} 与 \frac{B}{g} 互质，所以 k 必须是 \frac{B}{g} 的倍数，l 必须是 \frac{A}{g} 的倍数。令 k = t \cdot \frac{B}{g}，l = t \cdot \frac{A}{g}，其中 t 为非负整数。同时 k 和 l 必须满足：

0 \le k \le b_i \quad \text{和} \quad 0 \le l \le b_{i+1}

即：

0 \le t \cdot \frac{B}{g} \le b_i \quad \text{和} \quad 0 \le t \cdot \frac{A}{g} \le b_{i+1}

因此 t 的最大值为：

t_{\max} = \min\left( \left\lfloor \frac{b_i}{B/g} \right\rfloor, \left\lfloor \frac{b_{i+1}}{A/g} \right\rfloor \right)

从而匹配高度数 C_i = t_{\max} + 1（包括 t=0 对应的底部高度 0）。

总线段数

最少线段总数为水平线段数与垂直线段数之和：

\text{总线段数} = (n + \sum b_i - R) + (n+1) = 2n + 1 + \sum b_i - R

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[100009],b[100009],tot,tot1;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    for(int i=0;i<n;i++)tot+=b[i];
    for(int i=0;i<n-1;i++){
        ll g=__gcd(a[i]*b[i+1],a[i+1]*b[i]);
        tot1+=min(g/a[i],g/a[i+1]);
    }
    cout<<tot-tot1+n+2;
    return 0;
}

时间复杂度 O(n\log M)，完全可以过。