Right Side Character
记\(n=|s|\)，观察到以下两个性质：
-
若\(s_{n}=A\)，则\(f(s)_{n-1}=A\)，进而答案为\(A\)
-
若\(s_{n}=B\)且\(\exists i\in [2,n],s_{i-1}s_{i}=BA\)，则\(\exists i\in [2,n),f(s)_{i-1}f(s)_{i}=BA\)
由于最终必然不存在，中间即存在某步使得\(f(s)_{n-1}=A\)
综上，答案为\(B\)的必要条件\(s_{n}=B\)且\(\forall i\in [2,n],s_{i-1}s_{i}\ne BA\)，且显然充分
简单判定即可，时间复杂度为\(O(n)\)
Split and Insert
考虑将过程逆序，即对于给定的\(\{P_{n}\}\)，每次将\(k\)个数放到末尾，最终使得\(P_{i}=i\)
注意到两数的位置关系取决于最后一次恰选择其中一项的操作（若不存在即与初始相同）
记\(Q_{P_{i}}=i,S_{i}\)为表示\(i\)操作情况的\(K\)位二进制数，则即要求\(\forall i\in [1,n),(S_{i},Q_{i})<(S_{i+1},Q_{i+1})\)
定义\(f_{l,r,i}\)表示区间\([l,r]\)仅用\(i\)次操作的答案，则
\[\begin{cases}f_{l,r,0}=[Q_{l}<Q_{l+1}<...<Q_{r}]\\f_{l,r,i}=\min\{f_{l,r,i-1},\min_{j\in [l,r)}f_{l,j,i-1}+f_{j+1,r,i-1}+(r-j)c_{K-i+1}\}\end{cases} \]暴力实现即可，时间复杂度为\(O(n^{3}K)\)
Mex of Subset Sum
不妨假设\(a_{1}\le a_{2}\le ...\le a_{n}\)，并记\(A_{i}=\sum_{j=1}^{i}a_{j}\)
维护\([0,A_{i}]\)中不能被表示的数集合\(T\)，转移即\(T'=\{x\mid (x-a_{i}\in T\or x<a_{i})\and (x\in T \or x>A_{i-1})\}\)
将左半部分的条件拆开，即\(T'=\{x\mid x-a_{i}\in T\and ...\}\cup \{x\mid x<a_{i}\and ...\}\)
（其中\(...\)表示右半部分的条件）
后者若大小\(\ge k\)即可直接得到答案，否则即\(|T'|<|T|+k\)，进而\(|T|\le nk\)
用set暴力实现即可，时间复杂度为\(O(n^{2}k\log nk)\)
Walk Around Neighborhood
参考这里
Overlap Binary Tree
参考这里
Preserve Distinct
咕咕咕
标签：...,le,BA,复杂度,mid,即可,AGC062 From： https://www.cnblogs.com/PYWBKTDA/p/17520360.html