专栏文章

数据结构/大模拟题记

TTom17
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min9g7ei
此快照首次捕获于
2025/12/01 22:44
3 个月前
此快照最后确认于
2025/12/01 22:44
3 个月前
查看原文
  1. 如何写大模拟
摘自 P13065 [GCJ 2020 #2] Emacs++ 的 提交记录。
出现问题：
  1. calc 函数中将oval[x][0/1] 和 oval[y][0/1] 写作 oval[u][0/1] 和 oval[v][0/1]
    • 误将下标写作 id。
  2. dfs2 中将右值 oval[cu][0] 写作 oval[cu][1]， oval[cu][1] 写作 oval[cu][0]。
    • 属于理解不好，也可能是笔误。
  3. calc 函数中返回值 LL 写作 int。
    • 建议再检查一次。
代码注释：
  1. 代码中将每个匹配括号重新标号，idid 表示某对括号的 idid
  2. wlwl，wrwr 和题面的有所不同：wl[i]wl[i] 表示 i→i+1i\rightarrow i+1 的边权，wr[i]wr[i] 表示 i→i−1i\rightarrow i-1 的边权 相当于从该点出发的边权，且该点位于 l/r 侧，如果填指向侧不那么明了
  3. pla[id][2]pla[id][2] 表示对应 idid 的左右括号的位置，gidgid 表示对应位置括号的 idid
  4. rnkrnk 表示某个 id 在其父亲的儿子中排第多少个 用于查询时的偏序判断
  5. oval[id][0/1oval[id][0/1] 表示从 idid 括号对的一端走向另一端的距离，00 为左到右，11 为右到左
  6. odlodl 往后的 88 个数组记录的是距离关系
  • 下标 [id][0/1][id][0/1] 表示记录的是 idid 的左括号/右括号到某个位置（或者某个位置 到 idid 的左括号/右括号） 的信息
  • 下面称该位置为 plapla
  • odlodl : 从 plapla 到其上一级父亲的左括号
  • odrodr : 从 plapla 到其上一级父亲的右括号
  • pdlpdl : 与 odlodl 相反，从 plapla 的上一级父亲的左括号到 pla
  • pdrpdr : 与 odrodr 相反，从 plapla 的上一级父亲的右括号到 pla
  • udludl : 从 plapla 到其 kk 级父亲的左括号
  • udrudr : 从 plapla 到其 kk 级父亲的右括号
  • ddlddl : 与 udludl 相反，从 plapla 的 kk 级父亲的左括号到 pla
  • ddrddr : 与 udrudr 相反，从 plapla 的 kk 级父亲的右括号到 pla
  1. odl/odr/pdl/pdrodl/odr/pdl/pdr 是辅助数组，在 dfs1 后就没有动过了，所以其实际上记录的是走儿子方向的信息 在 dfs3 中，直接将其信息和走父亲方向的信息 打包给 对应的 kk 级父亲的信息数组 所以 odl/odr/pdl/pdrodl/odr/pdl/pdr 不包含往父亲方向的信息
  2. calc 函数中：
  • disx[0/1]disx[0/1] 表示从起点出发，到达当前的 xx 的左右括号的距离。
  • disy[0/1]disy[0/1] 表示从当前的 yy 的左右括号出发，到达终点的距离。
  1. 将 00 号点当作虚点，并将第一层的括号串在一起，但是不允许跨过 00 号点，所以将其跨越边权设为 00。
启示：
  1. 要把所有信息记在主元的位置
  • 就是说有一种方法是将信息记录在 某个 cucu 的第 kk 个儿子的 vector<int>[cu][k] 上。
  • 但是这样每次查询的时候就会要先查 idid 再转为 rnkrnk 查询，并且有溢出的风险。
  • 对于这种树上问题，一般直接将信息记录在儿子处
  • 并且以儿子的信息（不同点）作为数组的下标，将指向的信息设为名称
  • 这样会比较清晰
  1. 合理使用 std::array 可以将数组整体转移 并且一般 std::array 的溢出是 0，vector 溢出后值比较大
  2. 合理使用 lambda 函数，记得一般要 [&]
  1. B3594. 【NOIP模拟】美食 / P12730 [KOI 2021 Round 2] 美食推荐
本题第一次提交代码的算法考虑树形 DP，要点是：状态记录当前是 cucu 子树，只考虑 cucu 子树内的贡献，且 cucu 子树内的已选点所延伸的最小深度（可能为负），合并形如一个下标第二维：深度取 min⁡\min，限制条件；合并的两个深度之和大于当前点深度（需要考虑一个点延伸到另一个子树的情况）。朴素做法视实现是 O(n2)∼O(n3)O(n^2)\sim O(n^3) 的。考虑用线段树记录第二位，然后启发式合并，线段树本质不同状态数是 O(m)O(m) 的，时间是 O(mlog⁡m)O(m\log m)。
这里主要复习一下线段树的多标记合并。
然后还有序列单调性对线段树的操作优化。
还有一些大模拟的习惯。

1. 线段树多标记合并 (max)。

我们考虑这样的结构：区间加，区间取 max⁡\max，区间最大值。
显然维护加标记和取 max⁡\max 标记。
取 max⁡\max 标记对加标记没有影响，而加标记对取 max⁡\max 标记有加的影响，这个不能忘记。
这里没有查区间和，不需要吉司机线段树，只有说区间取 max⁡\max 或 min⁡\min 操作，同时需要区间加的时候才需要吉司机。吉司机注意势能即可，记录一个最大值/次大值即可。

2. 序列单调性对线段树的操作优化

注意到树形 DP 写法要对序列取一个“向前 max⁡\max”操作，即对于每个元素 arriarr_i 其要对 j>ij>i 的元素 arrjarr_j，使得 arri←max⁡{arri,arrj}arr_i\leftarrow \max \{arr_i,arr_j\}。
考虑上面几个操作如何优化。
首先区间 max⁡\max 可以变为单点 max⁡\max。但发现这样修改实现的就会比较多，所以可以考虑对修改分析。
发现 “向前取 max⁡\max” 这个操作可以变为查询单点改，然后查询后缀查。
我们注意到说区间 max⁡\max 这个操作本质上就是右端点取 max⁡\max，然后向前取 max⁡\max。然后向前取 max⁡\max 就变为查询时再往后查询。所以这一部分就可以变为单点取 max⁡\max。
区间加是简单的。
所以就不用写两个标记和 down 函数一大堆的下传了。
当有两个区间修改操作时，若存在某些性质，那么我们需要思考能否通过某些性质，使得其中一个的区间修改操作变为单点修改操作。以减少代码长度。
  1. 大模拟的习惯
  • 写对拍，争取是通过对拍拍出来的问题，这样子在考场上才能调试出来。
  • 验证内置数据结构的问题：还是对拍，考虑你的线段树或者其他的什么数据结构，本身自己有没有什么问题。也要通过对拍来写。
  • 先写暴力，验证暴力的正确性后，再通过暴力来撰写正解。（这里的暴力不是纯粹的暴力，而是把正解中要用数据结构的转移先用暴力写一次，保证暴力没有问题再写正解，这样不会出现正解写到最后发现其实是伪解的情况。）
  • 多用 debug 和 cerr，这个可能才是拍出来问题后最直接的调试方法。瞪眼是瞪不出来的。
  • 总结问题：考虑每次写完大模拟/数据结构后总结问题，写在 数据结构/大模拟易错提醒 中，不时复习。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...