题目内容

小红定义一个字符串的权值为:其长度为3的回文子序列数量。

例如，“$0110$“ 的权值为 $2$ ，因为包含两个回文子序列 "$010$"。

题目描述

小红定义一个字符串的权值为其长度为 3 的回文子序列数量。例如，“0110”的权值为 2，因为包含两个回文子序列“010”。
给定一个长度为 $n$ 的数组 $a$，需要构造一个 01 串 $S$，使得对任意 $1\le i\le n$，$S$ 的前缀长度为 $i$ 时的权值恰好等于 $a_i$。若无解，输出 -1；否则输出任意一个可行解。

解题思路与方法

1. 前缀权值增量公式

记当前已构造前缀长度为 $i-1$ 的串为 $S[1..i-1]$，其权值为 $f_{i-1}=a_{i-1}$。若在位置 $i$ 处添加字符 $b\in\{0,1\}$，则新增的所有长度 3 回文子序列都形如 $b\,x\,b$，其中中间字符 $x$ 来自前缀中所有与 $b$ 相等的位置。

• 设此前前缀中字符 $b$ 出现次数为 c，下标和为 s（下标从 1 开始）；
• 则新增回文数增量为 $\Delta_b =$$\sum_{j<i,,S_j=b}(i-j-1)