[套题记录]AGC 054

# A Remove Substrings **题意** ： 给出字符串 $S$ ，每次可以删除一个首尾不同的子串，求删空 $S$ 所需的最小步数，或指出无解。 $|S|\leq 10^5$ ，字符集为小写英文字母。 ------------ 考虑 DP。记 $f[i]$ 表示将 $S[1,i]$ 删除所需的最小步数。 则有转移 ： $$f[i]=1+\min_{j=1}^{i-1}\big[S[i]\neq S[j]\big]f[j-1]$$ 我们按照 $S[j]$ 将 $f[j-1]$ 分类，用桶优化转移，即可做到 $O(n\Sigma)$。 [评测记录](https://atcoder.jp/contests/agc054/submissions/23823780) # B Greedy Division **题意** ： 给出序列 $A_{1\sim n}$。用一个排列 $P$ 将序列 $A$ 打乱。 接下来，有两个变量 $c_1,c_2$ ，初始时为 $0$。 逐个考虑 $i=1\sim n$ ，若 $c_1\leq c_2$ ，则 $c_1$ 加上 $A_i$ ，否则 $c_2$ 加上 $A_i$。 求有多少个排列 $P$ ，使得最终 $c_1=c_2$。答案对 $998244353$ 取模。 $n,A_i\leq 100$。 ------------ 将 $A_{1\sim n}$ 分成两个和相同的集合 $S_1,S_2$ 。钦定 $c_1\leftarrow S_1,\ c_2\leftarrow S_2$ 。 将这两个集合内部的顺序任意打乱，然后考虑它们归并的方案数。 不难发现，由于贪心的决策是确定的，归并的方案数是唯一的。 于是，方案数为 $|S_1|!|S_2|!$。 接下来用 DP 求出划分集合的方案数。记 $f[i][j]$ 表示选了 $i$ 个数和为 $j$ 的方案数。 记 $S=\sum A_{1\sim n}$ ，则答案为 ： $${\rm Ans}=\sum\limits_{i=0}^nf[i][S/2]i!(n-i)!$$ 复杂度为 $O(n^3A)$。 [评测记录](https://atcoder.jp/contests/agc054/submissions/23826226) # C Roughly Sorted 看错题了！！！rating 乃身外之物！!1 **题意** ： 给定参数 $k$ 。 对于一个长为 $n$ 的排列 $P$，若满足下列条件，称之为好的。 - $\forall i\in[1,n]$ ，使得 $1\leq j<i$ 且 $P_j>P_i$ 的 $j$ 的个数 $\leq k$。 对于排列 $P$ ，要用最少次数的**相邻**交换将 $P$ 调整为好的。 现在我们知道了调整后的结果 $P'$ ，问原来的 $P$ 有多少种可能？答案对 $998244353$ 取模。 $n\leq 5000$ ------------ 这是一个经典的反映射计数问题，先考虑正映射。 记 $c_i$ 为 $P_i$ 前面 $>P_i$ 的数的个数。那么，$P_i$ 至少要参与 $\max(c_i-k,0)$ 次向前的交换。 - 存在如下策略使得交换次数达到下界 $\sum\limits_{i=1}^n\max(c_i-k,0)$。 **策略** ：不断找出 $c_i>k$ 且 $P_{i-1}>P_i$ 的 $i$ ，将 $p_{i-1},p_i$ 交换。 **正确性证明** ： 只需证当存在 $c_j>k$ 时，也存在 $i$ 使得 $c_i>k,\ P_{i-1}>P_i$。 考虑所有的后缀最小值，当存在 $c_j>k$ 时，一定存在一个后缀最小值 $P_i$ 满足 $c_i>k$。 找出一个 $i$ 使得 $P_i$ 是后缀最小值，但 $P_{i-1}$ 不是（如果找不出，则说明 $P$ 已排序），则必然满足 $P_{i-1}>P_i$。 - **结论** ： 该策略得到的排列是唯一的。 **证明** ： 观察上面的策略，不难发现后缀最小值只会变为原来的超集（以数值而言），而不会减少。 因此，后缀最小值向前移动时，不会互相越过。每个后缀最小值的移动都是独立的。 所以，如果移动步数确定的话，最终得到的结果也是确定的。 接下来解决原问题。 对给出的 $P'$ 求出 $c$ ，若 $c_i=k$ 则说明 $P_i'$ 有可能参与过向前的交换，若 $c_i<k$ ，则说明 $P_i'$ 不参与向前的交换。 对于每个可能移动的 $P_i$ ，其原来的位置可能是 $\geq i$ 的任何一个。 记 $T=\{i:c_i=k\}$ ，从大到小考虑 $T_i$ ，原来的位置有 $n-T_i+1$ 种方案，答案为 ： $${\rm Ans}=\prod_{i=1}^{|T|}(n-T_i+1)$$ 复杂度 $O(n\log n)$。 [评测记录](https://atcoder.jp/contests/agc054/submissions/23834582) # E ZigZag Break 好家伙，三个排列计数！ **题意** ： 给出 $n,a$ ，求满足下列条件的排列 $P$ 的个数 ： - $|P|=n,\ P_1=a$ - 每次可以消去连续三个数中的最大值或最小值，能将排列消剩 $P_1,P_n$。 多组询问， $T\leq 5\times 10^5,n\leq 10^6$。 ------------ 不失一般性，设 $P_1<P_n$。（否则将值域翻转） 先考虑如何判定一个排列是否满足要求。