526互联

AtCoder Regular Contest 169

发布时间 2023-12-12 10:53:40作者: Alan_Zhao_2007

A - Please Sign

某个 \(A_i\) 对 \(A_1\) 的贡献是 \(\binom{10^{100}}{\mathrm{dep}_i}\)，所以深度为 \(d\) 的节点的 \(A_i\) 之和只要不为 \(0\)，其贡献就一定远大于深度 \(<d\) 的所有点的贡献之和。

从大到小找到第一个和非零的深度即可。

B - Subsegments with Small Sums

直接考虑以每个位置为开头的段在答案中出现了多少次即可。

C - Not So Consecutive

直接 DP，设 \(f_{i,j}\) 表示当前考虑了前 \(i\) 个位置，且第 \(i\) 个位置填的数是 \(j\) 的方案数。转移是

\[f_{i,j}=\sum_{\max(\mathrm{last}_j,i-j)\le k<i} \sum_{l\neq j} f_{k,l}. \]

其中 \(\mathrm{last}_j\) 表示最大的 \(k\) 使得 \(k\le i\land A_k\neq -1\land A_k\neq j\)。

前缀和优化一下，可以做到 \(O(N^2)\)。

D - Add to Make a Permutation

首先，假设我们不进行取模操作，设最后得到的数列是 \(B_1,B_2,\dots,B_N\)，那么只需要 \(B_i\bmod N\) 互不相同，即可满足条件。

考虑什么样的 \(B\) 是可以得到的。设 \(S=\sum_{1\le i\le N} (B_i-A_i)\)，需要：

  • \(B_i\ge A_i\)；
  • \(M\mid S\)；
  • \(B_i-A_i\le \frac{S}{M}\)。

（赛时我漏了第三个条件，而且用的是另外一种做法，没法处理这个条件。）

然后发现最优的 \(B\) 序列有一些性质：

性质 1：假如 \(A\) 是递增的，那么最优的 \(B\) 是不降的。

证明：交换一对逆序的 \(B_i\) 不会使 \(S\) 改变，且会使得 \(\max(B_i-A_i)\) 变小。

性质 2：假如 \(A\) 是递增的，那么最优的 \(B\) 形如 \([x,x+1,\dots,x+N-1]\)。

证明：由于 \(B\) 是递增的且 \(B_i\bmod N\) 互不相同，所以只要 \(B\) 不是这样的，就一定存在 \(i,j\) 使得 \(B_j>B_i+N\)。此时令 \((B_i,B_j)\gets (B_i+N,B_j-N)\)，再将 \(B\) 数组排序，得到的 \(B\) 一定更优。

于是我们只需要找到最小的 \(x\)，使得其对应的 \(B\) 序列是可以得到的。上面的第 \(1,3\) 条限制对应了 \(x\) 需要大于等于某个数；第二条对应了 \(x\equiv k\pmod{\frac{M}{\gcd(N,M)}}\)，其中 \(k\) 是某个数。

E - Avoid Boring Matches

怎么想到的？？？

首先考虑判定一个串 \(S\) 是不是 boring 的。

如果 \(S\) 中 \(\texttt{R}\) 的个数大于一半，就一定是 boring 的。

  • 假如 \(S_1=\texttt{R}\)，那么它和最后一个 \(\texttt{B}\) 配对一定是最优的；
  • 否则，它和它后面的第一个 \(\texttt{R}\) 配对是最优的。

这样就可以将长为 \(2^N\) 的串以最优的方式缩成长为 \(2^{N-1}\) 的串。

考虑所有长为 \(2^N\) 且不 boring 的串中，字典序最大的一个，设为 \(T\)。\(T\) 可以通过反向模拟上面的贪心过程得到。有结论：

对于串 \(S\)，设 \(f_S(i)\) 表示将 \(S\) 中的 \(\texttt{R}\) 看作 \(-1\)，\(\texttt{B}\) 看作 \(1\)，\(i\) 位置的前缀和。

\(S\) 不是 boring 的，当且仅当对于每个 \(i\)，都有 \(f_S(i)\ge f_T(i)\)。

回到原问题，算出每个 \(f_S(i)\)，交换相邻的 \(\texttt{R},\texttt{B}\) 对 \(f\) 的影响就是将 \(\texttt{R}\) 所在的位置 \(+2\)。并且，只要存在至少一个位置使得 \(f_S(i)<f_T(i)\)，就一定可以将某个这样的位置 \(+2\)。

所以答案就是

\[\sum_{1\le i\le 2^N} \max\left(0,\frac{f_T(i)-f_S(i)}{2}\right). \]

F - Large DP Table

关键结论：

考虑两个点 \((a,b),(c,d)\) 满足 \(c\ge a,d\ge b\)。将 \((c,d)\) 走到 \((1,1)\) 的那条路径画出来，路径会穿过 \(Y=b\) 这条线（也就是说，\(X_a,X_{a+1},\dots,X_{N}\) 中有某一个造成了一次贡献），当且仅当 \(\min_{a\le i\le c} A_i<\min_{b\le i\le d} B_i\)。否则，路径会穿过 \(X=a\) 这条线。

然后用单调栈随便做做即可。时间复杂度 \(O(N)\)。