USACO 2023 January Contest, Gold, Find and Replace
Xem PDFBessie đang sử dụng phần mềm chỉnh sửa văn bản tiên tiến nhất, miV! Tính năng tìm và thay thế mạnh mẽ của nó cho phép cô tìm tất cả các ký tự chữ thường \(c\) và thay thế mỗi ký tự đó bằng một chuỗi không rỗng các chữ cái thường \(s\). Ví dụ, với chuỗi "ball", nếu Bessie chọn \(c\) là 'l' và \(s\) là "na", chuỗi sẽ biến thành "banana".
Bessie bắt đầu với chuỗi "a" và thực hiện một số thao tác tìm và thay thế, dẫn đến chuỗi cuối cùng là \(S\). Vì \(S\) có thể rất lớn, cô muốn biết, với các giá trị \(l\) và \(r\) thỏa mãn \(1 \le l \le r \le \min(|S|, 10^{18})\), chuỗi con \(S_{l \dots r}\) (từ ký tự thứ \(l\) đến ký tự thứ \(r\) trong \(S\)) là gì.
Đảm bảo rằng tổng độ dài của tất cả các chuỗi \(s\) trong các thao tác không vượt quá \(2 \cdot 10^5\), và \(r - l + 1 \le 2 \cdot 10^5\).
Input
- Dòng đầu tiên chứa các số nguyên \(l\), \(r\) và số lượng thao tác.
- Mỗi dòng tiếp theo mô tả một thao tác, chứa ký tự \(c\) và chuỗi \(s\) tương ứng. Tất cả các ký tự đều trong phạm vi từ 'a' đến 'z'.
Output
- In ra chuỗi \(S_{l \dots r}\) trên một dòng duy nhất.
Scoring
- Subtask \(1\): \(\sum |s|, r - l + 1 \le 2000\)
- Subtask \(2\): Không có ràng buộc nào khác.
Test 1
Input
3 8 4
a ab
a bc
c de
b bbb
Output
bdebbb
Note
Chuỗi được biến đổi như sau:
\({ a \rightarrow ab \rightarrow bcb \rightarrow bdeb \rightarrow bbbdebbb }\)
Bình luận
bài này sao giải
include <iostream>
include <vector>
include <string>
include <algorithm>
using namespace std;
string swaps(string s, const vector<pair\<char, string>>& v) {
for (const auto& x:v) {
char c=x.first;
const string& check= x.second;
string xau;
for (char ch:s) {
if (ch==c) {
xau+=check;
} else {
xau+=ch;
}
}
s=xau;
}
return s;
}
int main() {
int l,r,n;
cin >>l>>r>> n;
vector<pair\<char, string>> v(n);
for (int i=0;i<n;++i) { cin >>v[i].first >>v[i].second;
}
string s="a";
s=swaps(s,v);
l--;
r--;
if (l<0) l=0;
if (r>=s.length()) r=s.length() - 1;
cout << s.substr(l, r-l+1) << endl;
return 0;
} code cho anh em tham khảo hướng đi