积云不解下弦月

AGC062

[AGC062A]Right Side Character

咋这么难？
不难打标看出结论：当且仅当一个前缀是 \(A\) ，一个非空后缀是 \(B\) 时答案是 \(B\) 。

[AGC062B] Split and Insert

VP 时的思路。

首先考虑倒着，每次选择一个子序列放到最后，方便起见我们把操作序列也 reverse 一下。

这样，我们发现，如果设 \(S_i\) 为覆盖了 \(i\) 的操作集合（我们把 \(S_i\) 默认为降序排列），那么最终 \(S_i\) 相同的一定是在一起的，这样会形成若干个区间，并且这些区间的 \(S_i\) 按照字典序从小到达排列。

此时唯一的限制就是：每个 \(S_i\) 相同的区间内的数在 \(p\) 中的位置递增。

设 \(M\) 为不同的 \(S_i\) 个数，考虑 dp，设 \(f_{i,j}\) 表示考虑了前 \(i\) 个位置，当前位置的操作集合是 按字典序排序的 第 \(j\) 个的最小代价，转移时可以维护前缀 \(\min\) 做到 \(O(nM)\)。

但是我们发现 \(M=2^k\) 根本开不下，考虑优化一下。

注意到最终用到的只有 \(O(n)\) 个区间，那么我们考虑贪心的保留权值和最小的 \(n\) 个 \(S_i\)，这个可以用类似超级钢琴的思路求出来。

然后叫了一下发现 WA 了，再想想发现有可能一段长度很长的区间，我们想要让他取到尽可能小的权值和，但是有字典序的限制所以有可能取不到这个数，此时应该在前面 “垫” 一些段，故不一定是最小的 \(n\) 个有用。

此时我们充分发挥人类智慧，保留最小的 \(pn\) 个 \(S_i\)，实测 \(p=3\) 能过。

复杂度 \(O(n^2m+nm)\) ，跑的飞快。

虽然是个假做法但是复杂度比题解要优。

[AGC062C] Mex of Subset Sum

从小到大排序，设前缀何为 \(S_i\)，所有 \(x<S_i\) 且不能被前 \(i\) 个数表示出来的数的集合为 \(E_i\) 。

考虑从 \(E_{i-1}\) 推到 \(E_i\) ：

首先，一个数 \(x\) 不能被表示出来，当且仅当 \(x\) 不能被前 \(i-1\) 个数表示出来，且 \(x-A_i\) 不能被前 \(i-1\) 个数表示出来，这里的不能被表示有三种：\(<0,\in E_{i-1},>S_{i-1}\) 。

我们简单讨论一下：

• \(S_{i-1}<A_i\) ，此时 \(S_{i-1}\) 内的数和 \((S_{i-1,A_i})\) 内的数都不能被表示，并且因为 \(A_i\) 不降，之后也一定不能被表示，且一定不会有更小的不能被表示的数，所以这些数一定在答案里，如果他们个数 \(\geq K\) 就直接输出。否则，就把 \(x-A_i\) 必须 \(\in E_{i-1}\)，把这些数加进来就好了，可以发现与 \(E_{i-1}\) 相比，\(E_i\) 大小最多多 \(K-1\) 。
• \(S_{i-1}\geq A_i\)，那么 \(E_{i-1}\) 中 \(<A_i\) 的部分一定也是一定在答案里的，和上面一样处理。否则对于 \((A_i,S_{i-1})\) 中的数，只有 \(x\in E_{i-1},x-A_i\in E_{i-1}\) 才行，对于 \((S_{i-1},S_i)\) 中的数也要求 \(x-A_i\in E_{i-1}\)，可以发现加进来的数大小也不超过 \(E_{i-1}\) 。

综上 \(E_i\) 的大小不会超过 \(Ki\)，暴力做复杂度就是对的了。

[AGC062D] Walk Around Neighborhood

神秘思维题，感觉有点像是二维的摩尔投票。

我们先从小到大排序，如果前 \(n-1\) 个数的和 \(<a_n\) 一定无解，因为 \(a_n\) 不管咋走都会超。

否则，一定有解，并且答案一定在 \([\frac{a_n}{2},a_n]\) 中，这是因为：上界 \(a_n\) 的构造很简单，我们先走到 \(a_n\) 所在的正方形上，然后剩下的步长一定与这个正方形都有交，因此我们能一直保持在边界上，最后用 \(a_n\) 走回去就好了。下界 \(\frac{a_n}{2}\) 也是因为小于这个，\(a_n\) 不管咋走都会出去。

那么我们枚举答案 \(r\in [\frac{a_n}{2},a_n]\) ，注意到我们走的过程形如：

• 先用若干步数走到 \(r\) 的正方形上
• 中间一些步数在正方形边界上跳
• 再用一些步数走回去

并且因为 \(r\in [\frac{a_n}{2},a_n]\) 所以只要能走到边界上就一定能保持在边界上，所以我们只需要找两个集合，满足一个集合能走过去，一个集合能走回来就行了。

判断一个集合 \(S\) 能否走到 \(r\) 的正方形边界：

• 若 \(S\) 中小于 \(r\) 的数的和 \(\geq r\)，那么显然一定能走到 \(r\) 。
• 否则，我们一定要用 \(\geq r\) 的数，因为用了它之后一定要么走出去要么走到边界上，所以用一个就够了，记为 \(x\)。考虑什么时候不合法，发现若 \(x\) 很大，\(r\) 很小，我们就很容易跳出去，故 \(x\) 一定保留最小的一个，并且此时可以发现跳 \(x\) 的位置越偏越不容易跳出去，所以我们一定把 \(<r\) 的数沿着同一个方向走，所以记这些数的和为 \(s\)，那么合法的充要条件是 \(s\geq x-r\) 。

因为我们要分成两个集合，并且可以发现如果有 \(\geq r\) 的数一定用比不用好，因为 \(r\in [\frac{a_n}{2},a_n],x-r\leq r\) 更容易满足，并且因为 \(r\leq a_n\)，所以一定至少有一个 \(x\) 可以用，如果还有就再保留次小的，否则就只能选择第一种。

现在我们要找两个集合，第一个大小 \(\geq A\)，第二个 \(\geq B\) ，那么一定每个数都被选进某一个了。

用 bitset 维护可能集合大小，每次 _Find_next 找到 \(\geq A\) 的最小的子集，然后判断剩下的数是不是 \(\geq B\) 就行了。

复杂度 \(O(\frac{n^2}{w})\)。

[AGC062F] Preserve Distinct

这是人做的题？

首先，对于第 \(i\) 堆，求出它第一张牌对应的另一张所在的堆，记为 \(p_i\) 。

从 \(i\to p_i\) 连边，形成了一个基环树森林。

首先，环外的点，每次删叶子，显然可以删空，所以现在只有一堆环。

然后，不同连通块是独立的，因为我们可以一个一个删，删的过程中别的显然不影响，如果删完了最好，没删完也说明此时这个环的堆顶的牌一定都只在这个环出现，对别的没有影响。

因此我们可以一个一个环处理，我们按照环的顺序记为 \(1,2,3\cdots k\) ，第 \(i\) 堆堆顶的牌是 \(a_i\) 。

那么这些牌一定形如：

• \(1:a_1\cdots a_{k}\cdots\)
• \(2:a_2\cdots a_2\cdots\)
• \(\cdots\)
• \(k:a_k\cdots a_{k-1}\cdots\)

先讨论一些简单的情况，看能不能得到一些性质：