CF1517E. Group Photo

题目大意

对于一个长度为 n 的序列,每个元素有一个权值 a_i ,现在为这个序列每个元素分配一个 C 或者 P 。如果将 a_i 分配了 C ,就按顺序把 i 扔到集合 C 里,否则就按顺序把 i 扔到 P 。得到
C={c_1,c_2,\dots,c_m}\quad(c_1<c_2<\dots<c_m)

P={p_1,p_2,\dots,p_k} \quad (p_1<p_2<\dots<p_k
且满足

C∪P={1,2,…,n}

C\cap P =\empty

c_i−c_{i−1}≤c_{i+1}−c_i

p_i−p_{i−1}≥p_{i+1}−p_i

并且要求
\sum\limits_{x\in C}a_x<\sum\limits_{x\in P} a_y
问涂色的方式有多少种?

Solution

C 中的下标必须递增,P 中的下标必须递减。我们会发现只有形如 PPP\dots CCCC 或者
(C/P)CC…CPCPC…PCPP…P(C/P)
利用前缀和统计第一种序列有多少满足即可,

对于第二种序列,我们枚举前面 C 的个数 ,二分 PC 的出现次数(可以发现满足单调性),剩下的放P,即可统计。

#include<bits/stdc++.h>
#define ll long long
const int mod = 998244353;
const int N = 2e5+10;
int n;
ll a[N], ans = 0,pre[N], _div[N];
void solve(int f,int b){
    ll p = 0 , c = 0 ;
    if(f) p+=a[1];
    if(b) c+=a[n];
    for(int i=1+f;i<=n-1-b;++i){ //PPCPCPC
        c+=a[i];
        int l = -1 ,r = (n-i-1-b)/2 + 1;
        while(l+1<r){
            int mid = l+r>>1,len=mid*2;
            if(c+_div[i+len]-_div[i]<p+pre[n-b]-pre[i+len]+_div[i+len-1]-_div[i-1])
                l = mid;
            else
                r = mid;
        }
        l++;
        ans=(ans+l)%mod;
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%lld",&a[i]),pre[i]=pre[i-1]+a[i];
        for(int i=1;i<=n;++i) if(2*pre[i]>pre[n]) ans++;
        for(int i=1;i<=n;++i) _div[i]=_div[std::max(i-2,0)]+a[i];
        for(int i=0;i<=1;++i)
            for(int j=0;j<=1;++j)
                solve(i,j);
        printf("%d\n",ans); 
    }
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注