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

· · 题解

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

解题思路（题目传送门）

一定需要画的 n+2 条边（左右边界和底部），加上横线总数（仅包括柱子的顶部和柱子的 b_i-1 条 b_i 等分线），再减去可以合并成一条线的线段个数。

计算公式

cnt=n+2+\sum\limits_{i=1}^nb_i-\sum\limits_{i=1}^{n-1}k_i

PS：k_i 表示第 i 根柱子和第 i+1 根柱子的等分线中可以合并成一条线的线段个数。

k_i=\gcd(a_i \times b_{i+1},a_{i+1} \times b_i)/\max(a_i,a_{i+1})

时间复杂度

枚举每个位置的时间复杂度是 O(n)，计算最大公因数的时间复杂度是 O(\log k)，所以程序的总时间复杂度是 O(n \log k)。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,a[N],b[N],cnt;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    cnt+=n+2;//记录画出所有柱子的外边界所需的笔画数。
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],cnt+=b[i];
    for(int i=1;i<n;i++){
        int x=a[i]*b[i+1],y=a[i+1]*b[i];
        cnt-=__gcd(x,y)/max(a[i],a[i+1]);//__gcd(x,y)是万能头自带的求最大公因数的函数。
    }
    cout<<cnt;
    return 0;
}