[套题记录]AGC 054
command_block
·
·
个人记录
A Remove Substrings
题意 ： 给出字符串 S ，每次可以删除一个首尾不同的子串，求删空 S 所需的最小步数，或指出无解。
------------
考虑 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)。
评测记录
E ZigZag Break
好家伙，三个排列计数！
题意 ： 给出 n,a ，求满足下列条件的排列 P 的个数 ：
多组询问， T\leq 5\times 10^5,n\leq 10^6。
不失一般性，设 P_1<P_n。（否则将值域翻转）
先考虑如何判定一个排列是否满足要求。