怎么有人 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
你先别急。
标签：ARC169,AtCoder,int,sum,pos,long,dep,Regular,col From： https://www.cnblogs.com/ying-xue/p/arc169.html