2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training7
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training7 [2021/05/29 22:32] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:2021_buaa_spring_training7 [2021/06/02 09:59] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| 首先顺序读入同时维护所有字符串长度。然后设 $\text{dp}(k,l,r)$ 表示 $S_k[l,r]$ 的 $\text{Ascii}$ 码和，记忆化搜索逆推。 | 首先顺序读入同时维护所有字符串长度。然后设 $\text{dp}(k,l,r)$ 表示 $S_k[l,r]$ 的 $\text{Ascii}$ 码和，记忆化搜索逆推。 | ||
| - | 关于时间复杂度，定义计算 $S_1,S_2\cdots S_n$ 的所有答案的时间复杂度为 $T(n)$。 | + | 关于时间复杂度，发现逆推过程有些类似线段树的区间询问，于是每层的询问仅有 $[1,R],[L,R],[L,|S(k)|]$。 |
| - | 假设已经算出了前 $n-1$ 项的答案，然后仅需计算第 $n$ 项。发现逆推过程有些类似线段树的区间询问，遇到询问完整 $S_i$ 的区间直接返回。 | + | 并且可以通过数学归纳法，得到 $[L,R]$ 仅有 $[L(k),R],[L,R(k)]$ 两种形式，其中 $L(k),R(k)$ 为固定值。 |
| - | 于是每层仅 $O(1)$ 个结点，且树的深度为 $O(n)$，于是又递归式 $T(n)=T(n-1)+O(n)$，进一步有 $T(n)=O(n^2)$。 | + | 于是每层区间最多多分裂 $4$ 个结点，层数为 $O(n)$，每层结点数为 $O(n)$，结点数为 $O(n^2)$。 |
| ps. 还可以在从后往前递推询问时将多个相交询问分割成若干不相交小区间，维护每个小区间对应的询问数。然后处理每个小区间对应的询问。 | ps. 还可以在从后往前递推询问时将多个相交询问分割成若干不相交小区间，维护每个小区间对应的询问数。然后处理每个小区间对应的询问。 | ||
2020-2021/teams/legal_string/jxm2001/contest/2021_buaa_spring_training7.1622298744.txt.gz · 最后更改: 2021/05/29 22:32 由 jxm2001
