BZOJ 4488: [Jsoi2015]最大公约数 暴力 + gcd
生活随笔
收集整理的這篇文章主要介紹了
BZOJ 4488: [Jsoi2015]最大公约数 暴力 + gcd
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Description
給定一個長度為 N 的正整數序列Ai對于其任意一個連續的子序列
{Al,Al+1...Ar}，我們定義其權值W(L,R )為其長度與序列中所有元素的最大公約數的乘積，即W(L,R) = (R-L+1) ∗ gcd (Al..Ar)。
JYY 希望找出權值最大的子序列。
Input
輸入一行包含一個正整數 N。
接下來一行，包含 N個正整數，表示序列Ai
1 < = Ai < = 10^12, 1 < = N < = 100,000
Output
輸出文件包含一行一個正整數，表示權值最大的子序列的權值。
考慮暴力：
枚舉右端點，再暴力枚舉左端點，更新答案，時間復雜度為 $O(n^2log(10^{12}))$.
當一段區間的 $gcd$ 的值都相同時，我們只會取左端點最靠左的，這樣顯然最優.
而右端點固定時，區間左端點越靠左， $gcd$ 的值會越小，那么我們就能減少決策點
由于已知能對答案起貢獻的 $gcd$ 都是會不相同的，而每次 $gcd$ 向左都會減小，且至少 $/2$ (或不變)
那么每次只需枚舉那 $O(log(10^{12}))$ 個左端點.
我們得到了一個做法：
依次枚舉右端點，右端點每次增加 $1$，原先右端點所對應的決策點都要保留，并與新的右端點的值取 $gcd$，并加入右端點的值.
每次這么更新一下并刪掉相同的數即可.
枚舉右端點，再暴力枚舉左端點，更新答案，時間復雜度為 $O(n^2log(10^{12}))$.
當一段區間的 $gcd$ 的值都相同時，我們只會取左端點最靠左的，這樣顯然最優.
而右端點固定時，區間左端點越靠左， $gcd$ 的值會越小，那么我們就能減少決策點
由于已知能對答案起貢獻的 $gcd$ 都是會不相同的，而每次 $gcd$ 向左都會減小，且至少 $/2$ (或不變)
那么每次只需枚舉那 $O(log(10^{12}))$ 個左端點.
我們得到了一個做法：
依次枚舉右端點，右端點每次增加 $1$，原先右端點所對應的決策點都要保留，并與新的右端點的值取 $gcd$，并加入右端點的值.
每次這么更新一下并刪掉相同的數即可.
#include <bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 100004
#define ll long long
using namespace std; ll gcd(ll a,ll b) {
return b?gcd(b,a%b):a;
} ll arr[maxn],gc[maxn];
int pos[maxn],b[maxn]; int main() {
// setIO("input");
int n,i,j,top=0,tmp=0;
ll ans=0;
scanf("%d",&n);
for(i=1;i<=n;++i) {
scanf("%lld",&arr[i]);
for(j=1;j<=top;++j) gc[j]=gcd(gc[j],arr[i]);
gc[++top]=arr[i], pos[top]=i;
b[tmp=1]=1;
for(j=2;j<=top;++j) if(gc[j]!=gc[j-1]) b[++tmp]=j;
top=0;
for(j=1;j<=tmp;++j) {
gc[++top]=gc[b[j]],pos[top]=pos[b[j]];
ans=max(ans,1ll*(i-pos[top]+1)*gc[top]);
}
}
printf("%lld\n",ans);
return 0;
}
總結
以上是生活随笔為你收集整理的BZOJ 4488: [Jsoi2015]最大公约数 暴力 + gcd的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： vs code 写VUE代码 注释 ht
- 下一篇： docker学习（七）常见仓库介绍