#PU1281. USACO 2023 January Contest, Gold — Problem 1. Find and Replace

    ID: 1503 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan23来源:usaco.orgscoring:equal_test_cases字符串模拟

USACO 2023 January Contest, Gold — Problem 1. Find and Replace

USACO 2023 January Contest, Gold — Problem 1. Find and Replace

题目描述

Bessie is using the latest and greatest innovation in text-editing software, miV! Its powerful find-and-replace feature allows her to find all occurrences of a lowercase English letter cc and replace each with a nonempty string of lowercase letters ss. For example, given the string "ball\texttt{ball}", if Bessie selects cc to be 'l' and ss to be "na\texttt{na}", the given string transforms into "banana\texttt{banana}". Bessie starts with the string "a\texttt{a}" and transforms it using a number of these find-and-replace operations, resulting in a final string SS. Since SS could be massive, she wants to know, given ll and rr with 1≤l≤r≤min⁡(∣S∣,1018)1\le l\le r\le \min(|S|,10^{18}), what Sl…rS_{l\dots r} (the substring of SS from the ll-th to the rr-th character inclusive) is. It is guaranteed that the sum of ∣s∣|s| over all operations is at most 2⋅1052\cdot 10^5, and that r−l+1≤2⋅105r-l+1\le 2\cdot 10^5.

输入格式

The first line contains ll, rr, and the number of operations. Each subsequent line describes one operation and contains cc and ss for that operation. All characters are in the range 'a' through 'z'.

输出格式

(见题面原文)

数据范围

Inputs 2-7: ∑∣s∣,r−l+1≤2000\sum |s|, r-l+1\le 2000 Inputs 8-15: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

3 8 4
a ab
a bc
c de
b bbb
bdebbb
The string is transformed as follows:
$$\texttt{a} \rightarrow \texttt{ab} \rightarrow \texttt{bcb} \rightarrow \texttt{bdeb} \rightarrow \texttt{bbbdebbb}$$