Logo kal0rona的博客

博客

「FZOI」OI 周赛 #1 Div.1 - 题解

2019-12-10 12:34:39 By kal0rona

致歉

由于准备的比较仓促,所以这次周赛组题上出现了一些问题,并对受影响的选手表示道歉。

题解

A - 回旋旅行

显然是一个 Hamilton 路径,设置状态$dp[stat][j]$来进行转移即可。

B - 模拟赛水题

这道题的原题是 CF1257E。考虑对于当前三个序列的每一个序列都在值域上做一个前缀和,记为$prefix_1[i], prefix_2[i], prefix_3[i]$。考虑枚举值域上的两个断点$i, j$,那么操作次数则为:$prefix_1[n] - prefix_1[i] + prefix_3[j] + prefix_2[i] + prefix_2[n] - prefix_2[j]$。这样做$\Theta(n^2)$次,取最小值即可拿到答案,可以得到 60 分。

那么正解是啥?我们发现式子中有两项可以放在一起来算:$prefix_3[j] - prefix_2[j], i < j$。我们只要考虑让这个部分最小即可让当前选中$i$的决策下值最小。做个后缀最小值即可。

C - 彩灯

这道题的出题人为长沙市雅礼中学的 Wearry。以下是他的原题解:


子区间之间只有相互包含和不交的关系,因此它们的包含关系会构成一棵树。

首先考虑一个暴力的解法, 记 $f[i][j]$ 表示在 $i$ 为根的子树中点被覆盖的最多次数为 $j$ 的最优答案, 转移的时候首先将所有子树的答案直接合并,然后考虑点 $i$ 的贡献:

$$ f[i][j] = \max\{f[i][j], f[i][j-1] + a[i]\} $$

不难发现可以维护 $f[i]$ 的差分表, 则 $f[i]$ 的差分表一定单调, 则合并子树相当于将差分表对应相加, 点 $i$ 的贡献则相当于将 $a[i]$ 按照大小顺序插入差分表。

评论

暂无评论

发表评论

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