AGC028

Scintilla · 2022-10-25 08:23:34 · 个人记录

cnblogs

A (\texttt{Easy} \ 2 / 0)

答案只有可能为 \text{lcm}(n, m) 或 -1，直接枚举同时出现的位置并判断即可。

B (\texttt{Easy} \ 2 / 0)

一个区间 [l, r] 在方案中出现当且仅当 l - 1, r + 1 出现在 [l, r] 中任意数之前，所以包含它的方案数即

\frac{n!}{\binom{r - l + 3}{2}}

发现这只与长度有关，于是枚举长度并计算即可，注意特判 l = 1 或 r = n 的情况。

时间复杂度 \mathcal{O}(n)。

C (\texttt{Easy} \ 3 / 1)

降智了很久。

首先把 \min 变为钦定任意一个数，则最小值不变，而简化了计算总和的过程。对于每个点，考虑其 a, b 是否被钦定，共有四种状态，用 00, 01, 10, 11 表示。下面考虑怎样的钦定方案是合法的。发现如果存在 11, 00（它们成对出现）的话可以先把所有的 01 和 10 消掉，然后自己消；如果不存在的话，10 和 01 是无法操作的。可以发现合法的钦定方案包括两种情况：

存在 11, 00。
全部为 10 或全部为 01。

第二种情况是容易的。对于第一种情况，我们不妨考虑最小值的下界：所有的 a, b 中前 n 小数之和。如果其中存在 11, 00 则其就是答案；否则前 n 个数中每个位置都恰有一个，分类讨论：

若第 n + 1 个数的位置和第 n 个数的位置不一样，则答案为前 n - 1 个数和第 n + 1 个数之和。
否则，第 n - 1 个数和第 n + 1 个数位置不一样、第 n 个数和第 n + 2 个数的位置也不一样，取差较小的那一对替换即可。

时间复杂度 \mathcal{O}(n \log n)。

D (\texttt{Easy} \ 3 / 3)

~~很久以前做看了题解，差不多忘了但是现在胡出来了系列。~~

设 f_{l, r} 表示 [l, r] 最小值、最大值分别为 l, r 的连通块的方案数，转移的话，如果存在一条从 [l, r] 内的点连向 [l, r] 外的被钦定的边显然就是 0；否则考虑容斥，不满足条件的情况枚举 l 所在连通块的编号最大值，再处理一下已经钦定的边的情况即可。具体地，2n 个点配对的方案数是 (2n - 1)!! = \prod_{i = 1} ^ n (2i - 1)，如果 l 所在连通块的编号最大值为 p，那么右边的点和区间外的点未被钦定的任意配对即可。

时间复杂度 \mathcal{O}(n^3)。

E (\texttt{Hard} \ 7 / 3)

非常厉害的贪心题。

我们考虑逐位决定，问题转化为一个前缀已经划分好了，判定剩下的数是否存在一种划分方案满足要求。

我们称原序列中的前缀最大值为「大的」，其余数为「小的」，则有如下结论：

若存在满足条件的划分方案，则必然存在一种方案，使得 X 和 Y 中至少存在一个序列，使得剩下的数中被划分到该序列并在这个序列中作为前缀最大值的数全部是大的。

证明：考虑反证法。假设结论不成立，则对于任意一种方案，选取剩下的小的数中被划分到 X, Y 并作为前缀最大值的数各一个，记作 x, y，则把 x 放到 Y 中，并把 y 放到 X 中，不难发现二者都不再是前缀最大值了，所以两个序列的前缀最大值个数都减少了 1，依然相等。一直调整下去，可以得到一种满足结论的方案。

不妨假设 X 中的前缀最大值都是大的。假设当前 X 中有 c_x 的前缀最大值、Y 中有 c_y 个前缀最大值；还剩下 t 个大的数，其中 x 个被分到了 Y，t - x 个被分到了 X；Y 中还有 y 个小的前缀最大值，我们有等式

c_x + t - x = c_y + x + y

移项可得

c_x + t - c_y = 2x + y

左边的数是确定的；右边的 2x + y 只与我们钦定放在 Y 中的前缀最大值有关。我们把大的数的权值赋为 2、小的数的权值赋为 1，如果我们找到了一个能接在 Y 后的上升子序列，使得其权值和为 c_x + t - c_y，不难发现存在一种剩下的数的分配方案，使得 X 中的前缀最大值全部是大的，所以当前的状态就能构造出一组解。

于是我们把问题转为了如下形式：

有一个排列，每个点的权值为 1 或 2，每次询问一个后缀中能否找出首项 > k 并且权值和为 s 的递增子序列。询问的后缀长度递减。

发现存在权值和为 x \ge 2 的递增子序列，则必然存在权值和为 x - 2 的递增子序列，所以我们只需要知道权值和为奇数 / 偶数时的最大值即可。

这个可以 dp 解决，dp 的过程可以用线段树优化，这部分并不难，不再赘述。

总的时间复杂度是 \mathcal{O}(n \log n)。

F (\texttt{Medium} \ 6 / 2)

不知道怎么想到的，F2 不会，\mathcal{O}(n^3) 的代码艹过去的。

我们首先维护出 L_{i, j, k}, R_{i, j, k} 表示从 (i, j) 能走到第 k 行的最小位置和最大位置，并维护每一行的前缀和。但是我们并不能根据这些计算答案，因为 L, R 之间的所有数字并不一定全部能够走到。

怎么办呢？我们从下往上、从右往左地计算答案，每次计算完一个点，如果它的左边和上边都不是数字，就意味着它不可能再被计算了，可以直接删去它并更新前缀和。删去之后可能会出现新的点满足左边和上边都不是数字，递归删除即可。这样我们在计算一个点的答案时，L, R 之间的数都是可以走到的了。

时间复杂度 \mathcal{O}(n^3)。

以下是 F2 的一些卡常技巧：

大部分数组，例如 L, R 还有存储前缀和的数组，都可以开成 short。
递归删除的过程写手工栈。注意栈的大小超过了 short 的范围。
如果 (i, j) 并不能走到第 k 行，就可以直接 break 掉了。
交换前缀和数组的两维，使得内存访问连续。

使用这四个技巧之后可以卡到 8232 毫秒。