2020.11.11笔记

Educational Codeforces Round 97

A

看看样例,猜一手取 $a=r+1$,交上去过了。

B

枚举是变成 $1010 \dots 10101$ 还是 $0101 \dots 0101$,然后就可以知道哪些位置需要变了。

一个子串操作可以看做是对两个前缀进行操作,因此倒着扫,需要操作的时候就操作即可。

记 $r$ 为前缀为操作次数,则还原为字串操作的次数为 $\lceil \frac{r}{2} \rceil$。

C

显然把 $a_i$ 排序不会造成任何影响。

不难发现 $b_i$ 是单调的,因此可以直接 $dp$。

$f_{i, j}$ 表示第 $b_i=j$ 时的最小代价,转移直接暴力可以做到 $O(n^3)$,前缀最小值优化一下可以做到 $O(n^2)$。

D

考虑模拟这个过程,记录 $t_i$ 表示现在有多少深度为 $i$ 的叶子。

每次求出极长的上升连续段,然后都接到最浅的叶子上(操作之后就不再是叶子了)。

因为是 $bfs$,不难发现每次取的最浅的叶子深度是单调不降的,一个指针维护一下即可。

E

初步的想法是求出相邻两个不动点之间的 $\text{LIS}$,但是仔细思考可以发现忽略了权值严格递增的限制。

权值递增的限制可以描述成:

$$a_i-a_j \leq i-j$$

移项可以得到:

$$a_i-i \leq a_j-j$$

同时也不难发现如果也满足 $i < j$,则可以推出 $a_i < a_j$。

因此使得 $a’_i = a_i-i$,然后求相邻不动点之间的最长不下降子序列即可。

F

读完题没什么头绪,看了题解才会。

显然可以升序排个序。

不难发现 $\ge 2x$ 只会有 $\log$ 次,但是没用上。

最重要的观察是:开心的渔夫的权值是单调递增的,剩下的都是不开心的。

因此可以先把一个渔夫 $a_i$ 放下来,此时所有满足 $2x \leq a_i$ 的都可以放置了。因此可以假装先按照某种顺序放到了后面的位置(具体是哪些位置不确定,但是排列顺序要考虑)。

这个做法用到了先处理限制较紧的物品的思想。

设 $lim_i$ 表示有多少个数满足 $2x \leq a_i$。

因此设 $f_{i}$ 表示最大值为 $a_i$ 的方案数,不需要记长度是因为长度一定等于 $lim_1+1$。

则有转移:

$$f_{i} = \sum_{j=0}^{lim_i}\binom{n-2-lim_j}{lim_i-lim_j-1} (lim_i-lim_j-1)!f_j$$。

G

模板题,支持单点修改,求 $\text{AC}$ 自动机或者后缀树到根节点的最大值。

建出自动机之后直接树剖线段树维护,注意修改的是某个编号的权值,而可能有不同编号的人重名,因此要用 std::multiset维护每个点的最大值。