最优分割

Special Judge 提交数: 154, 通过率: 0.65%, 平均分: 0.91

题目描述:

一个数字序列是回文的,当且仅当其从前往后读与从后往前读不变。

形式地,一个序列\(S[1..n]\)是回文的当且仅当对任意\(j \in [1..n]\),有\(S[j] = S[n-j+1]\)。

定义一个回文数字序列\(S[1..n]\)的能量值为\[P(S[1..n]) = (S[1] \oplus S[2] \oplus \dots \oplus S[\lceil n/2 \rceil]) \times n\]

其中\(\oplus\)表示按位异或,\(\lceil n/2 \rceil\)表示向上取整。

即能量值为序列左半部分数字异或和(若长度为奇数,包括正中间的数字)乘上序列长度。

现给定一个长度为\(N\)的序列\(T\),问将序列\(T[1..N]\)分割成若干个连续的回文序列,这些回文序列的能量和最大为多少?

请输出使得能量和最大的任一合法分割方案。

输入格式:

第一行一个整数\(N\)。

第二行\(N\)个整数表示序列\(T\)。

\(1 \le N \le 10^6, 0 \le T[i] \le 10^9\).

输出格式:

第一行输出能得到的最大能量和为多少。

第二行输出一个整数\(C\),表示\(T\)被分割成了\(C\)块。

接下来\(C\)行,升序输出每一块的右端点的下标。

样例输入:

6
1 2 1 2 1 2

样例输出:

18
2
3
6

提示:

 \(T\)的分割方法有\((1), (2), (1), (2), (1), (2); (1), (2, 1, 2), (1), (2); (1, 2, 1), (2, 1, 2) \dots\)

其中分割成\((1, 2, 1), (2, 1, 2)\)能量值为\((1 \oplus 2) \times 3 + (2 \oplus 1) \times 3 = 3 \times 3 + 3 \times 3 = 18\),为最优解。

时间限制: 3000ms
空间限制: 512MB

来源: by Massimo