HZOI2019序列

题目链接：https://www.cnblogs.com/Juve/articles/11186805.html（密码是我的一个oj用户名）

题解：

这题我考试打的暴力，只有5分。

一开始理解错题意了，以为2，4，32这类不符合，于是有了下面的代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 #define MAXN 100005

 #define re register

 #define in inline

 using namespace std;

 in ll read(){

     re ll x=;char ch=getchar();

     while(ch<''||ch>''){ch=getchar();}

     while(ch>=''&&ch<=''){

         x=(x<<)+(x<<)+ch-'';

         ch=getchar();

     }

     return x;

 }

 ll n,a[MAXN],tot=,ans=;

 in ll max(re ll a,re ll b){

     return a>b?a:b;

 }

 in ll min(re ll a,re ll b){

     return a<b?a:b;

 }

 in bool judge(re ll x,re ll y){

     re ll num=,q;

     re ll b[MAXN];

     for(re ll i=x;i<=y;i++){

         b[++num]=a[i];

     }

     sort(b+,b+num+);

     //cout<<b[1]<<' '<<b[2]<<endl;

     //if(b[2]==b[1]) return 0;

     q=b[]/b[];

     for(re ll i=;i<=num;i++){

         if(b[i]%b[i-]!=) return ;

         if(b[i]==b[i-]) return ;

         if(b[i]/b[i-]!=q) return ;

     }

     return ;

 }

 signed main(){

     //freopen("test.in","r",stdin);

     n=read();

     for(re ll i=;i<=n;i++){

         a[i]=read();

         if(a[i]==) ans=;

         if(a[i]==a[i-]) tot++;

         else{

             ans=max(tot,ans);

             tot=;

         }

     }

     if(ans==n){

         printf("%lld\n",ans);

         return ;

     }

     for(re ll i=;i<=n;i++){

         if(!a[i]||!a[i+]){

             continue;

         }

         for(re ll j=i+;j<=n;j++){

             //cout<<j<<endl;

             if(judge(i,j)){

                 //cout<<i<<' '<<j<<endl;

                 tot=j-i+;

                 ans=max(ans,tot);

                 //cout<<tot<<endl;

             }

             else{

                 ans=max(ans,tot);

             }

         }

     }

     ans=max(ans,tot);

     printf("%lld\n",ans);

     return ;

 }

5分

考完试看正解，没看懂，于是开始更改我的暴力思路

设dp[q][i]表示公比为q，以i结尾能组成题目中序列的个数

我们先求出数列的max和min，得到q的范围

首先枚举q，之后枚举整个数列，对与每个a[i]和a[i-1]，如果max(a[i],a[i-1])%min(a[i],a[i-1])，

那么枚举q的指数q^p，如果min(a[i],a[i-1])*q^p=max(a[i],a[i-1])，那么从i向前dp[q][i-1]中判重，若没有重复，那么dp[q][i]=dp[q][i-1]+1;

判重是防止以下情况：4，2，4;

4在前面出现过一次了，所以dp[q][3]=2而不是3;

具体做法：

for(ll p=;p<=;p++){

                    ll Q=power(q,p);

                    if(Q>maxx) break;

                    if(mi*Q==ma){

                        bool flag=;

                        for(ll k=;k<=dp[q][i-];k++){

                            if(a[i]==a[i-k]){

                                dp[q][i]=k;flag=;

                                ans=max(ans,dp[q][i]);

                                //cout<<ans<<' '<<dp[q][i]<<' '<<q<<' '<<i<<endl;

                                break;

                            }

                        }

                        if(!flag){

                            dp[q][i]=dp[q][i-]+;

                            ans=max(ans,dp[q][i]);

                            //cout<<ans<<' '<<dp[q][i]<<' '<<q<<' '<<i<<endl;

                        }

                        break;

                    }

                }

细节的地方包括判断0以及公比是一的情况，随时更新ans

Ps:因为这道题的数据实在是不好造,所以最后公比最大不会很大，博主试验过了，公比最大是10

于是我们快乐地A掉了这道题

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

#define MAXN 100005

#define re register

#define in inline

using namespace std;

in ll read(){

    re ll x=;char ch=getchar();

    while(ch<''||ch>''){ch=getchar();}

    while(ch>=''&&ch<=''){

        x=(x<<)+(x<<)+ch-'';

        ch=getchar();

    }

    return x;

}

ll n,a[MAXN],tot=,ans=,maxx=,minn=9e18;

ll max_q,dp[][MAXN];//dp[q][i]表示公比为q，以一下标i结尾的序列最大能得到多长的等比序列

in ll max(re ll a,re ll b){

    return a>b?a:b;

}

in ll min(re ll a,re ll b){

    return a<b?a:b;

}

ll power(ll a,ll b){

    ll ans=;

    for(;b;b>>=){

        if(b&) ans=(ll)ans*a;

        a=(ll)a*a;

    }

    return ans;

}

signed main(){

    n=read();

    //cout<<n<<endl;

    for(re ll i=;i<=n;i++){

        a[i]=read();

        maxx=max(a[i],maxx);

        minn=min(a[i],minn);

        if(a[i]==){

            ans=max(ans,tot);

            tot=;

            continue;

        }

        if(a[i]==a[i-]){

            tot++;

            ans=max(ans,tot);

        }

        else{

            ans=max(ans,tot);

            tot=;

        }

        //cout<<tot<<endl;

    }

//    cout<<ans<<endl;

    if(minn==) minn=;

    max_q=min(,maxx/minn);

    //cout<<max_q<<endl;

    for(ll q=;q<=max_q;q++){//枚举公比

        dp[q][]=;

        if(a[]==) dp[q][]=;

        else dp[q][]=;

        for(ll i=;i<=n;i++){

            if(a[i]==){

                dp[q][i]=;

                continue;

            }

            ll ma=max(a[i],a[i-]),mi=min(a[i],a[i-]);

            //cout<<i<<endl;

            //cout<<ma<<' '<<mi<<endl;

            if(ma==mi){

                dp[q][i]=;

                continue;

            }

            if(mi==||ma%mi!=){

                dp[q][i]=;

                //cout<<ans<<' '<<dp[q][i]<<' '<<q<<' '<<i<<endl;

            }else{

                for(ll p=;p<=;p++){

                    ll Q=power(q,p);

                    if(Q>maxx) break;

                    if(mi*Q==ma){

                        bool flag=;

                        for(ll k=;k<=dp[q][i-];k++){

                            if(a[i]==a[i-k]){

                                dp[q][i]=k;flag=;

                                ans=max(ans,dp[q][i]);

                                //cout<<ans<<' '<<dp[q][i]<<' '<<q<<' '<<i<<endl;

                                break;

                            }

                        }

                        if(!flag){

                            dp[q][i]=dp[q][i-]+;

                            ans=max(ans,dp[q][i]);

                            //cout<<ans<<' '<<dp[q][i]<<' '<<q<<' '<<i<<endl;

                        }

                        break;

                    }

                }

            }

        }

    }

    //for(ll i=1;i<=max_q;i++)

    //    for(ll j=1;j<=n;j++)

    //        cout<<dp[i][j]<<' '<<i<<' '<<j<<endl;

    printf("%lld\n",ans);

    return ;

}

但其实这还不是正解

正解非常神仙：

因为选出的一段是一个等比序列的子序列,我们分为两种情况:
1. q=1,相当于找一个最长每个数都相等的子串,这个扫一遍就行了。
2. q!=1,那么这个序列最长只有$log_{2}n$,那么我们可以枚举开头,不妨设开始的两个数为 a[i]和 a[i+1],
其中比较大的一个为 x,另一个 y。
(1) 首先要满足 x%y=0
(2) 让 z=$\frac{x}{y}$,然后把 z 质因数分解,z=$p_{1}^{q_2}$×$p_{1}^{q_2}$×$p_{1}^{q_2}$......,设 g=gcd(q₁,q₂,q₃...),那么当前序
列的最小公比就是 $p_{1}^{\frac{q_{1}}{g}}$×$p_{2}^{\frac{q_{2}}{h}}$×......
(3) 我们找到最小公比后,每当往后加一个数,判断它与前边的数的比是否是最小公比的整次幂,
不是的话就说明不能再加了。
(4) 还有一个要求就是这个序列里不能有重复的数,这个东西用 set 判断就行了。
复杂度 O($nlog_{2}^{2}n$);

正解代码：

 #include<bits/stdc++.h>

 using namespace std;

 const long long L=<<|;

 char buffer[L],*S,*TT;

 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,L,stdin),S==TT))?EOF:*S++)

 long long n;

 long long data[],ans=,z[],q[],tot=;

 long long p[],c[];

 set<long long> s;

 inline long long read()

 {

     register long long a=,b=;char ch=getchar();

     while(ch<''||ch>'')b=(ch=='-')?-:,ch=getchar();

     while(ch>=''&&ch<='')a=(a<<)+(a<<)+(ch^),ch=getchar();

     return a*b;

 }

 inline long long qpow(register long long x,register long long y)

 {

     register long long ans=;

     while(y)

     {

         if(y&)ans*=x;

         x*=x;

         y>>=;

     }

     return ans;

 }

 inline long long gcd(register long long x,register long long y)

 {

     register long long i,j;

     if(x==)return y;

     if(y==)return x;

     for(i=;==(x&);++i)x>>=;

     for(j=;==(y&);++j)y>>=;

     if(j<i)i=j;

     while()

     {

         if(x<y)x^=y,y^=x,x^=y;

         if(==(x-=y))return y<<i;

         while(==(x&))x>>=;

     }

 }

 inline void divide(register long long x)

 {

     tot=;

     for(register long long i=;i<=min((long long),(long long)sqrt(x));i++)

         if(!(x%i))

         {

             p[++tot]=i;c[tot]=;

             while(!(x%i))x/=i,c[tot]++;

         }

     if(x>)p[++tot]=x,c[tot]=;

 }

 inline bool jud(register long long x,register long long y,register long long q)

 {

     if(x%y)return ;

     x/=y;

     while(x%q==)x/=q;

     if(x!=)return ;

     return ;

 }

 signed main()

 {

     n=read();

     register long long sum=;

     for(register long long i=;i<=n;++i)q[i]=;

     for(register long long i=;i<=n;++i)

     {

         data[i]=read();

         if(data[i]==data[i-])++sum;

         else sum=;

         ans=max(ans,sum);

         if(i>=)

         {

             register long long x=max(data[i],data[i-]);

             register long long y=min(data[i],data[i-]);

             if(x%y)continue;

             register long long d=x/y;

             divide(d);

             register long long g=c[];

                for(register long long m=;m<=tot;++m)

                {

                    if(g==)break;

                    g=gcd(g,c[m]);

                }

             for(register long long l=;l<=tot;++l)

             {

                    q[i-]*=qpow(p[l],c[l]/g);

                    if(q[i-]>)

                    {

                        q[i-]=;

                        break;

                 }

                }

         }

     }

        for(register long long i=;i<=n;i++)

         if(q[i-])

         {

             if(q[i-]==)continue;

             s.clear();

             s.insert(data[i-]),s.insert(data[i]);

             for(register long long j=i+;j<=n;j++)

             {

                 if(s.count(data[j]))break;

                 register long long x=max(*--s.end(),data[j]);

                 register long long y=min(*--s.end(),data[j]);

                 if(jud(x,y,q[i-]))s.insert(data[j]);

                 else break;

             }

             register long long mm=s.size();

                 ans=max(ans,mm);

         }

     printf("%lld",ans);

 }

非常感谢soul提供的代码，soul有素质有情怀有状态有节操%拜

巴特西

HZOI2019序列

最新文章

热门文章