0518蚂蚁暑期实习上机考试题3：小红的字符串构造

题目

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

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

现在给定一个长度为 n 的数组。你需要构造一个 01 串，满足其长度为 i 的前缀的权值恰好是数组的第 i 项。

输入描述：

第一行输入一个正整数 n ，代表待构造的字符串长度。

第二行输入一个长度为 n 的数组，代表待构造的 01 串每个长度的前缀权值。

输出描述：

如果无解，请输出 -1 。

否则输出一个长度为 n 的 01 串，有多解时输出任意即可。

输入样例1：

3
0 0 1

输出样例1（输出000，111，101亦可）：

010

解答

1. 问题分析:

   • 回文子序列定义为三个位置i < j < k，其中首尾字符相同。

   • 需要构造一个01串，使得每个前缀的权值严格匹配给定的数组。

2. 关键观察:

   • 前两个字符的权值必须为0，因为无法形成长度为3的子序列。

   • 每次添加新字符时，新增的回文子序列数目取决于前序字符的分布。

3. 算法选择:

   • 枚举所有可能的前两个字符组合（00, 01, 10, 11）。

   • 对每个组合，模拟后续字符的构造过程，维护字符计数和位置和以快速计算新增的回文子序列数目。

# 此代码通过了85%的测试点
n = int(input())
a = list(map(int, input().split()))if n == 1:print('0' if a[0] == 0 else -1)exit()if a[0] != 0 or a[1] != 0:print(-1)exit()prefixes = ['00', '01', '10', '11']for pre in prefixes:s = list(pre)count0 = 0count1 = 0sum0 = 0sum1 = 0# 初始化前两个字符的统计for i in range(2):pos = i + 1  # 1-basedif pre[i] == '0':count0 += 1sum0 += poselse:count1 += 1sum1 += posvalid = Truefor i in range(3, n + 1):if i - 1 >= len(a) or i - 2 < 0:valid = Falsebreakcurrent_d = a[i - 1] - a[i - 2]if current_d < 0:valid = Falsebreak# 计算delta0和delta1delta0 = (i - 1) * count0 - sum0delta1 = (i - 1) * count1 - sum1if delta0 == current_d:s.append('0')count0 += 1sum0 += ielif delta1 == current_d:s.append('1')count1 += 1sum1 += ielse:valid = Falsebreakif valid and len(s) == n:print(''.join(s))exit()print(-1)