Qingyu的博客

博客

Public NOIP Round #4 题解

2022-11-20 15:28:33 By Qingyu
  • 搬题人:
    • 咖啡, 画图:Qingyu
    • 治病, 拓扑序计数:feecle6418
    • 序列:Wu_Ren
    • 水果:p_b_p_b
  • 组题人:Qingyu
  • 题解:alpha1022, feecle6418, Wu_Ren, p_b_p_b

咖啡 (Div. 2 Only)

来源:

Tutorial by alpha1022.

不妨采用贪心策略:能喝则喝。

从左往右扫描,维护当前手中有几杯咖啡即可。

画图 (Div. 2 Only)

来源:

Tutorial by alpha1022.

采用深度优先搜索或广度优先搜索得出 $(x,y)$ 所在的连通块并染色即可,需要保证每个格子不被重复访问。

治病 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

首先我们要算出,如果不忽略任何医生,尼特花费的钱数。根据题意我们知道,对于某种药片,尼特吃这种药片的时间就是所有医生药方里的时间的并集,也就是给出一些区间让你求并。这是经典问题,按照左端点从小到大排序,维护当前最大的右端点即可。

如果忽略某个医生,只需要找到只被这一个医生覆盖的 (药片,时间) 二元组,把这些二元组的贡献减掉。对每种药片分开考虑,也就是对每个区间,求出只被这一个区间覆盖的位置的总长度。首先用差分求出每个位置被覆盖了多少次,找出只被覆盖一次的位置,把这些位置的权值赋值成 1,对权值做前缀和,然后求出每个区间内的位置的权值之和,就是只被这一个区间覆盖的位置的总长度。

所有差分、前缀和都需要在离散化之后的坐标上进行,瓶颈在于离散化,总时间复杂度为 $O((\sum K)\log (\sum K)+n+m)$。

拓扑序计数 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

设 $f(S)$ 表示按照拓扑序从前往后的顺序加点,初始为空集,到已经加入 $S$ 这个点集,这一段的加点方案数。设 $g(S)$ 表示按照拓扑序从后往前的顺序删点,初始为全集,到现在还剩下 $S$ 这个点集,此时删除顺序的方案数。$f,g$ 都可以在 $O(2^nn)$ 时间内简单地 dp 求出。

对于给定的 $u,v$,$u$ 在 $v$ 前,就是要,拓扑序加入 $v$ 那一刻,$u$ 已经在拓扑序里了。所以,$ans_{u,v}=\sum [u\in S,v\notin S]f(S)g(S\cup \{v\})$(枚举加入 $v$ 之前一刻,有哪些点加入了拓扑序)

直接实现该算法的时间复杂度为 $O(2^nn^2)$,但 $S$ 的枚举有 $1/4$ 的常数,已经可以过。

当然,上述算法还可以继续优化到 $O(2^nn)$:枚举 $S,v$,相当于 $\forall u\in S$,$ans_{u,v}$ 都加上一个定值。因此瓶颈在于:“给出 $a_{0}\sim a_{2^n-1}$,对所有 $u$ 求出 $\sum_{u\in S}a_S$”。可以用下面的方法:

for i from n-1 downto 0:
    for j from 2^i to (2^{i+1}-1):
        ans[i]+=a[j]
        a[j-2^i]+=a[j]

最后 $ans_u$ 就是答案。因此我们把 $O(2^nn)$ 的循环优化到了 $O(2^n)$。(但是实际上速度仅仅变快了不到一倍)

序列 (Div. 1 Only)

来源:

Tutorial by Wu_Ren.

由于答案有可二分性,直接获得 $O(nm\log n)$ 做法。

下面是正解:

考虑每次建出小根笛卡尔树,并且在笛卡尔树上 dp

我们对于每个节点,维护子树内 $a_i$ 最大值 $mx$,区间长度 $sz$,最长合法子段长度 $len$。

假设 $u$ 的两个儿子为 $lc,rc$,那么考虑合并 $lc,rc$ 的信息来得到 $u$ 的信息。

$mx,sz$ 的合并是显然的。考虑 $len$ 的合并,首先,假如合法子段不经过 $u$,那么就是 $len_u\leftarrow \max(len_{lc},len_{rc})$。假设存在 $u\in[l,r]$ 使得 $[l,r]$ 是合法子段,那么假设 $\max\limits_{i\in[l,u-1]} \{a_i\}\ge \max\limits_{i\in[u+1,r]} \{a_i\}$,此时我们可以发现,如果 $l>u-sz_{lc}\land r>u$,那么 $[l-1,r-1]$ 也是合法的。

那么就可以知道,我们可以认为跨越 $u$ 的合法子段要么一个端点是 $u$,要么一个端点是 $u-sz_{lc}$ 或 $u+sz_{rc}$。

这里可以发现,假如 $[l,u]$ 是合法子段且 $l>u-sz_{lc}$,那么 $[l-1,u-1]$ 也是合法子段,所以说一个端点是 $u$ 且另一个端点不是 $u-sz_{lc}$ 或 $u+sz_{rc}$ 的情况一定不优于 $\max(len_{lc},len_{rc})$。

那么我们只需要考虑一个端点在 $u-sz_{lc}$ 或 $u+sz_{rc}$,并且过 $u$ 的情况了(也就是说,我们只需要考虑至少把一颗子树完全包含的情况),这个转移是显然的。

复杂度 $O(nm)$。

水果 (Div. 1 Only)

来源:

Tutorial by p_b_p_b.

为了方便,先把 $a_i\ne -1$ 且无论如何都无法成为前缀最大值的水果删掉。

为了方便,再把水果的美味度修改一下,使得没有确定位置的水果的美味度是 $1,2,\cdots,m$ ,而确定位置的水果的美味度则是夹在中间的小数。

设 $a_1,\cdots,a_n$ 是读入的方案,$A_1,\cdots,A_n$ 是最终的方案。

放弃思考,直接设 $dp_{x,v}$ 表示确定了 $A_1,\cdots,A_x$ ,且其中最大值小于 $v+0.99$ ($v$ 是整数),考虑如何转移。

  • 如果 $a_x\ne -1$ ,那么有两种选择
    • 让 $a_x$ 成为最终的前缀最大值,那么从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移。
    • 扔掉 $a_x$ ,从 $dp_{x-1,v}$ 转移。
  • 如果 $a_x=-1$ ,再分两种
    • $a_1,\cdots,a_{x-1}$ 的最大值小于 $v$ ,那么这里肯定应该贪心放 $v$ ,从 $dp_{x-1,v-1}+c_v$ 转移。
    • 否则这里只能被迫开摆,随便放个以后不用的小的,从 $dp_{x-1,v}$ 转移。(注意因为我们做过预处理,所以这里总是可以保证不超过 $v$ 。)

于是就获得了一个非常垃圾 $O(n^2)$ 做法,下面考虑优化。

  • 对于 $a_x\ne -1$ ,注意到 $dp_{x,0},\cdots,dp_{x,m}$ 单调不降,因此一定是一个前缀从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移,而其他地方直接把 $dp_{x-1,v}$ 拉过来。因此只要二分分界点就可以直接前缀赋值。
  • 对于 $a_x=-1$ ,显然只有一个合法状态会从 $dp_{x-1,v}$ 转移,剩下的都从 $dp_{x-1,v-1}+c_v$ 转移。不过这个怎么维护呢?

设 $S_i=\sum_{j=1}^i c_j$ 表示 $c$ 的前缀和。另外设 $pre_x$ 表示 $a_1,\cdots,a_x$ 有几个 $-1$ 。

对每个 $dp_{x,v}$ 维护一个二元组 $f_{x,v}=(x',y)$ ,表示 $dp_{x,v}=S_v-S_{v-(pre_x-x')}+y$ ,那么就做完了:从 $dp_{x-1,v-1}+c_v$ 转移,就等价于 $f_{x,v}=f_{x-1,v-1}$ 。而其他转移也都是简单的单点或区间赋值。

暴力线段树就能维护了。还可以再好看一点,用双端队列来维护二元组的连续段,但其实区别不大。

评论

wang_9_sing
今晚九点,王浩清唱歌,大家不见不散。/qiang/qiang/qiang
  • 2022-11-22 13:06:49
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。