UVALive - 6582 Magical GCD (脑洞)

题意:

给一个数列,定义Magical GCD为序列gcd*序列length,问数列中子序列最大Magical GCD是多少.

解题思路:

定义i,j,i为长度,j去遍历i之前的数,逐步求GCD更新最大值,这种做法的时间复杂度是 n^2,这样暴力求肯定是超时的.

但是我们可以从这个思路去优化,我们会发现在逐步往前求GCD的时候,可能我们会连续的求出一些相同的GCD,这些相同的GCD,在下一次i+1往前求的时候,我们就不需要去和每个原数都求一遍GCD,我们只需要直接和这个(j到i的)GCD求一下GCD,就能求出j到i+1的GCD.所以对于连续相同的GCD我们只需要用一个变量来存储,并存下最左边的数的坐标,因为题目要求最大Magical GCD.所以i*i的遍历就被改成i*(GCD个数),时间复杂度就下降了许多了.

代码:

#include <cstdio>#include <iostream>#include <cstring>#include <bits/stdc++.h>#define LL long long using namespace std;const int maxn=1e5+5;LL a[maxn];struct p{   LL Gcd;   LL index;}g[maxn], gg[maxn];LL gcd(LL x, LL y){   if(x%y==0)return y;   else return gcd(y, x%y);}bool cmp(p a, p b){     return a.Gcd<b.Gcd;}int main(){   int t;   cin>>t;   int i, j;   int top=0;   while(t--)   {     int n;     scanf("%d", &n);     int i, j;     top=0;     LL ma=0;     for(i=0; i<n; i++)scanf("%lld", &a[i]);     for(i=0; i<n; i++)     {	int exi=0;	for(j=top; j>0; j--)	{	   if(g[j].Gcd==a[i])exi=1;	   g[j].Gcd=gcd(g[j].Gcd, a[i]);	   ma=max((i-g[j].index+1LL)*g[j].Gcd,ma);	  // PRintf(j==0?"%lld %lld/n":"%lld %lld+", g[j].Gcd, g[j].index);	}	if(exi==0)	{	   g[++top].Gcd=a[i];	   g[top].index=i;	   ma=max(ma, a[i]);	}	sort(g+1, g+top+1, cmp);	int k=1;	for(j=1; j<=top; j++)	{	   if(g[k].Gcd!=g[j].Gcd)	   {	     g[++k]=g[j]; //整个结构体赋值, 防止有内容忘记赋值 	   }	}	top=k;/*	for(j=1; j<=top; j++)	{	   printf("%lld+%d ", g[j].Gcd, j);	}	printf("/n");	*/     }     printf("%lld/n", ma);   }}