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
维护每个点的最大值。