线段树
Atcoder ARC149D – Simultaneous Sugoroku
官方题解做法是线性的,在此不再赘述。
考虑对于纸片 分别计算答案。每次暴力枚举显然不可取,但假若我们知晓对于 ,在 次操作以后纸片在数轴上的坐标 ,其中 是最小的取到 的位置,则对于 :
- 如果 不存在,则所有坐标整体向数轴正半轴平移 单位;
- 否则, 就将是起始点为 的纸片首次到达 点的位置,也即题目所求。所有小于 的坐标仍向正半轴平移 单位;而 的坐标,由于偏移量 符号翻转,则有 。依次考虑每一坐标,就会得到 。 (这里认为当 时仍然继续执行操作。维护 的坐标位置是为了计算 的答案。)
这是可以用区间树维护的:我们想要快速求出全局非正数最大值以及首次取到该最大值的位置,同时支持全局加 、后缀所有数符号翻转 ()。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置,采用延迟标记更新(两种操作对于前述信息是具有结合律的,形成幺半群)即可。
时间复杂度 ,常数一般。
CodeForces Round #502 Problem G – The Tree
这是lty数据结构专题里唯二自己做出来的题目中的一道。
如果不包含“将 的子树全部染白”的操作,应当怎样处理?
题目所给操作可以这样转述:令 为本次染色操作的节点。若 为白色,则立刻染黑并退出;否则我们找到其子树中的,与 相连的黑色连通块,则对于每个连通块底部节点,若其不是叶子节点,我们将其儿子染黑。
由于本题的树没有特殊性质,且将来加入回退操作,故而难以维护整个连通块以及其叶子节点。因此,我们可以从“在何种情况下,节点 被染黑”的方向考虑。
显然,只有从在 到根的路径上的节点开始的染色操作,才可能波及到 。假如最终 被染黑的一瞬,它被包含在了以 为根的连通块中。令链 为 ,那么自然想到,一种一定合法的染色序列是 ,其中有 ,也即我们每一步都在该连通块内部,并将连通块的最大深度推进一层。
这种序列确实合法(它是充分条件),但这真的是 被染黑的必要条件么? (更多…)
一场相当有收获的比赛。比赛链接
A – 石老板举世无双
解法一
尝试观察规律。我们发现,在完成次操作以后,左端点的可能取值为,右端点的可能取值为。假如现在我们达到最终状态,其。那么,在的二进制表示中,如果从高到底第位为,则在第轮中,有check (mid) == 0
,向右区间递归;否则向左区间递归。这是很容易解释的:若向右递归,则右端点不变。而在下一层,右端点表示中的所有系数乘,所以体现为二进制位末尾添一个。反之,就变成,在下一层中体现为。如果其有位为,则到达该状态的概率为。
以时的状态为例。的三位二进制表示为,则推断出在前三轮分别向右、左、右区间递归,到达其的概率为。 (更多…)
CodeForces Round #755 Div.2 F / Div.1 D Serious Business
此题整整困了我一天半,耗费了好几张草稿纸。实在走投无路,翻看题解,却发现正解曾经近在咫尺。有必要稍作整理。
考虑DP。
错误转移1
这道题与清理班次(《算法竞赛进阶指南》上的一道例题)过于相似,都是“给定一些段落,选择其中一些完整覆盖,求最小花费”的形式。记上述花费为。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在位置从第行转到第行,利用数据结构维护所有,在转移到第二行,解锁到达的最小代价。对于各行前缀和,我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在的时间内,计算出对于一个固定的起点,所有的值。 (更多…)