Chọn từ
Đề bài: CHONTU – Chọn từ
Cho danh sách A gồm $K$ từ phân biệt và danh sách B gồm $N$ kí tự.
Yêu cầu: lần lượt xét các kí tự trong danh sách B từ trên xuống, với mỗi kí tự $c$, hãy ghi ra từ $w$ tìm được trong danh sách A thỏa thứ tự ưu tiên sau:
- Từ $w$ phải bắt đầu bằng kí tự $c$.
- Nếu có nhiều từ $w$ bắt đầu bằng kí tự $c$, chọn từ được lấy ít nhất trong các lần trước đó.
- Nếu có nhiều hơn 1 từ thỏa điều kiện 1, 2; lấy từ có độ lớn (thứ tự từ điển) bé nhất.
Dữ liệu vào đảm bảo với mỗi kí tự có đúng 1 từ được chọn.
Input
- Dòng đầu ghi hai số nguyên dương $K$, $N$ ($1 \le K, N \le 10^5$).
- $K$ dòng sau, mỗi dòng ghi 1 từ độ dài không quá 21 kí tự.
- $N$ dòng sau, mỗi dòng ghi 1 kí tự.
Từ và kí tự chỉ gồm các chữ cái viết thường $\{a \ldots z\}$.
Output: ghi $N$ dòng, mỗi dòng là 1 từ tìm được theo yêu cầu.
Subtask
- 50% số test đầu tiên có $K, N \le 10^3$.
- 50% số test còn lại không có giới hạn gì thêm.
5 5
mai
no
mung
nam
moi
n
m
n
m
nnam
mai
no
moi
namNộp bài
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJMấu chốt: tìm kiếm cho nhanh
Với quy luật mà đề bài đưa ra thì ta thấy tóm lại thao tác chủ yếu là thao tác tìm kiếm. Cụ thể là tìm kiếm từ thỏa mãn tiêu chí từ 1 tới 3 như đề đã công bố rồi in từ đó ra. Vậy nếu ta không làm tốt thao tác tìm kiếm thì bài này rất có thể sẽ bị TLE khi test đầu vào lớn. Vậy ta phải nhìn ra những mấu chốt để tìm kiếm nhanh được.
Thì khi nhắc đến bài toán tìm kiếm, các bạn đã học rồi thì sẽ biết chính yếu có 2 dạng là tìm kiếm tuần tự và tìm kiếm nhị phân. Tìm kiếm tuần tự sẽ cho độ phức tạp $O(N)$, trong khi đó tìm kiếm nhị phân sẽ cho độ phức tạp là $O(\log N)$. Vậy thì chắc chắn tìm kiếm nhị phân sẽ tối ưu hơn nhiều. Nhưng để tìm kiếm nhị phân được thì danh sách cần có thứ tự tăng dần hay giảm dần, vậy lúc này nó lại có liên quan đến vấn đề cần phải sắp xếp. Thì khi nói về sắp xếp các bạn học rồi sẽ biết các thuật toán sắp xếp tệ nhất là $O(N^2)$ (N lũy thừa 2, ^ ở đây là ký hiệu của lũy thừa chứ không phải phép xor nha các bạn), tối ưu hơn chúng ta sẽ có độ phức tạp $O(N \log N)$.
Vậy tóm lại nhìn vào bài này trước mắt với yêu cầu tìm kiếm là ta thấy muốn tối ưu là phải sắp xếp danh sách theo một trật tự nào đó. Thì đọc vào ta sẽ thấy trong số những quy luật có quy luật yêu cầu là nếu có nhiều từ thỏa mãn các tiêu chí thì chọn từ có thứ tự từ điển nhỏ nhất. Đến đây ta thấy rằng có vẻ là ta sẽ cần phải đi sắp xếp các từ tăng dần theo thứ tự từ điển, rồi thì từ đó ta mới có thể ngay lập tức tìm được từ có thứ tự từ điển nhỏ nhất để chọn là từ nào. Trước mắt ta có thể nhìn thấy một số điểm như thế để dần hình thành tư tưởng giải quyết bài này, giờ ta bắt đầu đi sâu vào hơn.
Bước 1: phân nhóm các từ theo chữ cái đầu
Thì ta thấy yêu cầu 1: từ $w$ phải bắt đầu bằng ký tự $c$. Vậy ta thấy phải làm sao khi có ký tự $c$ thì ngay lập tức lọc ra được những từ có ký tự đầu tiên là ký tự $c$, rồi thì từ đó ta mới tìm kiếm trong phạm vi các từ đó. Và ta thấy rằng ký tự $c$ cũng chỉ gói gọn trong 26 ký tự của bảng chữ cái từ a đến z, vậy nên nếu ngay từ bước đọc các từ $w$ từ input vào mà ta phân loại ra được những từ $w$ có ký tự đầu tiên trùng nhau thì phân nó vào một nhóm riêng, để khi tìm kiếm ta có thể ngay lập tức xét được những từ đó. Cái này nó giống như khi các bạn tra cứu quyển sách từ điển giấy vậy đó, nếu bạn nào đã từng. Vậy nên ta cần phải sàng lọc phân loại để giảm thiểu phạm vi phải tìm kiếm, từ đó thúc đẩy việc tìm được nhanh hơn.
Giải pháp trong tình huống này là ta đi dùng kỹ thuật mảng đánh dấu: cụ thể ta tạo ra mảng 2 chiều chuỗi (tức là mảng 2 chiều mà mỗi phần tử trong mảng là 1 chuỗi), mảng 2 chiều này có số dòng cố định là 26 dòng ngầm định ứng với 26 ký tự bảng chữ cái, nghĩa là index dòng từ 0 đến 25. Ta hiểu dòng index 0 sẽ là tập hợp danh sách các từ có ký tự đầu tiên là a, dòng index 1 sẽ là tập hợp danh sách các từ có ký tự đầu tiên là b, và cứ thế … dòng index 25 sẽ là tập hợp danh sách các từ có ký tự đầu tiên là z. Còn cụ thể trên mỗi dòng thì số lượng cột (phần tử) sẽ không giống nhau, bởi vì nó tùy theo dữ liệu input vào. Nên nói chính xác mảng 2 chiều này là mảng 2 chiều răng cưa.
Tiện nhất trong tình huống này là đi dùng cấu trúc dữ liệu vector (kiểu mảng động), hoặc không thì dùng con trỏ cấp 2 cấp phát động mảng 2 chiều, nhưng đụng đến con trỏ thì phức tạp nếu bạn nào không rành.
string a[26][k]; bên trong hàm main và bị tràn stack khi $k$ là $10^5$, lúc này phải đem nó khai báo làm mảng toàn cục thì mới không bị tràn.Thì khi ta đã có mảng 2 chiều chuỗi có 26 dòng, thì mỗi chuỗi s đọc vào ta xét ký tự đầu tiên (s[0]) lấy nó trừ cho ký tự 'a', tức là s[0] - 'a', thì sẽ ra ngay index của dòng tương ứng cần đưa chuỗi s đó vào. Tại sao lại như vậy? Vì bản chất các ký tự được lưu trữ theo mã ASCII: ký tự 'a' có mã ASCII là 97, 'b' là 98, 'c' là 99 và cứ thế … 'z' là 122. Thì khi lấy s[0] - 'a', giả sử s[0] là ký tự 'a' thì lúc này nó hiểu: 97 − 97 = 0 (tức là index 0). Giả sử s[0] là ký tự 'b' thì lúc này nó hiểu: 98 − 97 = 1 (tức là index 1). Chỉ 1 phép tính là ta xác định ngay lập tức được chuỗi đó cần đưa vào dòng có index bao nhiêu trong mảng 2 chiều.
Sau khi đọc toàn bộ input vào thì ta đã có mảng 2 chiều chuỗi với mỗi dòng là tập hợp những từ có ký tự đầu tiên giống nhau. Lúc này ta đi vào từng dòng và sắp xếp toàn bộ các chuỗi trong từng dòng tăng dần theo thứ tự từ điển. Với ví dụ của đề, sau bước này ta có:
Bước 2: lấy lần lượt từ trái qua phải, hết thì quay vòng
Đến đây các bạn phải nhắm mắt lại và tưởng tượng một chút: nếu toàn bộ các dòng đã được sắp xếp xong, lúc này chưa có chuỗi nào được chọn cả vì chưa đọc ký tự $c$ nào vào mà. Rồi thì bắt đầu đọc vào ký tự $c$ đầu tiên, thì dựa theo ký tự $c$ đó ta xác định chuỗi kết quả cần lấy ra nằm tại dòng index c - 'a' trong mảng 2 chiều. Rồi thì trong số những chuỗi đang có tại dòng này và đã được sắp xếp theo thứ tự từ điển tăng dần, nếu giờ xét theo tiêu chí 2 thì mọi chuỗi đều chưa có chuỗi nào được lấy, nghĩa là theo tiêu chí 2 lúc này ta có thể lấy tùy ý chuỗi nào cũng đều hợp lệ. Lúc này phải xét qua tiêu chí 3: là sẽ lấy chuỗi có thứ tự từ điển nhỏ nhất. Vậy trong tình huống hiện tại khi danh sách đang sắp tăng dần theo thứ tự từ điển thì nghĩa là ta sẽ lấy chuỗi đầu tiên, index 0 tại dòng đó.
Rồi thì các bạn lại tưởng tượng tiếp: nếu tiếp theo sau đó ký tự $c$ được đọc vào tiếp theo lại tính ra index nó nằm tại đúng dòng index mà ta vừa xét xong, thì có phải giờ đây từ tiếp theo được lấy sẽ là từ kế tiếp từ trước đó không? Tức là từ nằm tại index 1 trên dòng đó. Tại sao lại như vậy? Vì nếu trước đó ta lấy từ đầu tiên thì nghĩa là nó đã được lấy 1 lần, toàn bộ các từ còn lại từ index 1 về cuối đều chưa được lấy, nên lần xét này theo tiêu chí 2 ta sẽ không thể lấy từ đầu tiên mà chỉ lấy từ thứ 2 trở đi (index 1 trở đi), và trong số những từ này thì từ có thứ tự từ điển nhỏ nhất chính là từ index 1. Rồi cứ thế nếu việc trên lặp lại thì sẽ lấy từ index 2 và cứ thế từ trái qua phải … cho đến khi nào mà toàn bộ các từ trên dòng đó đều được lấy hết, tức là đều được lấy 1 lần, thì nếu lần tiếp theo mà lại xét dòng đó thì ta sẽ lấy lại từ tại index 0, vì lúc này toàn bộ các từ đều có số lần lấy như nhau thì chọn theo từ có thứ tự từ điển nhỏ nhất.
Vậy lúc này có 1 vấn đề là nếu dòng đó (gọi là dòng A đi ha) cứ liên tục được xét thì ta cứ theo quy luật lấy từ trái qua phải trên dòng A đó; nhưng nếu ký tự $c$ đọc vào tiếp theo lại tính ra chỉ số index dòng khác trên mảng 2 chiều (ví dụ gọi là dòng B đi), thì làm sao để ở 1 lần nào đó trong tương lai khi xét lại dòng A thì ta nhớ là ta đang xét đến index nào trên dòng A đó? Để từ đó tiếp tục quy trình đi từ trái qua phải như đã nói ở trên.
Vậy ta sẽ thấy rằng ta cần có biến lưu vị trí index ở lần cuối cùng ta xét đến trên dòng đó, để khi xét lại dòng đó ta gọi biến đó ra là biết được ta cần xét index tiếp theo là index nào. Và tổng cộng ta có đến 26 dòng, nên giải pháp ta lại tiếp tục có thêm một mảng đánh dấu int b[26], và b[i] hiểu là vị trí index ta đang xét trên dòng thứ $i$ ($i$ tính từ 0 đến 25) của mảng 2 chiều. Cứ thế mỗi lần xét xong vị trí index trên dòng nào thì cập nhật b[i]++, và nhớ xét nếu b[i] sau khi ++ mà bằng với số lượng phần tử trên dòng đó thì phải reset lại b[i] về 0 để sẽ xét lại từ đầu. Và nói như thế nghĩa là ngay từ đầu khi khai báo mảng b ta cũng khởi tạo tất cả đều là 0 để hiểu là xét bắt đầu từ index 0.
Rồi thì quy trình cứ như trên mình đã nói thôi: cứ ký tự $c$ đọc vào, tính ra chỉ số index dòng trong mảng 2 chiều bằng cách idx = c - 'a'. Rồi duyệt vào dòng index đó trên mảng 2 chiều và xuất chuỗi nằm tại vị trí index b[idx] trên dòng đó, rồi thì cập nhật lại b[idx] và cứ thế xét tiếp ký tự $c$ mới đọc vào. Chạy thử với ví dụ của đề (ô xanh là từ được in ra):
| c | idx = c − 'a' | b[idx] | Dòng a[idx] | In ra | b[idx] mới |
|---|---|---|---|---|---|
| n | 13 | 0 | namno | nam | 1 |
| m | 12 | 0 | maimoimung | mai | 1 |
| n | 13 | 1 | namno | no | 0 (reset) |
| m | 12 | 1 | maimoimung | moi | 2 |
| n | 13 | 0 | namno | nam | 1 |
Em nhập danh sách từ và các kí tự rồi bấm Tiếp để xem từng bước: phân nhóm, sắp xếp, rồi lấy quay vòng bằng con trỏ:
Source code
Source code để các bạn tham khảo với tư tưởng mình trình bày ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int k, n;
cin >> k >> n;
vector<vector<string>> a(26);
int b[26] = {0};
string s;
char c;
while(k--){
cin >> s;
a[s[0] - 'a'].push_back(s);
}
for(int i = 0; i < a.size(); ++i){
sort(a[i].begin(), a[i].end());
}
while(n--){
cin >> c;
int idx = c - 'a';
cout << a[idx][b[idx]] << endl;
b[idx]++;
if(b[idx] == a[idx].size()){
b[idx] = 0;
}
}
return 0;
}import sys
input = sys.stdin.readline
k, n = map(int, input().split())
a = [[] for _ in range(26)]
b = [0] * 26
for _ in range(k):
s = input().strip()
a[ord(s[0]) - ord('a')].append(s)
for i in range(26):
a[i].sort()
for _ in range(n):
c = input().strip()
idx = ord(c) - ord('a')
print(a[idx][b[idx]])
b[idx] += 1
if b[idx] == len(a[idx]):
b[idx] = 0Giải thích một số chỗ trong code ở trên:
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều, như trường hợp bài này ta thấy $K$, $N$ tối đa là $10^5$, vậy trong trường hợp xấu nhất ta sẽ cần nhập cả $10^5$ từ và $10^5$ ký tự nên đây cũng là số lượng lớn thì ta nên để thêm 2 dòng này vào đầu để chương trình chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.while(n--)tức là vòng lặp sẽ lặp đủ $n$ lần (mỗi lần kiểm tran != 0rồi giảmnđi 1). Chỗ này mình giải thích kỹ kẻo bạn nào không biết, mình thường thích ghi gọn như vậy, chứ mình thấy nhiều bạn phải code dài dòng nhưfor(int i = 1; i <= n; i++)thì cũng là vòng lặp lặp đủ $n$ lần nhưng khá dài dòng khi gõ, trong khi gõ như trên sẽ rất ngắn gọn.vector<vector<string>> a(26);ta khởi tạo mảng 2 chiều mà mỗi phần tử trong đó là kiểustring(chuỗi), mảng này đầu tiên khởi tạo 26 dòng, rồi cứ mỗi từ được đọc vào biếnstring sta xác định theo ký tựs[0]để biết từ đó sẽ nằm tại dòngs[0] - 'a'trong mảng 2 chiều. Và như thế ta gọia[s[0] - 'a'].push_back(s);, tức là đưa chuỗisđó vào cuối cùng của dònga[s[0] - 'a'].sort(a[i].begin(), a[i].end());nghĩa là sắp xếp tăng dần các phần tử từa[i].begin()tức là từ đầu đếna[i].end()tức là đến cuối. Vớia[i]ở đây chính là dòng index $i$ trong mảng 2 chiều, lúc này nó sẽ đi sắp xếp các chuỗi trong dòng index $i$ tăng dần. Hàmsortnày có độ phức tạp tối ưu $O(N \log N)$ và ngắn gọn để gọi ra thay vì phải tự cài đặt phức tạp. Bạn nào không biết thì nên tìm hiểu về hàm này nhé. Thì cứ thế vòng lặp chạy đủ qua 26 dòng để mọi dòng đều được sắp xếp.- Sau khi đã làm được các bước ở trên thì sau cùng ký tự $c$ đọc vào đi tính ra chỉ số index dòng trong mảng 2 chiều, rồi thì sẽ lấy từ tại vị trí index
b[idx]trên dòng đó, sau đó cập nhậtb[idx]++, và nếu thấyb[idx]sau khi++mà bằnga[idx].size(), tức là bằng với số lượng phần tử trên dòng đó, nghĩa là đã xét hết toàn bộ các phần tử trên dòng đó, ta resetb[idx]về 0 để lần tiếp theo sẽ xét lại từ index 0 trên dòng đó.
Đánh giá độ phức tạp
- Độ phức tạp không gian (Space Complexity): thì bản chất khi dùng cấu trúc dữ liệu trong STL C++ như
vectortrong bài này chẳng hạn là lúc nào nó cũng cấp phát dư bộ nhớ để ta dùng cho thoải mái, nên nếu tính chính xác thì không được, ta sẽ tính một cách tương đối theo đúng dữ kiện trong bài này đưa ra: mảngatuy lưu ở dạng mảng 2 chiều nhưng suy cho cùng nó cũng chỉ lưu đủ $K$ từ thôi. Còn mảngblưu 26 phần tử thì có thể xem như độ phức tạp hằng số, nên ta có thể kết luận độ phức tạp không gian bộ nhớ sẽ là $O(K)$ với $K$ là số từ cần đọc vào. - Độ phức tạp thời gian (Time Complexity): bước đọc các từ ở input có độ phức tạp $O(K)$ + bước sắp xếp các từ trong từng dòng tăng dần, thì tổng cộng tất cả các dòng cộng lại hết là $K$ từ, nên có thể hiểu là đi sắp xếp toàn bộ $K$ từ tăng dần, độ phức tạp bước này là $O(K \log K)$ + bước xử lý đọc từng ký tự $c$ vào và đi in ra kết quả tương ứng, bước này có độ phức tạp $O(N)$. Vậy độ phức tạp thời gian cả thảy là $O(K) + O(K \log K) + O(N)$. Nếu xét giữa $O(K) + O(K \log K)$ thì theo quy tắc cộng Big O sẽ lấy theo thành phần lớn nhất nên chỗ này ta có thể chỉ tính $O(K \log K)$, sau đó là cộng thêm $O(N)$ nên cũng theo quy tắc cộng Big O, ta có thể kết luận độ phức tạp thời gian tổng quát sẽ là $O(\max(K \log K, N))$, với $K$ là số lượng từ, $N$ là số lượng ký tự.
Vậy trong trường hợp xấu nhất khi $N$, $K$ tối đa là $10^5$ theo như đề công bố, như thế thì độ phức tạp thời gian sẽ là $10^5 + 10^5 \times \log(10^5) + 10^5$. Hàm log ở đây nói chính xác là logarit cơ số 2, vậy tổng lúc này sẽ khoảng $19 \times 10^5$. Thì với ngưỡng này vẫn nhỏ hơn ngưỡng giới hạn 1 giây là $(3 \div 5) \times 10^7$ hay cao lắm là $10^8$ nên ta yên tâm sẽ không bị TLE với cách làm này (mình chạy thử test lớn nhất thì C++ chỉ mất khoảng 0.06 giây).