题目详情题解（0）讨论（0）提交记录（0）

AT_abc374_g.[ABC374G] Only One Product Name

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Keyence 的所有商品名均由两个大写英文字母组成。
现已使用了 NN 个商品名，第 ii 个商品名（1≤i≤N1\leq i\leq N）为 SiS_i。
由于已使用过的商品名不能再次使用，为了能快速查找过去用过的商品名，决定制作一个 NG 列表。

NG 列表需要满足以下条件：

  • 由一个或多个字符串组成，每个字符串仅包含大写英文字母。
  • 对于每一个已经使用过的商品名，至少存在一个字符串将其作为（连续的）子串包含。
  • 列表中的所有字符串都不包含任何不是已使用商品名的长度为 22 的字符串作为（连续的）子串。

请你求出 NG 列表中字符串数量可能的最小值。

输入格式

输入按以下格式从标准输入给出。

NN
S1S_1
S2S_2
⋮\vdots
SNS_N

输出格式

请输出 NG 列表中字符串数量可能的最小值。

输入输出样例

  • 输入#1

    7
AB
BC
CA
CD
DE
DF
XX

    输出#1

    3

  • 输入#2

    5
AC
BC
CD
DE
DF

    输出#2

    2

  • 输入#3

    6
AB
AC
CB
AD
DB
BA

    输出#3

    1

说明/提示

限制条件

  • 1≤N≤2621\leq N\leq 26^2
  • NN 为整数。
  • SiS_i 为仅包含大写英文字母的长度为 22 的字符串。
  • S1,S2,…,SNS_1,S_2,\ldots,S_N 均互不相同。

样例解释 1

满足条件的 NG 列表例如可以由以下 33 个字符串组成：

  • CABCDE
  • DF
  • XX
    这是由 33 个字符串组成的，且不存在由 22 个或更少字符串组成且满足条件的 NG 列表，因此输出 33。

样例解释 2

满足条件的 NG 列表例如可以由以下 22 个字符串组成：

  • ACDE
  • BCDF
    注意，已使用过的商品名可以在 NG 列表中的多个字符串中出现，也可以在同一个字符串中出现多次。

样例解释 3

例如，仅由 ABACBADB 组成的 NG 列表就满足条件。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页