P10885 【MX-S3-T1】「FeOI Round 1」野心

Rigel · 2024-08-18 09:08:15 · 题解

思路

在一个排序后为等差数列的数列中，定义 l 为数列长度，d 为可能的数列公差。

试分析以 i 为断点形成的 2 个排序后为等差数列的数列中 d 与 l 的关系。

先定义 l 为“特殊的”，当且仅当 l=\begin{cases} \lfloor\frac{n}{2}\rfloor\ 或\ \lfloor\frac{n}{2}\rfloor+1&n=2x+1,\ x\in\mathbb{N+},\\ \frac{n}{2}&n=2x,\ x\in\mathbb{N+}. \end{cases}

存在如下 3 种情况：

• 当 l \in [1,2] 时，d \in [1,n-1]。

• 当 l \in [3,n] 时，d=\begin{cases} 1\ 或\ 2& l\ 为“特殊的”,\\ 1 & \mathop{\operatorname{otherwise}}.\\ \end{cases}

再定义 \mathop{f_i}\limits_{i \in [1,n]}=[\ [p_1,p_2,\cdots,p_i] 为等差数列]，\mathop{g_i}\limits_{i \in [1,n]}=[\ [p_{i},p_{i+1},\cdots,p_n]为等差数列]。

注意到，\forall i\in [1,n)，f_i=1\ \land \ g_{i+1}=1，则 i 合法，因此求出 f_i 与 g_i 即可。

下面以求出 f_i 为例，此时 l=i。

正难则反，我们设出 d 的值并检验 d 的合法性，若 d 合法，则 f_i=1。

显然，l \le 2 时 f_i=1，不再赘述。

当 l > 2 时，

• 先设 d=1。若 l=\mathop{\operatorname{max}}(p_1,p_2,\cdots,p_i)-\mathop{\operatorname{min}}(p_1,p_2,\cdots,p_i)+1，则 d 合法。

• 若 l 为“特殊的”，再设 d=2，此时遍历数列 [p_1,p_2,\cdots,p_i] 判断 d 的合法性（详情见代码）。

不难发现，求 f_i 的过程中，“遍历数列”的操作至多进行 2 次，不会爆时间。

求 g_i 时，l=n-i+1，过程同理，注意顺序。

代码

#include<bits/stdc++.h>
#define int long long
#define INF 0x7fffffffffffffff
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))
#define maxn 2000010
using namespace std;
int t,n,a[maxn],vis[maxn],f[maxn],g[maxn],ans;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}
signed main(){
    t=read();
    while(t--){
        n=read(),ans=0;
        for(int i=1;i<=n;i++)a[i]=read(),vis[i]=0;
        if(n==1){printf("0\n");continue;}
        //求 f[i] 
        int cnt=0,minn=INF,mx=-INF;
        for(int i=1;i<=n;i++){
            vis[a[i]]=1;
            if(a[i]>=mx)mx=a[i];
            if(a[i]<=minn)minn=a[i];
            if(mx-minn+1==i||i<=2){f[i]=1;continue;}    
            if(((n&1)&&(i==(n>>1)||i==(n>>1)+1))||(!(n&1)&&(i==(n>>1)))){
                int k=((mx-minn)>>1)+1;
                if(k!=i){f[i]=0;continue;}
                int op=0;
                for(int j=minn;j<=mx;j+=2)if(!vis[j]){op=1;break;}
                f[i]=op^1;
            }else f[i]=0;
        }
        //求 g[i] 
        cnt=0,minn=INF,mx=-INF;
        for(int i=1;i<=n;i++)vis[i]=0;      
        for(int i=n;i>=1;i--){
            vis[a[i]]=1;
            if(a[i]>=mx)mx=a[i];
            if(a[i]<=minn)minn=a[i];
            if(mx-minn+1==(n-i+1)||(n-i+1)<=2){g[i]=1;continue;}    
            if(((n&1)&&((n-i+1)==(n>>1)||(n-i+1)==(n>>1)+1))||(!(n&1)&&(n-i+1)==(n>>1))){
                int k=((mx-minn)>>1)+1;
                if(k!=(n-i+1)){g[i]=0;continue;}
                int op=0;
                for(int j=minn;j<=mx;j+=2)if(!vis[j]){op=1;break;}
                g[i]=op^1;
            }else g[i]=0;
        }
        for(int i=1;i<=n-1;i++)if(f[i]&&g[i+1])ans++;
        printf("%lld\n",ans);
    }
    return 0;
}