Отказ от ответственности:
Я новичок в конкурентном программировании, и это я документирую моих учащихся. Итак, все, что я говорю, это просто то, что я думаю в данный момент и не следует принимать как твердые истины.
Это было долгое время, когда я практиковал свои конкурентные навыки программирования. Не очень хорошо у него. Последний я практиковал тщательно было во время подготовки к интервью в июле 2020 года.
Фаза 1: Основное здание
Я планировал решить как минимум два Реализация Основанные проблемы каждый день в течение месяца, начиная с сегодняшнего дня и дополнительно изучая один новый алгоритм ежедневно. Я лично люблю алгоритмы строки, поэтому я начну оттуда.
Проблема 1: не отвлекайтесь!
main() {
int n;
cin >> n;
string s;
cin >> s;
s.erase(unique(begin(s), end(s)), end(s));
sort(begin(s), end(s));
auto it = unique(begin(s), end(s));
if(it != end(s)) cout << "NO";
else cout << "YES";
}
Сложность времени: O (NLOG (N)) Пространство сложности: o (1) # не учитывая пространство для хранения данных
Другое решение:
main() {
int n;
cin >> n;
string s;
cin >> s;
unordered_set se;
bool yes = true;
for(int i = 0; i < n; i++) {
if(i && s[i] == s[i-1]) continue;
if(se.count(s[i])) {
yes = false;
break;
}
se.insert(s[i]);
}
if(yes) cout << "YES";
else cout << "NO";
}
Сложность времени: O (n) Космическая сложность: O (n) # Неупорядоченный набор используется для содержания Элементы для проверки.
Проблема 2: черный квадрат
main() {
vector v(4);
for(auto& e: v) cin >> e;
string s;
cin >> s;
long long total = 0;
for(auto& c: s) {
int p = c - '0' - 1; // additional -1 for zero based indexing
total += v[p];
}
cout << total;
}
Это было бы веселее, чтобы написать в Python.
v = list(map(int, input().split())) s = input() s = [int(c)-1 for c in s] # -1 for zero based indexing total = sum(v[i] for i in s) print(total)
Я уверен, что мы могли бы использовать Find STL-алгоритм для кода C ++. Это все на сегодняшний день 2 решения проблемы реализации.
Давайте надеемся изучать один новый/старый алгоритм строки.
Струнный алгоритм
Основной вопрос, когда дело доходит до строки, о том, является ли данный узор длины м происходит в текст длина n . Проблема может быть решена с использованием наивного метода в O (N * M) времени.
main() {
string text = "abcabc";
string pattern = "abc";
int n = text.length(), m = pattern.length();
bool found = false;
// looping through all starting position of the pattern
for(int i = 0; i < n-m+1; i++) {
// checking if the substring matches
if(text.substr(i, m) == pattern) {
found = true;
break;
}
}
if(found) cout << "YES";
else cout << "NO";
}
Сейчас есть алгоритмы, которые могут решить вышеупомянутое образец в O (N + M) времени. Первый, который имеется в виду, это знаменитый Кнут Моррис Пратт или лучше известен как алгоритм KMP.
Здесь Видео Дональда Кнута говорит о алгоритме КМП.
vectorprefix_func(string s) { int n = s.length(); vector pi(n, 0); for(int i = 1; i < n; i++) { int j = pi[i-1]; while(j > 0 && s[i] != s[j]) j = pi[j-1]; if(s[i] == s[j]) j++; pi[i] = j; } return pi; }
Чтобы использовать алгоритм KMP, предварительно вычислите таблицу, используя выше prefix_func Отказ Так для данного шаблон и текст , строка, которая должна быть передана prefix_func это Шаблон + х + текст , где «X» – какой-то персонаж, который не принадлежит ни одному узору, ни тексту.
Разные вопросы, которые можно ответить:
- Происходит ли шаблон в тексте?
- Сколько раз происходит шаблон в тексте?
- Если происходит рисунок, найдите начальную позицию в тексте.
- Найдите максимальное не перекрывающееся вхождение рисунка в тексте. И многое другое.
Большую часть времени сопоставление шаблона используется в качестве части для решения проблемы, а не целая проблема.
Источники:
Prefix_function: – CP-алгоритмы
Ресурсы для дополнительного обучения и практики:
Датирован: 13 июля 2021
Оригинал: “https://dev.to/geekypandey/day-1-rebooting-the-competitive-programming-drive-23lf”