ABC353 | 如同流星划过天空

A. & B.

依题意模拟即可。

C.

注意只有 \(f(x,y)\) 需要对 \(10^8\) 取模，\(f\) 的求和不需要。

关注到 \(a_i \in [1,10^8)\)，故 \(a_i + a_j \in [2,2 \times 10^8)\)。

从而 \(f(x,y)=[x+y<10^8](x+y)+[x+y\ge 10^8](x+y-10^8) = x+y -10^8[x+y\ge 10^8]\)。

只需统计有序对 \((i,j)\) 使 \(a_i + a_j \ge 10^8\) 的对数即可。

枚举 \(i\)，\(j\) 的个数是在值域上一个后缀和，容易做到 \(O(n)\)。

\(\color{green}{\checkmark}\)

D.

把式子变形成 \(f(x,y)=x\times 10^{\lceil\log_{10}y\rceil}+y\)，然后拆和式即可用缀和优化。

\(\color{green}{\checkmark}\)

E.

多串 LCP 让我们想到 Trie 树。

考虑将 \(f(x,y)\) 的贡献挂在 \(y\) 上。

考虑在 Trie 树上插入的过程，每次匹配一位，我们就将在当前位失配字符串数乘上匹配长度贡献给答案即可。

\(\color{green}{\checkmark}\)

F. \(\color{#DB7D74}{\star}\)

感受那股劲。

先感受一下，曼哈顿距离是可能的答案。当 \(k=1\) 时这就是答案。

\(k>1\) 时，考虑大格子会对答案产生什么影响。

感受一下，随着 \(k\) 变大，最优方案直接穿过 \(k\times k\) 的小格子的个数断然不增。因为我们能从大格子绕路。

用一下官方题解的图：

当 \(k\) 较大时，通过左边这种方式绕路代替直接穿过是更优的。具体计算知，当 \(k=2\) 时，直接穿过更优，\(k>2\) 时，绕路更优。

那就做完了。

\(\color{green}{\checkmark}\)

G.

dp，\(f_{i,j}\) 表示已经考虑了 \([0,i)\) 的交易，目前位于 \(j\) 城市。

考虑第 \(i\) 个交易 \((T,p)\) 的转移。

首先要有 \(f_{i+1}=f_i\)，含义是原地不动。

然后是 \(f_{i+1,T}=\max\limits_{j\in[0,n)}\{f_{i,j}-|j-T|\times C\}+p\)。

把绝对值拆开，变形：\(f_{i+1,T}=\max\{\max\limits_{j\in[0,T)}\{f_{i,j} +jC\}-TC+p,\max\limits_{j\in[T,n)}\{f_{i,j}-jC\}+TC+p\}\)。

考虑用数据结构优化转移，发现我们要做的是单点修改，求前后缀最大值，开两颗 BITS 分别维护 \(f_{i,j} \pm jC\) 即可。

注意由于答案是 \(\max{f_{i,j}}\)，所以不能在 BITS 上查全局最大值作为答案，要把每次转移时计算出的 \(f_{i+1,T}\) 取最大值作为答案。

\(\color{green}{\checkmark}\)