M_sea

Educational Codeforces Round 69 题解
比赛地址我真的什么都不会了嘤嘤嘤DIY Wooden Ladder语文题设次大的 $a$ 为 $x$ 。那么显然答...
扫描右侧二维码阅读全文
02
2019/08

Educational Codeforces Round 69 题解

比赛地址

我真的什么都不会了嘤嘤嘤

DIY Wooden Ladder

语文题

设次大的 $a$ 为 $x$ 。

那么显然答案为 $\min\left\{n-2,x-1\right\}$ 。

代码

Pillars

从大到小考虑所有盘子,如果它到最大的那个盘子中没有比它小的就可以移过去。

写一个 ST 表 / 线段树 / 平衡树 / 分块 / …… 求区间最小值即可。

代码

Array Splitting

假设分成两段 $[1,x]$ 和 $[x+1,n]$ ,那么和为 $a_n-a_{x+1}+a_x-a_1=(a_n-a_1)-(a_{x+1}-a_x)$ 。

也就是说,每把 $x$ 和 $x+1$ 分成两段,答案就在 $a_n-a_1$ 的基础上减小 $a_{x+1}-a_x$ 。

那么只要选最大的那些就好了。

代码

Yet Another Subarray Problem

假设选的左端点是 $l$ ,那么我们把 $a_l,a_{l+m},a_{l+2m},\cdots$ 全部减去 $k$ ,那么权值就变成 $\displaystyle\sum_{i=l}^ra_i$ 了。

进一步发现,对于所有 $\bmod m$ 相同的 $l$ ,要减去 $k$ 的 $a$ 都是一样的。

于是枚举 $l\bmod m$ 的值,然后把对应位置的 $a$ 减去 $k$ ,再枚举左端点找到一个最大的右端点即可。

至于怎么找最大的右端点:维护前缀和 $sum$ 和 $sum$ 的后缀最大值 $max$ ,那么左端点为 $l$ 时的最大权值就是 $max_l-sum_{l-1}$ 。

代码

Culture Code

考虑这样一个图:

  • 对于一对套娃 $(i,j)$ ,如果 $out_i\leq in_j$ ,那么从 $i$ 向 $j$ 连边权为 $in_j-out_i$ 的边。
  • 对于每个套娃,从 $0$ 向 $i$ 连边权为 $in_i$ 的边。

可以发现这样子问题就转化成了最短路计数。因为是 DAG ,所以直接拓扑排序计算即可。

然而这样子边数是 $O(n^2)$ 级别的,考虑优化。

  • 套娃 $i-1$ 向套娃 $i$ 连边权为 $in_i-in_{i-1}$ 的边。特别的,$0$ 要向 $1$ 连边权 $in_1$ 的边。
  • 对于一个套娃 $i$ ,找到最小的 $in_j$ 使得 $in_j\geq out_i$ ,然后从 $i$ 向 $j$ 连边权 $in_j-out_i$ 的边。这个 $j$ 可以把所有套娃排序后二分找。

PS:感觉这个优化的建图好妙啊,反正我是想不出来

然后还是最短路计数即可。注意最后算答案的时候只能算那些无法被套住的套娃。

代码

Coloring Game

咕咕咕。

最后修改:2019 年 08 月 02 日 08 : 50 PM

发表评论