Educational Codeforces Round 145 (Rated for Div. 2)

B

1. 逆推，答案为多少时，最大满足的点的多少
2. 可以直接找规律 $(n + 1) ^ 2$
3. 如 1 的思路，从外到内构造，再计算点数

C

1. 构造题，先构造几个 2，保证这几个数内部能够为正数
2. 再构造一个数，满足剩下的正数
3. 剩下全为负无穷

D

1. 可以 DP
2. 由数据大小可知，是要总操作数最小，再满足删除操作最少
3. 由 2 可知，交换操作只有一次，如果有多次，必然会作用到同一个元素，而不如将这个元素删除
4. 由 3 可知，既可以枚举交换操作的点

E

1. 做题可以先想暴力解法，再优化复杂度，比如说 $O(n \times a \times b)$ 的复杂度 n 肯定不能消去，所以考虑降低复杂度 $(a \times b)$
2. 发现当 c + d 固定时，总和总是不变，考虑 c + d 相同时，c 不同的情况
3. 发现当 c 处于合适范围内时，可以满足所有操作而不考虑限制，此时只需要 $c - sum$ 即可
4. 而如果超出边界，发现答案即使临界情况，所以此题主要是算出临界的上下界为多少
5. c 的下界即是使 c 经历一些操作后能够刚好变成最小值 $max(0, c + d - b)$，c 的上界即是使 c 经历一些操作后能够刚好变成最大值 $min(a, c + d)$
6. 拿最小值举例。显然如果初始水更小，那么任意操作后，a 中的水一定也是小于等于的，所以说如果下界满足了临界条件，则必然更小的值也能变成这种情况。最大值同理。
7. 考虑如果计算出下界，进行逆推。$l = \max(L, l + v[i])$，即类似求区间最大和的思路，从后开始，如果后面对前面能有贡献，则就在此基础上加上，如果说 $l + v[i] < L$，即代表回溯成了一个不可能的状态，后面不可能对前面有贡献，重新令 $l = L$

F

• 先考虑求一个的情况，可以在 1 处直接加满，2 处如果要加就加到刚好能走到下一个结点，记录上次加油是在 1 还是 2 处。最后答案减去 $remain * (lst == 1 ? 1 : 2)$
• 自然而然想到换根 DP，消去第一个的影响，如果第一个是 1，那么直接减去 $2 \times dis$ 即可
• 如果是 0，发现一个性质，如果中途经过了一个 1，那么后续状态都将相同，只需消去前面的影响。无非是考虑是将多少的油从原来的代价 1 变为代价 2（细节可能多，调了一会儿 :)）
• 如果中间没有 1，发现中途的代价可以不依靠前面的答案，直接计算即可

---

• 官方答案是倍增，意料之中，我一开始从倍增和换根里面选了换根，但发现码力不够，要写很久 :)

---

• jiangly 写的也是 $O(n)$ 的 DP，而且比我的换根简单很多，可惜我看不懂 :)

G

• 英语烂到题解都看不懂 :)