AtCoder ARC100 四题题解

花了够长时间终于把这四题搞完了。其实前三题也就写了 2h (虽然中间横跨一周多),最后一题水平太低,写了 3h 多……

直接放题解

C | Linear Approximation

容易发现取中位数是对的,证明 ez ,考虑将 b 的取点左右移动直到跨过一些点,然后对比总和的变化。

D | Equal Cut

orz Leader One

队友切掉的。

要是切两刀大概是 sb 题,三刀就有些微妙。

解法只能向特殊的方向考虑,考虑一个 \mathcal{O}(n \log n) 的做法:

枚举中间的那刀切在哪里,之后显然将左右两半各自(尽可能)平分才是最优的。

于是写个二分就可以了。注意这个「尽可能」带来的坑比较多。

E | Or Plus Max

三个人口胡好久,中道崩殂不会做后半部分,看了题解……

首先考虑如果我们把问题转化为计算 \max {A_i + A_j} \quad \mathrm{where} \quad i \lor j = K   那么最后只需要一发前缀和就可以有答案。

计算这个并不容易,我们考虑 DP。

对于每个值 x ,我们称 y \subseteq x 当且仅当二进制 ory or x == x 。

对于每个 x 我们建立一个集合 S_x 记录 \forall y \subseteq xa_y 的前两大值。

那么就可以轻松的算出 \max\{A_i + A_j\} \quad \mathrm{where} \quad i \lor j = K   。

考虑如何更新 S_x 。其实只要从小到大枚举 x 然后从 y \subseteq x 并且 y 的二进制 1 的个数只比 x1y  更新 S_x 即可。

这样的 DP 转移是完全的,至于为什么可以思考一下。写起来也挺好写。

F | Colorful Sequences

直接抄题解好了,再补充点细节。

这问题正面求确实不好求。于是我们先计算 A 在所有的 S_N (不管是不是 Colorful)中出现的数量,然后减去非 Colorful 的即可。

然后总数显然是 (N-M+1) \times K^{N-M} ,先算出来。之后的主要矛盾变为计算 A 在所有不多彩的 S_N 中出现的数量。下面的「答案」指的都是这个。

先考虑如果 A 本身是多彩的,那么答案是 0。显然。

如果 A 不是多彩的,有两种情况。我们先来考虑一个基础问题:

计算出长度为 N 的非多彩序列

这个显然可以 DP。我们设 dp[i][j] 是考虑了序列前 i 个位置,最后 j 个位置的值各不相同,但最后 j+1 个位置的值至少有一对相同的序列数。当然,\forall S_i \in S_N \, , \,  1 \leqslant S_i \leqslant K

稍加思考, DP 是这样转移的:

dp[i][j] = dp[i-1][j-1] * (K-j+1) + dp[i-1][j ... K]

后缀和维护一下做到 \mathcal{O}(NK),OK。

那么不多彩的 A 的第一种情况是 A 中无重复元素。这时候只要算出这样的问题即可:

对于每个不多彩的 S_N ,计算这个 S_N 中连续的长为 M 的元素互不重复的子序列数量,之后求和。

这样就将 A 从问题中移去了。但是显然这样会多数,多了恰好 \frac{K!}{(K-M!)} 倍,除掉就可以获得答案了。

那么如何计算呢?方法就类似上面那个 DP,只不过需要稍加修改

就可以顺利算出答案了。

对于第二种情况—— A 中有重复元素,我们计算出 FB 表示起头 F 和结尾 B 个元素是最长不重复的。

之后我们先枚举 AS_N 中的位置,再从两端出发,计算同上一个问题相似的问题(不过 M 换成了 F/B),然后两端乘起来就可以了。

这部分(我能想到的)实现其实挺复杂,具体可以看代码。

以上。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据