题解 P6297 【替换】

奇米 · 2020-04-06 10:19:40 · 题解

题解 - \mathrm{P6297 } 替换

\huge\color{blue}\boxed{\color{Violet}\mathfrak{There\ is \ my \ blog}}

题目意思

• P6297
• 求一段回文串[l,r]使得\prod\limits_{i=l}^r\ a_i 最大

\mathrm{Sol}

• 前置知识：对数

• 对数转换的思维可以看：另一道题

• 众所周知\log(a\times b)=\log(a)+\log(b)

• 那么我们不直接地计算\prod\limits_{i=l}^r\ a_i来比较大小（极限情况：1e9^{10^3}显然存不下的），那么我们通过比较\sum\limits_{i=l}^r \log(a_i)来比较大小这样就方便多了。

• 后来就是回文的判断（注意判断奇偶两种情况）

• 时间复杂度：O(3\times n^2)

\mathrm{Code}

#include <bits/stdc++.h>
#define pb push_back
#define int long long 
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=1005;
const int mod=1e9+7;

int n,m,a[N],Log[N],ansx,ansy;
double b[N];

signed main()
{
    n=read();
    m=read();
    for ( int i=1;i<=n;i++ ) 
    {
        a[i]=read();
        b[i]=b[i-1]+log2(a[i]);//取对数做前缀和
    }
    double mx=0;
    for ( int i=1;i<=n;i++ )
    {
        int l=i,r=i,gs=m;
        if(log2(a[l])>mx)
        {
            mx=log2(a[l]);
            ansx=l,ansy=l;
        }
        while(l>=1&&r<=n)//寻找回文
        {
            l--,r++;
            if(a[l]!=a[r]) 
            {
                if(gs>0) gs--;
                else break;
            }
            if(b[r]-b[l-1]>mx)
            {
                mx=b[r]-b[l-1];
                ansx=l,ansy=r;//寻找最大区间
            }
        }
    }//奇数长度回文串情况
    for ( int i=1;i<=n;i++ )
    {
        int l=i-1,r=i,gs=m;
        if(a[l]!=a[i]) gs--;
        if(log2(a[l])+log2(a[i])>mx)
        {
            mx=log2(a[l])+log2(a[i]);
            ansx=l;
            ansy=i;
        }
        while(l>=1&&r<=n)
        {
            l--,r++; 
            if(a[l]!=a[r]) 
            {
                if(gs>0) gs--;
                else break;
            }
            if(b[r]-b[l-1]>mx)
            {
                mx=b[r]-b[l-1];
                ansx=l,ansy=r;
            }
        }
    }
    for ( int i=1;i<=n;i++ )
    {
        int l=i,r=i+1,gs=m;
        if(a[r]!=a[i]) gs--;
        if(log2(a[r])+log2(a[i])>mx)
        {
            mx=log2(a[r])+log2(a[i]);
            ansx=l;
            ansy=i;
        }
        while(l>=1&&r<=n)
        {
            l--,r++;
            if(a[l]!=a[r]) 
            {
                if(gs>0) gs--;
                else break;
            }
            if(b[r]-b[l-1]>mx)
            {
                mx=b[r]-b[l-1];
                ansx=l,ansy=r;
            }
        }
    }//偶数长度回文串情况
    int ans=1;
    for ( int i=ansx;i<=ansy;i++ ) ans=(ans*a[i]%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}