ABC 381 D~F

\(D\)

简要题意：给你一个长度为 \(n\) 的序列 \(A\) (\(1\le n\le 10^5,1\le A_i\le n\)) ，你需要找出其最长的满足以下条件的连续子序列 \(a\) 输出它的长度。

1. 长度为偶
2. \(a_{2*i}=a_{2*i-1} / (1\le i \le \frac{len}{2})\)
3. 每个数出现两次。

思路：一个有趣的题，借鉴了暑假一道题的思想，那道题好像是可以将 \(a_i=a_{i+1}\) 合并为 \(a_i+1\)，求最后序列的最大值。其中一步的思想就是如果有连续的 \(3\) 个相同的数连在一起那么两段必然不能连在一起，由于不确定放在哪边，直接两边都放然后中间用分隔符 \(inf\) 隔开即可。
这道题一样，连续两个的直接合并，一个的直接变成 \(inf\)，三个及以上两边都放中间用 \(inf\) 分隔(因为合并后的数在子序列中只能出现一次，所以三个以上直接分隔即可)。(不要忘了序列末放一个 \(inf\))
统计 \(inf\) 之间的段的答案(满足条件的最长子序列的长度)，记录上一个该颜色出现的位置，一定是选到上一个该颜色出现的位置之后一个位置即可(注意边界细节处理)，因为合并后是原始两个数合成一个，所以输出答案 \(*2\) 即可。
时间复杂度 \(O(n)\)。

Code

\(E\)

简要题意：一个长度为 \(n\) 字符串 \(S\)，\(q\) 次询问(\(1\le n,q\le 10^5,S_i\in \{'1','2','/'\}\))，你需要找出 \(S\) 子串 \(S_{L_i}\) ~ \(S_{R_i}\) 中最长的子序列 \(s\) (可以不连续)满足以下条件并输出其长度。

1. 长度为奇。
2. \(s_{\frac{len+1}{2}}='/'\)
3. \(s_i='1'(1\le i\lt \frac{len+1}{2})\)
4. \(s_i='2'(\frac{len+1}{2}\lt i\le len)\)

思路：考虑如果我们对于每一个 \(/\) 该如果快速求解其所产生的答案，定义 \(pre_i\) 表示 \(1\) ~ \(i\) 位 \(S\) 中 \(1\) 的个数，\(suf_i\) 表示 \(i\) ~ \(len\) 位 \(2\) 的数量，显然对于 \(S_i='/'\) 其答案为 \(\min\{pre_{i-1},suf_{i+1}\}*2+1\) 。而 \(S_{L_i}\) ~ \(S_{R_i}\) 中的 \(S_j='/'\) 其答案为 \(\min\{pre_{j-1}-pre_{L_i-1},suf_{j+1}-suf_{R_i+1}\}*2+1\)。因为取 \(\min\)，所以我们希望它们尽可能平均，而 \(pre\) 在区间 \(1\) ~ \(len\) 上单增，而 \(suf\) 在区间 \(1\) ~ \(len\) 上单减，所以它的最值在第一个满足 \(pre_{j-1} \ge suf_{j+1}\) 的 \(j\) 处或最后一个满足 \(pre_{j-1} \le suf_{j+1}\) 的 \(j\) 处取得。二分即可。
时间复杂度 \(O(q\log_2 n)\)。

Code

\(F\)

简要题意：给你一个长度为 \(n\) 的序列 \(A\) (\(1\le n\le 10^5,1\le A_i\le 20\)) ，你需要找出其最长的满足以下条件的子序列 \(a\) (可以不连续)输出它的长度。

1. 长度为偶
2. \(a_{2*i}=a_{2*i-1} / (1\le i \le \frac{len}{2})\)
3. 每个数出现两次。

思路：设 \(m\) 为 \(A_i\) 值的个数，考虑设立 \(dp_{i,S}\) 表示前 \(i\) 位，选取 \(A_i\) 值集合为 \(S\) 的最长长度。
转移方程显然：$$dp_{i,S}=\max_{j=1}^{i}\max_{s=1 \ && \ S&(1<<(s-1))\ne 0}^{m}{[j\lt s_{p1}\lt s_{p2}\le i]*(dp_{j,S \oplus (1<<(s-1))}+2)} (A_{s_{p1}}=A_{s_{p2}}=s)$$
时间复杂度为 \(O(n*m*2^m)\)，空间复杂度为 \(O(n*2^m)\)。
时空复杂度均吃不消，但我们发现有了 \(S\) 这一维，我们可以直接知道答案就是 \(popcount(S)*2\)，因为一个值不能被选两次。
于是我们不需要去记录 \(dp_{i,S}\) 表示前 \(i\) 位，选取 \(A_i\) 值集合为 \(S\) 的最长长度。可以换一种 \(DP\) 方式，将我们的第一维放进储存的值中，变为 \(dp_{S}\) 表示选取 \(A_i\) 值集合为 \(S\) 的末尾最小位数。
而转移方程变为了：$$dp_{S}=\min_{s=1 \ && \ S&(1<<(s-1))\ne 0}^{m}\min_{dp_{S \oplus (1<<(s-1))}\lt s_{p1}\lt s_{p2}\le i \ && A_{s_{p1}}=A_{s_{p2}}=s)}{s_{p2}}$$
第二个 \(\min\) 可以通过记录所有 \(s\) 值在 \(A\) 中出现的位置，二分得到。
时间复杂度 \(O(2^m*m*\log_2 n)\)，空间复杂度 \(O(2^m)\)。

我们尝试感性证明一下后面的 \(DP\) 为什么是正确的，因为我们最终选取的颜色序列一定可以通过 \(DP\) 转移的顺序一个一个的往序列的后面插，所以我们只需要让最后的位置尽量靠前即可。

学习到了一个 \(trick\)，如果 \(DP\) 状态复杂度特别高而值域小，可以尝试将其互换以减少复杂度。

Code