Educational Codeforces Round 171 vp 记录

A. Perpendicular Segments

4 min +0

唐题。

一眼限制紧的边必然连对角线，因为最小长度的限制是相同的所以另一条边也连对角线即可。

B. Black Cells

9 min +0

唐题。

显然最优策略是相邻的点匹配， $n$ 为奇数的情况有一个孤立点随便连，为了写起来方便设 $dp_{i,0/1}$ 表示前 $i$ 个点自己匹配，是否使用了新点的最小代价，转移显然。

C. Action Figures

19 min +0

贪心。

第一眼尝试从前往后返回贪心，很难做。

所以倒序考虑，显然要尽量让当前数被白嫖，扫到这里还没被匹配溢出且当前值可以当天买就可以白嫖。

D. Sums of Segments

26 min +0

二分，前缀和。

容易发现同一开头的区间在 $b$ 数组中是连续一段的，直接二分就可以找出有哪些开头的区间是整体被计入答案的，二分即可，贡献可以前缀和计算。

此时剩一段不全的区间，直接用前缀和的前缀和计算贡献即可。

E. Best Subsequence

不会做qwq

网络流题。

或起来以后 1 的个数是很难刻画的，所以考虑转化！

假设初始时 or 出来全是 1 ，也就是初始贡献是 -60 ，计算 0 的贡献，发现 0 的贡献的条件是有一些数与某位的 0 矛盾，两边不能同时选。

所以考虑最大独立集的建模，把每个位置和这个位置的数所有 1 的位置进行连边，由于二分图最大独立集= $n$ - 最小点覆盖，所以直接跑流就求完了。

F. Bermart Ice Cream

不会做qwq

巧妙 trick。

首先不管可持久化，考虑只有 2 3 4 操作怎么做。

可以发现修改要实现一个类似 queue 的东西，但是背包并不对 queue 友好，对 stack 更友好。

所以我们可以实现一个双栈模拟队列！

直接用双栈模拟队列即可实现 在尾部插入/在头部删除 和查询，每次查询合并答案是简单的，复杂度均为 $O(p)$。

现在考虑加入可持久化。

容易发现栈不太好在线可持久化，所以考虑离线下来建出版本树，容易发现此时只需要实现头尾插入删除即可！

根据双栈模拟队列的思路，可以直接得到一个单次 $O(len)$ 的实现方式，这显然不够优。

容易发现这时不够优是因为每次一边为空的时候都需要把另一边整体移动，这很不优。

所以可以直接在一边为空的时候只移动另一边的一半，这是均摊 $O(1)$ 的。

于是这题以 $O(qp)$ 的复杂度解决了。