题解 AT2346 【[ARC070B] No Need】

Achtoria · 2021-02-09 17:11:20 · 题解

这里介绍几种做法。

解法一

首先可以转化一下题意，\forall i 如果 i 不是可有可无的当且仅当不用 i 能拼出 [K - a_i, K) 中的数。

基于观察可以发现，对于 \forall i 如果 i 不是可有可无的，那么 \forall j, a_j \ge a_i 都不是可有可无的，证明如下：

取出使得对于 i 能拼出 [K - a_i, K) 中一个数的集合 S，分以下两种情况讨论：

• 若 j \in S，考虑用 a_i 替换 a_j 使得对于 j 合法。

则可知 K - a_i \le |S| \le K \Rightarrow K \le |S| + a_i \le K - a_i

于是有 K - a_j \le |S| + a_i - a_j \le K + a_i - a_j \le K 因此替换是可行的。

• 若 j \notin S 直接使用 S 即可满足 j 的要求。

因此我们先按照 a_i 从小到大排序，可替换的必然是一段前缀，直接二分加背包判断即可，复杂度 O(nk \log n)。

解法二

一个直接的想法在于求出不使用 i 能拼成的数字有哪些。

暴力的做法就是 \forall i 枚举 j \ne i 进行暴力 dp。

但是你会发现有对于一些 i 有很多 j 都是能枚举的，换而言之每一对点对 (i, j)(i < j) 都会在 i, j 上分别用对方 dp 一次。

对于这种点对对答案的贡献问题，经常可以考虑使用 \rm CDQ 分治解决。

那么我们在分治 [l, r] 这个区间时可以发现，[l, mid] 内的所有数会对 [mid + 1, r] 内所有数的 dp 数组造成贡献。

因此我们直接考虑枚举左区间的每个数 i 让其在右区间恰好 dp 一次，对于右区间同理。

那么分治下去的时候就要同时将整个区间的 dp 数组传递下去，不难发现这样的复杂度实际上只枚举了 n \log n 个点，因此复杂度是 O(nk \log n) 的。

解法三

注意到我们要求的实质上是去除掉 i 以后的 dp 数组，不难让我们想起了 消失之物 这题的退背包做法。

但是本题的 dp 是判定性的，不存在可加性，怎么办呢？

不难发现只需要改写 dp 状态让其满足可加性即可，即我们将存储的值由是否可行变为方案数。

那么一个数不能被拼出来当且仅当方案数为 0。

于是先 dp 出总方案数，然后从左至右做退背包即可。

由于方案数过大，需要取模，复杂度 O(nk)。

解法四

考虑另一个暴力合并 dp 数组的做法，先记录 pre, suf 两个前缀/后缀 dp 数组。