| | Вызов 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} |
