AdditionalFile5559.zip

#5559. 「POI2026 R1」Przeglądarka internetowa

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – I etap Przeglądarka internetowa

Bajtosia 正在准备一堂信息学课的报告，她需要访问 $n$ 个互不相同的网页（地址全为小写字母组成），从中收集所需资料。

她使用的浏览器有一个地址栏，初始内容为空字符串。可以通过以下四种按键操作来修改地址栏内容并访问网页：

1. 按下 $\texttt{a}\sim \texttt{z}$ 中的任意小写字母：将该字母追加到当前地址栏末尾。
2. 按下 $\texttt{BACKSPACE}$（用 $\texttt{B}$ 表示）：删除地址栏最后一个字符（若已为空则无效果）。
3. 按下 $\texttt{ENTER}$（用 $\texttt{E}$ 表示）：访问当前地址栏内容的网页，随后清空地址栏（变回空字符串）。
4. 按下 $\texttt{TAB}$（用 $\texttt{T}$ 表示）：自动补全功能——把当前地址栏内容补全为「最近一次访问过的、且以当前内容为前缀的网页地址」。如果没有这样的已访问网页，则无效果。

Bajtosia 时间紧迫，她希望用最少的按键次数完成以下目标：

• 恰好访问给定的 $n$ 个目标网页各一次（顺序任意）
• 不能访问任何非目标网页

请你计算出最少按键次数，并输出一种合法的按键序列。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 10^6)$，表示需要访问的网页数量。

接下来 $n$ 行，每行一个非空字符串 $s_i$（仅含小写字母 $\texttt{a}\sim \texttt{z}$），表示第 $i$ 个目标网页地址。

所有 $s_i$ 互不相同，且总长度和 $S = |s_1| + \cdots + |s_n| \leq 10^6$。

输出格式

第一行输出一个整数 $k$，表示最少的按键次数。

第二行输出长度为 $k$ 的字符串，仅由以下字符组成：

• $\texttt{a}\sim \texttt{z}$（输入字母）
• $\texttt{B}$（Backspace）
• $\texttt{E}$（Enter）
• $\texttt{T}$（Tab）

若有多种最优方案，输出任意一种即可。

只要你输出的第一行（即最少按键次数 $k$）正确，即使第二行缺失或错误，你仍能得到该测试点 $80\%$ 的分数。

注：本题因spj程序有问题，所以只判断整数 $k$ 是否正确 。第二行一样要输出，只是不做判断。

样例

输入

3
aaaaba
aaaaczzz
aaaadb

输出

21
aaaabaETBBdbETBBczzzE

1. 输入 aaaaba → 按 E → 访问 aaaaba，清空
2. 按 T → 自动补全为最近访问的 aaaaba
3. 按两次 B → 删除成 aaaa
4. 输入 db → 变成 aaaadb → 按 E → 访问 aaaadb，清空
5. 按 T → 再次补全为 aaaaba（当前最近的以 aaaa 为前缀的是 aaaaba）
6. 再按两次 B → 得到 aaaa
7. 输入 czzz → 变成 aaaaczzz → 按 E → 访问 aaaaczzz

总共 $21$ 次按键，完成了全部三个网页的访问。

附加样例

1. $n=26$，每个串前 $19999$ 个字符都是 $\texttt{a}$，最后一个字符依次为 $\texttt{a}\sim \texttt{z}$
2. $n=10$，第 $i$ 个串为 $18i$ 个 $\texttt{a}$
3. $n=65534$，包含所有长度 $\leq 15$ 的非空 $\texttt{a/b}$ 二元串
4. $n=2$，两个长度 $500000$ 的串，前 $300000$ 位相同，第 $300001$ 位不同，后面随机

数据范围与提示

详细子任务附加限制及分值如下表所示。