P8810 [蓝桥杯 2022 国 C] 数组个数

wflengxuenong · 2022-11-07 15:31:25 · 个人记录

这是一个环形问题

方法一 dp

一般的环形问题是断环为链，扩展为2倍长度。这个问题回到尾部后还有看能否和断点连接。所以我们可以直接枚举起点。当然还是扩展一倍长度，直接用%n确定点的位置。我们设a数组为可以填数值的最大值，a_i=min(b_{i-1},b_i,b_{i+1})。

我们设f_{ixy}为i位置的数为y，i-1位置的数为x。每个状态只与其前两个位置相关。枚举起点状态的时间复杂度为o(max(b_i)^2)。确定起始状态后，进行每个结点需要o(N*max(b_i)^3)，枚举3个结点的状态进行转移。

初始状态01位置还不能确定，从2位置开始确定1位置的。对每个结点来说，如果前两个结点已经确定最大值，当前结点可以任意填数。否则当前结点只能填确定的最大值。结束后确定了n-2位置的，把环折回来再看n-1和0状态是否合法。最后仅把合法状态计入答案。

时间复杂度分析

因此总的时间复杂度为o(N*max(b_i)^5).

#include<bits/stdc++.h>
using namespace std;
const int N=2029;
typedef long long ll;
const ll mod=1e9+7;
int n,a[N],b[N],c[N];//有几个连续的。
ll f[N][11][11],ans=0ll;//当前状态可以与前面两个位置的状态相关。 

ll dp(int x,int y){
    //01起点确定，从2开始，再回到01判断。

    memset(f,0,sizeof(f));
    f[1][x][y]=1;
    for(int i=2;i<n;i++){
        for(int j=a[i];j>=0;j--)
            for(int k=a[i-1];k>=0;k--){
                for(int l=a[i-2];l>=0;l--){
                    if(max(l,k)==b[i-1])f[i][k][j]=(f[i][k][j]+f[i-1][l][k])%mod;
                    else if(j==b[i-1])f[i][k][j]=(f[i][k][j]+f[i-1][l][k])%mod;
                        else break;
                }       
            }
    }
    //判断 n-2 n-1，x y  决定的n-1,0 
    //
    ll ans=0;
    for(int i=a[n-1];i>=0;i--)
        for(int j=a[n-2];j>=0;j--){
            if(max(max(i,j),x)==b[n-1]&&max(max(i,x),y)==b[0]){
                ans=(ans+f[n-1][j][i])%mod;
            }
        }
    return ans ;
}

int main(){

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>b[i];
        b[i+n]=b[i];
    }
    for(int i=0;i<n;i++){
        a[i]=min(min(b[(i+n-1)%n],b[i]),b[(i+1+n)%n]),a[i+n]=a[n];
    }
    ans=0;
    for(int i=a[0];i>=0;i--){
        for(int j=a[1];j>=0;j--){
            ll tmp=dp(i,j);
            ans=(ans+tmp)%mod;
        }
    }
    cout<<ans<<endl;
}

方法二

根据b数值的情况，手工做几组样例我们可以发现：

当b_i!=b_{i+1}时候

如果b_i>b_{i+1},那么我们可以唯一确定i-1的值为b_i.

如果b_i<c_{i+1},那么我们可以唯一确定i+2的值为b_i.

我们设a数组为可以填数值的最大值，a_i=min(b_{i-1},b_i,b_{i+1})。设c数组为数组可以确定填上的数值。

现在c内连续空着的数值其a_i是相当的。设其连续长度为len

len<=2$,相邻数填了，方案数为$(a_i+1)^{len}
len>=3$,那每3个数至少一个填$a_i
统计出连续长度后，我们可以设f_{i0/1}代表当前填数是否为t=a_i,然后用动态规划转移。

f[i][1]=(f[i-1][0]+f[i-1][1]);

f[i][0]=(f[i-1][1]t+f[i-2][1]t*t);

特殊情况，所有的b_i都相等

这时，就在一个环形区域内填数，每3个数至少有一个b_i,初始状态与线性稍微不同，进行特殊处理，头尾合起来时候用容斥减去不合法数据。

复杂度分析

这个算法不依赖b_i的大小，过程都是线性的，时间复杂度为O(N)。


#include<bits/stdc++.h>
using namespace std;
const int N=2029;
typedef long long ll;
const ll mod=1e9+7;
int n,a[N],b[N],c[N],rk[N];//有几个连续的。
ll f[N][2],ans=1ll;
ll work(int len,int t){//环的情况：连续长度未len，最大数为t, 
    if(len==1)return 1ll;
    if(len==2)return ((t+1)*(t+1) )-1;
    for(int i=0;i<=len;i++)f[i][0]=f[i][1]=0;
    f[0][0]=t,f[0][1]=1;
    f[1][0]=(t+1)*t;
    f[1][1]=t+1;
    for(int i=2;i<len;i++){
        f[i][1]=(f[i-1][0]+f[i-1][1])%mod;
        f[i][0]=(f[i-1][1]*t+f[i-2][1]*t*t)%mod;
    } 
    return (f[len-1][0]+f[len-1][1])%mod;
} 
ll work2(int len,int t){//线性情况：连续长度未len，最大数为t, 
    if(len==1)return ll(t+1);
    if(len==2)return ((t+1)*(t+1) );
    for(int i=0;i<=len;i++)f[i][0]=f[i][1]=0;
    f[0][0]=t,f[0][1]=1;
    f[1][0]=(t+1)*t;
    f[1][1]=t+1;
    for(int i=2;i<len;i++){
        f[i][1]=(f[i-1][0]+f[i-1][1])%mod;
        f[i][0]=(f[i-1][1]*t+f[i-2][1]*t*t)%mod;
    } 
    return (f[len-1][0]+f[len-1][1])%mod;
}

int main(){

    cin>>n;
    for(int i=0;i<n;i++)cin>>b[i],b[i+n]=b[i]; 
    for(int i=0;i<n;i++){
        a[i]=min(min(b[(i-1+n)%n],b[i]),b[(i+1)%n]);
        a[i+n]=a[i];
    }
    memset(c,-1,sizeof(c));
    int flag=-1;
    for(int i=0;i<n;i++) { //先把可以确定的确定。 
        if(b[(i-1+n)%n]<b[i])c[(i+1)%n]=c[(i+1)%n+n]=b[i],flag=(i+1)%n;
        else if((b[(i-1+n)%n]>b[i]))c[(i-2+n)%n]=c[(i-2+n)%n+n]=b[(i-1+n)%n],flag=(i-2+n)%n;
    }

    //找出连续的数据段。
    if(flag==-1){//所有数据一样，构成环。 
        ans=work(n,a[0]);
        if(n==4)ans=(ans-(ll)pow(a[11],3))%mod;
        else if(n>4)ans= (ans-(ll)pow(a[11],4)-2*(ll)pow(a[11],3))%mod;
        if(ans<0)ans+=mod;
        cout<<ans<<endl;
        return 0;
    }
    int len=0;
    for(int i=flag;i<=n+flag;i++) {
        if(c[i%n]>-1)len=0;
        else {
            len++;
            if(c[(i+1)%n]>-1){
                ll tmp=work2(len,a[i%n]);
                ans=ans*tmp%mod;
            }
        }

    }
    cout<<ans<<endl;

} 

/*
6
8 8 8 5 5 4
366
*/