B. 炼金术

Codeforces

IDCF10217B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

小白最近沉迷炼金术。通过炼金术，小白可以获得很多没见过的新物质，例如 $c u + a l arrow.r a u + c l$。在这种炼金术中，每一种物质都可以用一个只包含小写字母的字符串来表示。同一个字符串表示相同的物质，不同的字符串表示的物质也不同。如果一种物质对应的字符串包含在另一种物质对应的字符串中，也就是它作为子串出现在另一种物质中，那么这种物质通过炼金术流程可以得到另一种物质。例如，_ababc_中包含了_aba_，但_abcba_中不包含_aba_。小白认为一种物质只有它对应的字符串长度恰好为 $n$ 时，它才是最令人愉悦的。现在小白手里已经有 $m$ 种已知物质，他希望找到一种新的物质。该物质不能从已有的 $m$ 种物质中的任何一种中得到，同时也必须是有令人愉悦的特质。聪明的你能帮助他找到一种这样的物质吗？请输出该物质对应的字符串，如果有多种这样的物质存在，你可以输出任意一种，题目保证至少存在一种新的物质。输入共 $m + 1$ 行，第一行输入两个正整数 $n " "(1 <= n <= 10^5)$ 和 $m " "(1 <= m <= 10^4)$ 由空格间隔开，表示新物质对应字符串长度 $n$ 和小白手里已有的物质种类数 $m$。接下来 $m$ 行，第 $i$ 行输入一个字符串 $s_i$，表示第 $i$ 种物质对应的字符串。字符串只包含小写字母，且保证 $\\sum_{i = 1}^{m} | s_i | <= 3 times 10^5$。请输出一个长度为 $n$ 的字符串，描述小白可以炼出的新物质。 ## Input 输入共 $m + 1$ 行，第一行输入两个正整数 $n " "(1 <= n <= 10^5)$ 和 $m " "(1 <= m <= 10^4)$ 由空格间隔开，表示新物质对应字符串长度 $n$ 和小白手里已有的物质种类数 $m$。接下来 $m$ 行，第 $i$ 行输入一个字符串 $s_i$，表示第 $i$ 种物质对应的字符串。字符串只包含小写字母，且保证 $\\sum_{i = 1}^{m} | s_i | <= 3 times 10^5$。 ## Output 请输出一个长度为 $n$ 的字符串，描述小白可以炼出的新物质。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the required length of the target string. Let $ m \in \mathbb{Z}^+ $ be the number of existing strings. Let $ S = \{s_1, s_2, \dots, s_m\} $ be the set of existing strings, where each $ s_i \in \Sigma^* $ and $ \Sigma = \{a, b, \dots, z\} $. **Constraints** 1. $ 1 \le n \le 10^5 $ 2. $ 1 \le m \le 10^4 $ 3. $ \sum_{i=1}^m |s_i| \le 3 \times 10^5 $ 4. Each $ s_i $ consists only of lowercase English letters. **Objective** Find a string $ t \in \Sigma^n $ such that for all $ s_i \in S $, $ s_i \not\subseteq t $ (i.e., $ s_i $ is not a substring of $ t $). Output any such $ t $.

API Response (JSON)

{
  "problem": {
    "name": "B. 炼金术",
    "description": {
      "content": "小白最近沉迷炼金术。通过炼金术，小白可以获得很多没见过的新物质，例如 $c u + a l arrow.r a u + c l$。 在这种炼金术中，每一种物质都可以用一个只包含小写字母的字符串来表示。同一个字符串表示相同的物质，不同的字符串表示的物质也不同。如果一种物质对应的字符串包含在另一种物质对应的字符串中，也就是它作为子串出现在另一种物质中，那么这种物质通过炼金术流程可以得到另一种物质。例",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10217B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小白最近沉迷炼金术。通过炼金术，小白可以获得很多没见过的新物质，例如 $c u + a l arrow.r a u + c l$。\n\n在这种炼金术中，每一种物质都可以用一个只包含小写字母的字符串来表示。同一个字符串表示相同的物质，不同的字符串表示的物质也不同。如果一种物质对应的字符串包含在另一种物质对应的字符串中，也就是它作为子串出现在另一种物质中，那么这种物质通过炼金术流程可以得到另一种物质。例...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the required length of the target string.  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of existing strings.  \nLet $ S = \\{s_1, s_2, \\dots, s_m\\} $ be the ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments