BZOJ 4488:[Jsoi2015]最大公约数 UPC:2018山东冬令营 权值 (GCD)

本文主要是介绍BZOJ 4488:[Jsoi2015]最大公约数 UPC:2018山东冬令营 权值 (GCD)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

时间限制: 1 Sec   内存限制: 512 MB
提交: 57   解决: 19
[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

输入

输出

样例输入

5

30 60 20 20 20

样例输出

80

提示

来源

【思路】

    有一个定理  ：    长度为n的子序列中  ， GCD 最多为log(n)  

    在 BZOJ 上 这个 时间限度时 10s 在 upc 上 限定1s  ；  

    很尬尬的用 Map 数组，  在bzoj上跑1s  在  upc 上 跑1092ms  差一丢丢  就是过不去；

    改用数组标记 时间 降到128ms  ，  说明UPC 对 STL 库 的支持 不是很好哇；

    固定右端点(枚举右端点)     去掉重复的 gcd ，  延伸最左端点能达到最长；

    map 的话 不断翻滚，  数组  是去重

【代码实现】

STL map的‘

#include <iostream>
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const ll INF=0x3f3f3f3f;
const int MAXN=1e5+5;
const int MOD=1e9+7;using namespace std;inline ll gcd(ll a,ll b) { return b? gcd(b,a%b):a;}ll a[MAXN];map<ll,ll>mp,tmp;
map<ll,ll>::iterator it;
int main()
{int n;ll ans=-INF;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++){ans=max(ans,a[i]);for(it=mp.begin();it!=mp.end();it++){ll now_gcd = gcd(it->first,a[i]);ans= max(ans, now_gcd*(i-it->second+1));if(!tmp[now_gcd])tmp[now_gcd]=(it->second);elsetmp[now_gcd]= min(tmp[now_gcd],it->second); // 取left最远}if(!tmp[a[i]])tmp[a[i]]=i;mp=tmp;tmp.clear();}printf("%lld",ans);return 0;
}

用数组标记的  128ms 

#include <iostream>
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const ll INF=0x3f3f3f3f;
const int MAXN=1e5+5;
const int MOD=1e9+7;using namespace std;inline ll gcd(ll a,ll b) { return b? gcd(b,a%b):a;}ll col[MAXN];
ll gc[MAXN];
ll a[MAXN];
map<ll,ll>mp,tmp;
map<ll,ll>::iterator it;
int main()
{int n;ll ans=-INF;int k=0,cot;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++){col[++k]=i;gc[k]=a[i];for(int j=k-1;j>=1;j--)gc[j]=gcd(gc[j],gc[j+1]);int cot=0;for(int j=1;j<=k;){gc[++cot]=gc[j];col[cot]=col[j];while(gc[cot]==gc[j]) j++;}k=cot;for(int j=1;j<=k;j++){ans=max(ans,gc[j]*(i-col[j]+1));}}printf("%lld",ans);return 0;
}

123

这篇关于BZOJ 4488:[Jsoi2015]最大公约数 UPC:2018山东冬令营 权值 (GCD)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---