个人博客地址：blog.jerryhzy.top
比赛链接 Educational Codeforces Round 158 (Rated for Div. 2)
目前进度：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| solved contest | solved contest | solved contest | solved contest | solved later | not solved |
A. Line Trip
简要翻译
在一维数轴上，有一辆车，刚开始在 $$$0$$$ 且油箱为满，走一个单位消耗一升油，经过 $$$a_1,a_2\ldots a_n$$$ 处可加满油。
现在需要从 $$$0$$$ 走到 $$$x$$$ 再走回 $$$0$$$ ，求能完成路径的油箱油量最小值。
思路解析
先不考虑回程，设 $$$a_0=0$$$，则 $$$ans = \underset{1\le i\le n}{max} \lbrace a_{i}-a_{i-1} \rbrace$$$ 。
在 $$$x$$$ 处转弯时不能加油，所以有 $$$ans = \max(ans,2(x-a_n))$$$ 。
返程和去程一样，不用再统计。
B. Chip and Ribbon
简要翻译
有一列 $$$n$$$ 个格子和一个指针，一开始格子里的数 $$$a_i=0$$$ 。
第 $$$1$$$ 步，Mococarp 会把指针放在第一个格子上，接下来每一步可以做下列两种移动之一：
若指针在第 $$$i$$$ 个格子上，且 $$$i \neq n$$$，则将指针放在 $$$i+1$$$ 上。
将指针放在任意一个格子上（可以放在同一个格子上）。
每一步之后，若指针在第 $$$x$$$ 个格子上，则 $$$a_x$$$ 加一。
现在，Mococarp 想尽可能少的使用移动 $$$2$$$ ，使得 $$$\forall i\in [1,n],a_i=c_i$$$ 。
思路解析
只使用移动 $$$1$$$ 时相当于给一个区间加一，问题转化为用多少个区间可以使 $$$i$$$ 被 $$$c_i$$$ 个区间包含。
那么 $$$c_i>c_{i-1}$$$ 时表示有 $$$c_i -c_{i-1}$$$ 个区间要从 $$$i$$$ 开始， $$$ans+=c_i-c_{i-1}$$$ 。
C. Add, Divide and Floor
简要翻译
有一个数组 $$$\lbrace a_n \rbrace$$$ ，每次可以选一个 $$$x$$$ ，将所有 $$$a_i$$$ 赋值为 $$$\lfloor \dfrac{a_i+x}{2} \rfloor$$$ ，求最少次数使 $$$a_1=a_2=\cdots=a_n$$$ 。
思路解析
先考虑两个数 $$$x,y(x<y)$$$ 如何化为相等值。
考虑两者的差值，若选的数 $$$v \ge 2$$$ 则总有等效操作。
如果 $$$v\ge 2$$$ 且为偶数，则 $$$\lfloor \dfrac{x+v}{2} \rfloor = \lfloor \dfrac{x}{2} \rfloor+\dfrac{v}{2}$$$ ， $$$\lfloor \dfrac{y+v}{2} \rfloor = \lfloor \dfrac{y}{2} \rfloor+\dfrac{v}{2}$$$ ，和直接除以二的效果相同。
如果 $$$v\ge 2$$$ 且为奇数，则和加一再除以二的效果相同。
观察样例，在 $$$x$$$ 为奇数 且 $$$y$$$ 为偶数时，加一再除以二相当于除以二后只给 $$$x$$$ 加一。
其他情况下，加一再除以二不如直接除以二。
因为 $$$x\le y \Leftrightarrow \lfloor \dfrac{x+v}{2} \rfloor \le \lfloor \dfrac{y+v}{2} \rfloor$$$ ，所以只用考虑数列中的最小值和最大值，其他值经过操作后也一定夹在两数中间。
D. Yet Another Monster Fight
简要翻译
有 $$$n$$$ 个怪兽，第 $$$i$$$ 个的生命值为 $$$a_i$$$ 。
Vasya 有闪电法术，他可以选择初始威力 $$$x$$$ 和攻击的第一个怪兽 $$$i_1$$$ 。
每次攻击后，闪电会随机攻击一个尚未被攻击且旁边有被攻击过怪兽的怪兽。
第 $$$k$$$ 次攻击的怪兽 $$$i_k$$$ 收到 $$$(x-k+1)$$$ 点伤害，这个值大于等于 $$$a_i$$$ 会使怪兽死亡。
现在 Vasya 想确定最小的 $$$x$$$ ，使得在适当挑选 $$$i_1$$$ 后，无论闪电的攻击顺序如何，所有怪兽都会死亡。
思路解析
对于 $$$a_i$$$ ，考虑 $$$i_1<i$$$ 和 $$$i_1>i$$$ 的情况。
- $$$i_1<i$$$：$$$a_i$$$ 能影响 $$$x$$$ 取值的最坏情况是，把前 $$$i-1$$$ 个数都消灭之后再消灭 $$$a_i$$$，对应的 $$$x$$$ 至少为 $$$a_i+i-1$$$ 。
- $$$i_1>i$$$：最坏情况变为，把后面 $$$a_{i+1} \sim a_n$$$ 都消灭后再消灭 $$$a_i$$$，对应的 $$$x$$$ 至少为 $$$a_i+n-i$$$ 。
第一种情况求后缀，第二种情况求前缀（ $$$\max$$$ ），然后 $$$i_1=i$$$ 时的答案为 $$$\max \lbrace pre_{i-1}, a_i, nxt_{i+1} \rbrace $$$ ，取最小值即可。
E. Compressed Tree
简要翻译
有一棵 $$$n$$$ 个点的树，每个点有权值 $$$a_i$$$ 。
在第一阶段，你可以选择任意一个有至多 $$$1$$$ 条边的点，并删除这个点和它所连的边。可以重复任意次。
在第二阶段，所有度为 $$$2$$$ 的点将被删去，原来和它相连的 $$$2$$$ 个点之间生成一条新边。一直重复直到不存在度为 $$$2$$$ 的点。
求压缩后剩下的点的权值和最大值。注意，权值可以是负数。
思路分析
比赛时想到树形 dp，但是想到换根去了，最后浪费一个小时。
官方题解的说法，是按保不保留 $$$x$$$ 与父亲 $$$fa_x$$$ 的边，以及 $$$x$$$ 保留儿子的个数来讨论的。
设 $$$f_x$$$ 为 保留 边 $$$(x,fa_x)$$$ 时， $$$x$$$ 及其子树内压缩后的最大权值和。
则讨论 $$$x$$$ 保留儿子的个数：
不保留： 只保留 $$$x$$$ 作为叶子， $$$f_x =\max(f_x,a_x)$$$ 。
保留 $$$1$$$ 个：那么 $$$x$$$ 恰好有两条边，压缩后消失， $$$f_x=\max(f_x,\underset{y}{\max}f_y)$$$ 。
保留 $$$2$$$ 个及以上： $$$x$$$ 可以保留， $$$f_x=\max(f_x,a_x+\underset{y}{\sum}\max(0,f_y))$$$ ，至少选两个 $$$f_y$$$ 。
考虑 不保留 边 $$$(x,fa_x)$$$ 时， $$$x$$$ 子树外的节点全部都被删除了。
再讨论保留儿子的个数：
不保留： $$$ans=\max(ans,a_x)$$$ 。
保留 $$$1$$$ 个： $$$ans=\max(ans,a_x+\underset{y}{max}f_y)$$$ 。
保留 $$$2$$$ 个： $$$x$$$ 恰好会被压缩， $$$ans=\max(ans,\underset{y_1,y_2}{\max}(f_{y_1}+f_{y_2}))$$$ 。
保留 $$$3$$$ 个及以上： $$$ans=\max(ans,\underset{y}{\sum}\max(0,f_y))$$$ ，至少选三个 $$$f_y$$$ 。
儿子个数用类似 $$$01$$$ 背包的写法，非常巧妙。
F. Landscaping
简要翻译
没看懂呢
思路分析
没想出来呢
代码
没写呢
Auto comment: topic has been updated by a999999 (previous revision, new revision, compare).
Auto comment: topic has been updated by a999999 (previous revision, new revision, compare).
Auto comment: topic has been updated by a999999 (previous revision, new revision, compare).