526互联

AtCoder Regular Contest 169 (ARC169)

发布时间 2023-12-11 07:21:18作者: 樱雪喵

怎么有人 ARC A 卡了半天的？

A. Please Sign

考虑 \(i\) 位置上的数，下次它被加到 \(P_i\)，再下次被加到 \(P_{P_i}\)，因为这个序列有性质 \(P_i<i\)，这样加若干轮一定会到达 \(1\)。
令所有的 \(i\) 向 \(P_i\) 连边，则这是一棵以 \(1\) 为根的树。

设 \(f_i=\sum\limits_{j=1}^n [dep_j=i] a_j\)。其中 \(dep_1=0\)。
那么 \(A_1=f_0\)，一次操作相当于令所有 \(f_i\gets f_i+f_{i+1}\)。

首先如果 \(f\) 数组全都是 \(0\)，\(A_1\) 操作很多次后显然还是 \(0\)。
考虑 \(f\) 最后一个不为 \(0\) 的位置的符号，设这个数为 \(f_x\)。若 \(f_x>0\)，由于每次令 \(f_{x-1}\gets f_{x-1}+f_x\)，\(f_{x-1}\) 一定会在若干次操作后变为正数。这可以类似地推广到 \(f_{x-2},f_{x-3},\dots\)。因此操作次数足够多时，有 \(f_0>0\)，即 \(A_1>0\)。

\(f_x<0\) 同理。综上，我们得到结论：\(A_1\) 最后的符号与 \(f\) 数组最后一个不为 \(0\) 的位置符号相同。

Code 
#define int long long
const int N=2.5e5+5,inf=2e9;
int n,a[N],p[N],f[N],dep[N],mx;
vector<int> e[N];
void dfs(int u)
{
    mx=max(mx,dep[u]);
    for(auto v:e[u]) 
    {
        dep[v]=dep[u]+1;
        dfs(v);
    }
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=2;i<=n;i++) p[i]=read(),e[p[i]].push_back(i);
    dfs(1);
    for(int i=2;i<=n;i++) f[dep[i]]+=a[i];
    int flag=0;
    for(int i=n;i;i--)
        if(f[i]) {flag=f[i]>0?1:-1;break;}
    a[1]=flag*inf+a[1];
    if(a[1]>0) cout<<"+";
    else if(a[1]==0) cout<<"0";
    else cout<<"-";
    return 0;
}

B. Subsegments with Small Sums

先考虑一个确定的区间怎么求答案。

直接贪心，从左往右考虑这个序列，如果上一段能放下就放进上一段，否则新开一段。正确性比较显然。
那这个题就能做了：考虑左端点相同时每个右端点的答案，设这个和为 \(f_l\)。分为两种情况：

  • 只有一段，对答案的贡献为 \(1\)；
  • 有至少两段，但根据上面的贪心，它们第一段结束的位置均相同。设这个位置是 \(x\)。

那么 \(r\ge x\) 的区间可以看作 \([x,r]\) 的答案加 \(1\)，即有转移 \(f_l\gets f_x+(n-l+1)\)，答案为 \(ans=\sum\limits_{i=1}^n f_i\)。
找 \(x\) 的过程双指针或二分均可。

Code 
#define int long long
const int N=2.5e5+5;
int n,s,sum[N],a[N];
int f[N];
signed main()
{
    n=read(),s=read();
    for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];
    for(int i=n;i;i--)
    {
        int nxt=lower_bound(sum+1,sum+n+1,sum[i-1]+s+1)-sum;
        f[i]=f[nxt]+(n-i+1);
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans+=f[i];
    printf("%lld\n",ans);
    return 0;
}

C. Not So Consecutive

读错题了，写了一车组合数还在想为什么过不去最后一个样例。

设 \(f_{i,j}\) 表示填了前 \(i\) 个位置，第 \(i\) 个位置填的是 \(j\) 的方案数。那么枚举这个连续段的起点，朴素转移有

\[f_{i,j}=\sum_{k=\max(0,i-j)}^{i-1} [\forall l\in [k+1,i],A_l=-1 \text{ or } A_l=j]\sum_{col\neq j} f_{k,col} \]

这样直接做是 \(\mathcal{O}(n^4)\) 的，考虑优化。

首先方括号里那一串式子本质上是找 \(i\) 前面最后一个填了不为 \(j\) 的数的位置，设这个位置为 \(lst\)。

对每个数维护 \(pos_j\) 表示数 \(j\) 当前最后一次出现的位置。那么对于每个新的 \(i\)，我们记录 \(pos\) 的最大值和次大值即可。

这个过程对每个 \(i\) 可以 \(\mathcal{O}(n)\) 完成。式子变成了

\[f_{i,j}=\sum_{k=lst}^{i-1} \sum_{col\neq j} f_{k,col} \]

再把 \(col\neq j\) 这个条件容斥掉，有

\[f_{i,j}=\sum_{k=lst}^{i-1} \sum_{col=1}^n f_{k,col}-\sum_{k=lst}^{i-1}f_{k,j} \]

设 \(S_i=\sum\limits_{j=1}^i \sum\limits_{col=1}^n f_{i,col}\)，\(s_{i,j}=\sum\limits_{k=1}^i f_{k,j}\)，前缀和优化即可。时间复杂度 \(\mathcal{O}(n^2)\)。

Code 
#define int long long
const int N=5005,mod=998244353;
int pos[N],f[N][N],s[N][N],sum[N],n,a[N];
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    f[0][0]=1,sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=-1) pos[a[i]]=i;
        int mx1=0,mx2=0;
        for(int j=1;j<=n;j++) 
        {
            if(pos[j]>mx1) mx2=mx1,mx1=pos[j];
            else if(pos[j]>mx2) mx2=pos[j];
        }
        for(int j=1;j<=n;j++)
        {
            int lst=max(i-j,(a[mx1]==j)?mx2:mx1);
            f[i][j]=sum[i-1]-(lst?sum[lst-1]:0)-(s[i-1][j]-(lst?s[lst-1][j]:0));
            f[i][j]=(f[i][j]%mod+mod)%mod;
            s[i][j]=(s[i-1][j]+f[i][j])%mod;
            (sum[i]+=f[i][j])%=mod;
        }
        (sum[i]+=sum[i-1])%=mod;
    }
    cout<<(sum[n]-sum[n-1]+mod)%mod<<endl;
    return 0;
}

D. Add to Make a Permutation

你先别急。