| Вызов lower_bound: |
| {noformat} |
| int pos = lower_bound(dict.begin(), |
| dict.end(), |
| make_pair(pref, 0)) |
| - dict.begin(); |
| {noformat} |
| В pos находим (дихотомией) в отсортированном словаре пар dict |
| позицию слова пары со словом pref. |
| \\ |
| |
| 14_FebB. AUTO |
| [http://dl.gsu.by/task.jsp?nid=1270623&cid=15] |
| |
| Идея решения, вводим словарь и по ходу заносим в вектор слова и номера этих слов в словаре. |
| Сортируем слова по возрастанию (вместе с номерами). |
| Цикл по поисковым префиксам |
| Вводим префикс и его позицию k |
| Дихотомией (с помощью lower bound) |
| ищем в словаре pos первое вхождение префикса |
| Инкрементируем pos на k |
| Если полученная позиция в словаре, |
| а слово на этой позиции совпадает с префиксом |
| Тогда выводим её |
| Иначе выводим \-1 |
| |
| Подробнее о коде |
| {noformat} |
| | int pos = lower_bound(dict.begin(), |
| dict.end(), |
| make_pair(pref, 0)) |
| - dict.begin(); |
| | int pos = lower_bound(dict.begin(), |
| dict.end(), |
| make_pair(pref, 0)) |
| - dict.begin(); |
| {noformat} |
| В pos находим (дихотомией) в отсортированном словаре позицию слова pref. |
| {noformat} |
| | int poss = pos + k; |
| if (poss < dict.size() && match(pref, dict\[poss\].first)) |
| cout << dict\[poss\].second + 1 << endl; |
| else cout << \-1 << endl; |
| | int poss = pos + k; |
| if (poss < dict.size() && match(pref, dict[poss].first)) |
| cout << dict[poss].second + 1 << endl; |
| else cout << -1 << endl; |
| {noformat} |
| если k-ое вхождение есть и соответствует pref, |
| тогда выводим исходный номер слова |
| иначе вводим \-1 |
| {noformat} |
| bool match(string pref, string word) |
| | { |
| if (pref.size() > word.size()) return false; |
| return word.substr(0, pref.size()) == pref; |
| } |
| | { |
| if (pref.size() > word.size()) return false; |
| return word.substr(0, pref.size()) == pref; |
| } |
| {noformat} |
| Соответствие слова из словаря word и искомого префикса pref |
| Выясняется с помощю булевой функции match |
| |
| Далее приведен полный текст решения |
| {code:title=all.cpp\|borderStyle=solid} |
| | \#include <bits/stdc++.h> |
| | #include <bits/stdc++.h> |
| using namespace std; |
| |
| int n, m; |
| vector<pair<string, int> > dict; |
| |
| bool match(string& pref, string& word) |
| | { |
| if (pref.size() > word.size()) return false; |
| return word.substr(0, pref.size()) == pref; |
| } |
| | { |
| if (pref.size() > word.size()) return false; |
| return word.substr(0, pref.size()) == pref; |
| } |
| |
| | int main() |
| | int main() |
| { |
| | freopen("auto.in", "r", stdin); |
| freopen("auto.out", "w", stdout); |
| cin >> n >> m; |
| for (int i = 0; i < n; i++) |
| { |
| string s; |
| cin >> s; |
| dict.push_back(make_pair(s, i)); |
| } |
| sort(dict.begin(), dict.end()); |
| for (int i = 0; i < m; i++) |
| { |
| int k; string pref; |
| cin >> k >> pref; |
| k--; |
| int pos = lower_bound(dict.begin(), |
| dict.end(), |
| make_pair(pref, 0)) |
| - dict.begin(); |
| int poss = pos + k; |
| if (poss < dict.size() && match(pref, dict\[poss\].first)) |
| cout << dict\[poss\].second + 1 << endl; |
| else cout << \-1 << endl; |
| } |
| | freopen("auto.in", "r", stdin); |
| freopen("auto.out", "w", stdout); |
| cin >> n >> m; |
| for (int i = 0; i < n; i++) |
| { |
| string s; |
| cin >> s; |
| dict.push_back(make_pair(s, i)); |
| } |
| sort(dict.begin(), dict.end()); |
| for (int i = 0; i < m; i++) |
| { |
| int k; string pref; |
| cin >> k >> pref; |
| k--; |
| int pos = lower_bound(dict.begin(), |
| dict.end(), |
| make_pair(pref, 0)) |
| - dict.begin(); |
| int poss = pos + k; |
| if (poss < dict.size() && match(pref, dict[poss].first)) |
| cout << dict[poss].second + 1 << endl; |
| else cout << -1 << endl; |
| } |
| } |
| {code} |