ARC169-526互联

[ARC169A] Please Sign

每个点会一直一直给它的父节点加，所以深度越深的点影响越大，统计出每个深度的点权和，从深到浅判断正负，有正负就输出答案，全都没有就是 $0$。

$\texttt{Code}$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=3e5+10;
int n,a[N],dep[N],sum[N];
il int read(){
    re int x=0;re char c=getchar(),f=0;
    while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?-x:x;
}
signed main(){
    n=read();
    for(re int i=1;i<=n;i++)a[i]=read();
    sum[0]=a[1];
    for(re int i=2;i<=n;i++)
        sum[dep[i]=dep[read()]+1]+=a[i];
    for(re int i=n;i>=0;i--)
        if(sum[i])return putchar(sum[i]>0?'+':'-'),0;
    putchar('0');
    return 0;
}

[ARC169B] Subsegments with Small Sums

想起了 ARC060E。考虑倍增。

然后套一个 $dp$，$f_i$ 表示从任意起点走到 $i$ 的方案总和。

发现倍增没有用，还会算重，所以换回初始的东西，就是预处理出 $nxt_i$ 表示 $i$ 跳一步最远跳到哪儿。

对于每一组 $[i,nxt_i]$ 我们从 $i$ 跳到 $[i,n]$ 中的任意一个位置都会用到它，所以 $i$ 位置的贡献是 $(n-i+1)f_{i-1}$，然后转移一下 $f$，$f_{nxt_i}=f_{nxt_i}+f_{i-1}$。

我也很震惊竟然直接就过了，开心。

$\texttt{Code}$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=3e5+10;
int n,S,a[N],nxt[N],f[N],s[N],ans;
il int read(){
    re int x=0;re char c=getchar(),f=0;
    while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?-x:x;
}
signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    n=read(),S=read();
    for(re int i=1;i<=n;i++)a[i]=read(),s[i]=s[i-1]+a[i];
    for(re int i=1;i<=n;i++)
        nxt[i]=upper_bound(s+1,s+1+n,s[i-1]+S)-s-1;
    for(re int i=0;i<n;i++)f[i]=1;
    for(re int i=1;i<=n;i++){
        ans+=(n-i+1)*f[i-1];
        f[nxt[i]]+=f[i-1];
    }
    cout<<ans;
    return 0;
}

[ARC169C] Not So Consecutive

像一般的线性 $dp$ 按每一位考虑是不容易的，因为需要知道这一位填什么，已经连续填了多少个，状态数就是 $O(n^3)$ 的。当然好像也能做，但我没发现第一篇题解的那个队列+维护和，感觉可能是因为没有认真地把式子写下来导致的。

考虑按连续段转移，设 $f_{i,j}$ 表示填了前 $i$ 个位置，最后填了一个颜色为 $j$ 的连续段。

枚举连续段的起点 $k$，这里需要满足 $[k,i]$ 里面没有已经被确定为其他数（$\neq j$）了的。这个我们可以记录一个 $pos$ 存每个颜色最后出现的位置，每次到了一个被确定的位置就更新，然后对所有 $pos$ 求最大值 $mx1$ 和次大值 $mx2$，如果 $a_{mx1}=j$，那么那么 $k$ 最远可以到 $mx2$，否则可以到 $mx1$，注意为了满足题目的限制还要对 $i-j$ 取一个 $\max$，然后把这个最远可以取到的位置记为 $lst$。

转移就比较简单：

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

把 $col\neq j$ 容斥掉：

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

$O(n^4)$，于是发现这两部分都可以用前缀和优化掉，$O(n^2)$。

$\texttt{Code}$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=5010,mod=998244353;
int n,a[N],pos[N],f[N][N],s[N][N],S[N];
il int read(){
    re int x=0;re char c=getchar(),f=0;
    while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?-x:x;
}
signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    n=read();
    for(re int i=1;i<=n;i++)a[i]=read();
    f[0][0]=S[0]=1;
    for(re int i=1;i<=n;i++){
        if(a[i]!=-1)pos[a[i]]=i;
        int mx1=0,mx2=0;
        for(re int j=1;j<=n;j++)
            if(pos[j]>mx1)mx2=mx1,mx1=pos[j];
            else mx2=max(mx2,pos[j]);
        for(re int j=1;j<=n;j++){
            int lst=max(i-j,(a[mx1]==j)?mx2:mx1);
            f[i][j]=(S[i-1]-(lst?S[lst-1]:0)+mod-(s[i-1][j]-(lst?s[lst-1][j]:0)+mod)+mod)%mod;
            s[i][j]=(s[i-1][j]+f[i][j])%mod,S[i]+=f[i][j];
        }
        S[i]=(S[i]+S[i-1])%mod;
    }
    cout<<(S[n]-S[n-1]+mod)%mod;
    return 0;
}

[ARC169D] Add to Make a Permutation

很符合我对做思维题的感觉的期望。

显然这些操作就是每次选 $m$ 个数加一，最后全部 $\mod n$。先省去取模这一步，记最后得到的未取模的序列为 $b$。那么 $b$ 需要满足以下条件：

$\forall i\in [1,n],b_i\ge a_i$；
$b_i\mod n$ 之后两两不相同；
令 $sum=\sum_{i=1}^n (b_i-a_i)$，$m|sum$；
令 $mx=\max_{i=1}^n\{b_i-a_i\}$，$mx\le \frac{sum}{m}$。

考虑第四个条件，当操作数一定时，$mx$ 应尽量小才更有可能满足条件，又因为此时 $sum$ 一定，所以每个位置加的量应该尽量“均匀分配”。即我们把 $a$ 升序排序，那么操作完之后的 $b$ 序列也应是升序的，所以下面钦定 $a,b$ 都是升序的。

结论：若有解，那么一定存在一种最优解形如 $b=\{x,x+1,x+2,\dots,x+n-1\}$。

用调整法证明。假设我们得到了一个最优解 $b$，且 $b_n-b_1\ge n$，那么我们重新构造这两项：$b'_1=b_n-n,b'_n=b_1+n$。然后我们来 $\text{check}$ 一下是否仍然满足条件：

$b_n\ge b_1+n,b_1\ge a_1,b'_1=b_n-n\ge b_1\ge a_1$，$a_1+n\gt a_n,b_1\ge a_1,b'_n=b_1+n\ge a_1+n\gt a_n$；
加减 $n$ 不影响 $\mod n$ 之后的结果；
加减 $n$ 之后 $sum$ 不变，又因为答案只与 $sum$ 有关，所以答案不变，仍然最优；
$b'_n=b_1+n\le b_n,b'_n-a_n\le b_n-a_n$，$b_n-a_n\ge b_n-(a_1+n)=b_n-n-a_1=b'_1-a_1$。

综上，调整之后的序列仍然合法。

那么考虑计算最优解，即最小化 $x$ 的值。

第一个条件为 $x$ 提供了一个下界 $\max_{i=1}^n\{a_i-(i-1)\}$；
再看第四个条件，$x$ 没增加 $1$，不等式左边增加 $1$，右边增加 $\frac{n}{m}$，又因为 $m\lt n$，所以 $\frac{n}{m}\gt 1$，因此它也为 $x$ 提供了一个下界。

最后只需要满足第三个条件就好了，发现 $x$ 与 $x+m$ 对这个条件而言是等价的，并且后者答案更劣。所以只需从 $x$ 开始往上枚举 $m$ 次到 $x+m-1$ 即可。

$\texttt{Code}$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=3e5+10;
int n,m,a[N],x,sum,mx;
il int read(){
    re int x=0;re char c=getchar(),f=0;
    while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?-x:x;
}
signed main(){
    n=read(),m=read();
    for(re int i=0;i<n;i++)a[i]=read();
    sort(a,a+n);
    for(re int i=0;i<n;i++)x=max(x,a[i]-i);
    for(re int i=0;i<n;i++)sum+=x+i-a[i];
    bool flg=0;
    for(re int i=0;i<m;i++)
        if(!((sum+n*i)%m)){
            flg=1,x+=i,sum+=n*i;
            break;
        }
    if(!flg)return puts("-1"),0;
    for(re int i=0;i<n;i++)mx=max(mx,x+i-a[i]);
    while(mx>sum/m)mx+=m/__gcd(n,m),sum+=n*m/__gcd(n,m);
    cout<<sum/m;
    return 0;
}

atcoder regular contest 169

169 atcoder regular contest

169d可控硅单向bt