[NordicOI 2023] ChatNOI

Luogu

IDLGP10646

Time4000ms

Memory1024MB

DifficultyP6

2023Special JudgeNordicOI（北欧）

你正在和你的机器人玩一个对话游戏，规则是这样的：首先给定一个包含了 $n$ 个字符串的仅含小写字符串组 $w$ 和一个数字 $k$。定义一个字符串组的质量为其每个长度为 $k+1$ 的连续段的在 $w$ 中出现的次数的最小值。有 $q$ 次询问，每次给定 $m_i$ 与 $k$ 个字符串。你需要构造 $m_i$ 个字符串，使得在给出的 $k$ 个字符串后依次加入构造的 $m_i$ 个字符串形成的字符串组质量最大。若有多解，只需输出任意一个。 ## Input 第一行一个整数 $n(1 \leq n \leq 5 \times 10^5)$ 和 $k (1 \leq k < n)$。第二行一句包含 $n$ 个单词的句子 $w_i( 1\leq|w_i| \leq10)$。第三行一个整数 $q(1 \leq q \leq 5 \times 10^5)$，表示一共有 $q$ 次询问。然后 $q$ 行，每行一个数 $m_i$ 和长度为 $k$ 的 $s$ 的子字符串。 ## Output 你需要对于每个询问，输出 $k$ 之后的 $m_i$ 个单词。 [samples] ## Background 翻译自 [NordicOI 2023 A 题](https://noi23.kattis.com/contests/noi23/problems/chatnoi) ChatNOI。 ## Note **本题采用捆绑测试**。令 $M = \sum m_i$。 - Subtask 1（5 points）：$k < n \leq 100$，$k = 1$，$1 \leq q \leq 100$，$m_i = 1$。 - Subtask 2（7 points）：$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10^5$，$m_i = 1$。 - Subtask 3（17 points）：$k < n \leq 6$，$1 \leq k \leq 10$，$1 \leq q \leq 10$，$1 \leq m_i \leq 6$。 - Subtask 4（18 points）：$k < n \leq 5000$，$1 \leq k \leq10$，$1 \leq q \leq 5000$，$q \leq M \leq 5000$。 - Subtask 5（24 points）：$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10$，$q \leq M \leq 5 \times 10^5$。 - Subtask 6（16 points）：$k < n \leq 10^5$，$1 \leq k \leq10$，$1 \leq q \leq 10^5$，$q \leq M \leq 5 \times 10^5$。 - Subtask 7（13 points）：无特殊限制。对于所有测试数据，$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10^5$，$q \leq M \leq 5 \times 10^5$。

Samples

Input #1

13 2
ullen dullen doff kikke lane koff koffe lane bikke bane ullen dullen doff
3
1 ullen dullen
2 ullen dullen
3 ullen dullen

Output #1

doff 
doff kikke 
doff kikke lane

Input #2

8 1
buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo
1
7 buffalo

Output #2

buffalo buffalo buffalo buffalo buffalo buffalo buffalo

Input #3

16 1
have you not heard about the bird the bird bird bird the bird is the word
8
1 have
1 you
1 not
1 heard
1 about
1 the
1 bird
1 is

Output #3

you 
not 
heard 
about 
the 
bird 
bird 
the

API Response (JSON)

{
  "problem": {
    "name": "[NordicOI 2023] ChatNOI",
    "description": {
      "content": "你正在和你的机器人玩一个对话游戏，规则是这样的： 首先给定一个包含了 $n$ 个字符串的仅含小写字符串组 $w$ 和一个数字 $k$。 定义一个字符串组的质量为其每个长度为 $k+1$ 的连续段的在 $w$ 中出现的次数的最小值。 有 $q$ 次询问，每次给定 $m_i$ 与 $k$ 个字符串。 你需要构造 $m_i$ 个字符串，使得在给出的 $k$ 个字符串后依次加入构造的 $m_i$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10646"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你正在和你的机器人玩一个对话游戏，规则是这样的：\n\n首先给定一个包含了 $n$ 个字符串的仅含小写字符串组 $w$ 和一个数字 $k$。\n\n定义一个字符串组的质量为其每个长度为 $k+1$ 的连续段的在 $w$ 中出现的次数的最小值。\n\n有 $q$ 次询问，每次给定 $m_i$ 与 $k$ 个字符串。\n\n你需要构造 $m_i$ 个字符串，使得在给出的 $k$ 个字符串后依次加入构造的 $m_i$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments