专栏文章

题解：CF1647F Madoka and Laziness

hhoko
CF1647F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miojbb7r
此快照首次捕获于
2025/12/02 20:08
3 个月前
此快照最后确认于
2025/12/02 20:08
3 个月前
查看原文

题目传送门

题意

给定一个长度为 nn 的序列 aa，要求把这个序列分成两个子序列使得这两个子序列都为单峰序列，问有多少种划分方案，两种划分方案不同时，当且仅当存在一个序列的峰值不同。

思路

注意到，序列中每个数都不相同。所以，一定有一个子序列一直包含着序列中的最大值。所以方案数一定不会超过 nn。我们钦定包含序列最大值的子序列为 AA，另一个子序列为 BB。由于序列最大值 xx 会被包含在第一个序列中，我们假定第二个序列的峰值 yy 在 xx 的右边。那在左边的情况怎么办呢，把整个序列翻转，再操作一遍即可。
那么根据 xx 和 yy 的相对位置，我们可以把所有情况分为三种，如下图所示：
在 1∼x1\sim x 的区间内，序列 AA 和序列 BB 都上升，但是观察可知，因为序列 AA 的峰值离 11 更近且峰值最大，所以在这段区间内我们要求让序列 AA 上升的值尽可能的大，而序列 BB 上升的值尽可能的小，这是为了满足 yy 为峰值。
代码如下：
CPP
m1=m2=0;
for(int i=1;i<=pos;i++){
    if(a[i]>m1)m1=a[i];
    else if(a[i]>m2)m2=a[i];
    else return;
}
如果这个数可以给序列 AA 那么就优先给序列 AA,否则给序列 BB。因为序列 AA 的峰值最大，不用担心加入序列 AA 的数会超过峰值。如果这个数都不能加入两个子序列那么说明这种情况不合法，直接返回。
同理，在 y∼ny\sim n 的区间内，序列 AA 和序列 BB 都下降。但是为了让当前 aia_i 可能成为序列 BB 的峰值，所以我们从后往前循环，用类似情况一的贪心策略，不过是让序列二尽可能大，这样 aia_i 才有可能成为序列二的峰值为整个序列做贡献。
代码如下：
CPP
for(int i=n;i>pos;i--){
    if(a[i]>m2)m2=a[i];
    else if(a[i]>m1)m1=a[i];
    else break;
    dp1[i]=m1,dp2[i]=m2;
}
最后一种情况就是 x∼yx \sim y 的区间，这时 AA 序列下降 BB 序列上升，所以我们先考虑那种情况必须给 BB 或给 BB 更优，那么我们就把 aia_i 给 BB，否则给 AA。同时判断答案是否合法。
代码如下：
CPP
for(int i=pos+1;i<=n;i++){
    if(a[i]>m2&&(a[i]>m1||a[i]<a[i+1]))m2=a[i];
    else if(a[i]<m1)m1=a[i];
    else break;
    ans+=(m1>dp1[i]&&m2<=dp2[i]);
}
最后不要忘记 把整个序列翻转，再做一遍。
完整代码如下：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
const ll inf=1e18;
ll n,ans,a[N],dp1[N],dp2[N];
void solve(){
    ll pos=0,m1=0,m2=0;
    for(int i=1;i<=n;i++)dp1[i]=1e9,dp2[i]=0;
    for(int i=1;i<=n;i++)if(a[i]>a[pos])pos=i;
    for(int i=n;i>pos;i--){
        if(a[i]>m2)m2=a[i];
        else if(a[i]>m1)m1=a[i];
        else break;
        dp1[i]=m1,dp2[i]=m2;
    }
    m1=m2=0;
    for(int i=1;i<=pos;i++){
        if(a[i]>m1)m1=a[i];
        else if(a[i]>m2)m2=a[i];
        else return;
    }
    for(int i=pos+1;i<=n;i++){
        if(a[i]>m2&&(a[i]>m1||a[i]<a[i+1]))m2=a[i];
        else if(a[i]<m1)m1=a[i];
        else break;
        ans+=(m1>dp1[i]&&m2<=dp2[i]);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    solve();
    reverse(a+1,a+n+1);
    solve();
    cout<<ans<<'\n';
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...