AT_abc268_f [ABC268F] Best Concatenation

题目描述

给定 $N$ 个仅由数字 $1$ 到 $9$ 以及 X 组成的字符串 $S_1, S_2, \ldots, S_N$。

你可以任选一个 $1$ 到 $N$ 的排列 $P = (P_1, P_2, \ldots, P_N)$，并将字符串 $S_{P_1}, S_{P_2}, \ldots, S_{P_N}$ 按顺序连接，得到字符串 $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$。这里的 $+$ 表示字符串的连接操作。

然后，对字符串 $T = T_1T_2\ldots T_{|T|}$ 计算其“得分”（$|T|$ 表示 $T$ 的长度）。 $T$ 的得分从 $0$ 开始，按照以下 $9$ 个步骤计算：

• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 1 的整数对 $(i, j)$，每对使得得分加 $1$。
• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 2 的整数对 $(i, j)$，每对使得得分加 $2$。
• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 3 的整数对 $(i, j)$，每对使得得分加 $3$。
• $\cdots$
• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 9 的整数对 $(i, j)$，每对使得得分加 $9$。

请输出在任意选择排列 $P$ 时，$T$ 的得分可能取得的最大值。

输入格式

输入按以下格式从标准输入读入。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3
1X3
59
XXX

输出 #1

71

输入输出样例 #2

输入 #2

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

输出 #2

3010

说明/提示

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $N$ 为整数
• $S_i$ 是仅由数字 $1$ 到 $9$ 以及 X 组成的字符串，长度至少为 $1$
• $S_1, S_2, \ldots, S_N$ 的总长度不超过 $2 \times 10^5$

样例解释 1

当 $P = (3, 1, 2)$ 时，$T = S_3 + S_1 + S_2 =$ XXX1X359。此时，$T$ 的得分如下计算：

• 满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 1 的整数对 $(i, j)$ 有 $3$ 个；
• 满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 3 的整数对 $(i, j)$ 有 $4$ 个；
• 满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 5 的整数对 $(i, j)$ 有 $4$ 个；
• 满足 $1 \leq i < j \leq |T|$ 且 $T_i =$ X 且 $T_j =$ 9 的整数对 $(i, j)$ 有 $4$ 个。

因此，$T$ 的得分为 $1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71$，这也是可能取得的最大值。

由 ChatGPT 4.1 翻译