CF1411E Poman Numbers 题解

十分神秘的题。考虑到对于给定的字符串 $s$ 完全可以将其映射到一个新的序列 $a$，满足 $a_i=2^{\text{pos}(s_i)}$。然后就是找寻一组 $o$ 满足 $\sum\limits_{i=1}^no_ia_i=T$ 且 $o$ 满足题目中给出的构造。因此此时只需要考虑哪些构造是合法的。

仔细观察 $f$ 函数可以发现：其实对于 $f_{[l,r]}$，可以在 $[l,r)$ 区间中选择一个整数 $m$，然后将区间 $[l,m]$ 中所有的 $o_i$ 符号取反（初始时 $\forall i,o_i=1$）。因此容易观察到对于序列的最后一个元素 $o_n$，显然不论区间 $[l,r]$ 怎样选择（需要保证 $1\le l<r\le n$），都无法选取 $m$ 使得 $m=n$。因此必有 $o_n=1$。

然而显然不只这一个特殊的限制条件。容易观察到，$n-1$ 位置想要被取到，当且仅当 $r=n$ 的时候选取 $m=n-1$。之后有 $r=n-1$，$m=n-1$ 将再也不会被选择。因此 $m=n-1$ 的情况必恰好被取反一次，必有 $o_{n-1}=-1$。

此时可以发现对于 $[1,n-2]$ 中的任何数 $i$，$o_i$ 都可以任取 $\lbrace 1,-1\rbrace$。然后考虑反悔贪心一开始 $[1,n-2]$ 全部选择 $1$，每一次选择最大的可以选的数贪心的将其的 $o_i$ 变为 $-1$ 即可。时间复杂度为 $O(n\log n)$ 可以通过。