Тема: Теоретический минимум для нубов.
Всем привет! Я начинающий "спортивный программист" поэтому не очень сильно шарю в алгоритмах.
Захотелось определить приоритеты изучения алгоритмов(обучаюсь самостоятельно), пожалуйста помогите мне.
Начальный знания:
#include С++, STL, некоторые простые алгоритмы, математика(школьный уровень).
И так я начну (по убыванию приоритета){
0 = математика(){
0.2 = Факторизация числа;
0.3 = Расширенный алгоритм Евклида[НОД,НОК,обратный элемент];
}
1 = Длинная арифметика ;
2 = Комбинаторика(){
2.1 = коэффициент Сnm;
2.2 = генерация перестановок;
}
3 = Геометрия(){
3.1 = Теорема Пифагора[с отрезками];
3.2 = Теорема синусов, косинусов[с треугольниками];
}
4 = Алгоритмы на графах(){
4.1 = Поиск в ширину == волновой алгоритм == BFS;
4.2 = Поиск в глубину == DFS;
4.3 = Максимальный поток[метод Эдмондса-Карпа];
4.4 = Нахождение каркаса графа[Крускал,Прима];
4.5 = ...;
}
5 = Алгоритмы на строках(){
5.1 = быстрый поиск подстроки с использование хэш + дерево сумм;
}
6 = Динамическое программирование(){
6.1 = нахождение способов замощения области;
6.2 = нахождение способов замощения области по маски;
}
7 = Жадное программирование[это уже "врожденное" умение программировать];
8 = Структуры данных(){
8.1 = хэш;
8.1 = двоичное дерево;
8.2 = дерево максимум/минимумов/сумм;
8.3 = система не пересекающихся множеств[как подзадача других задач];
8.4 = сбалансированные деревья АВЛ, красно-черное;
8.4 = ...;
}
9 = ....;
}
Еще хочется побольше знать вещей на подобии:
1. Хэш-таблицы реализованы в STL hash_map,hash_set.
2. Множестве set в STL есть сбалансированное красно-черное дерево.
3. Длинная арифметика реализована в Java ее можно использовать на соревнованиях.
4. Граф является деревом если E == V - 1, где E - кол-во ребер, V - кол-во вершин.
5. Количество делителей числа равно произведению степеней простых множителей числа увеличенных на единицу.
6. %i - оказывается пытается распознать системы счисления числа.
7. Для определения количества способов замостить область фигурками 2х1 можно использовать мак. пар(узнал с этого форума).
8. Вывод вектора:
vector<any_type> a(5,0);
cout << a; //выведет {0,0,0,0,0}если предварительно описать:
template<class T>
ostream& operator<<(ostream& out, const vector<T> a){/
out << "{";
if(!a.empty()) out << a[0];
for(int i = 1; i < (int)a.size(); i++) out << ", " << a[i];
out << "}";
return out;
}9. При перемножении элементов массива тип который long long нужно использовать 1ll чтоб при перемножении числа не воспринимались как int(узнал с этого форума)
long long a[3] = {121111111,1111111111,0};
a[2] = a[0]*1ll*a[1];P.S.
Это то что для меня кажется "хитростями", для кого-то покажется ерундой. Но я думаю у Вас все равно есть знания которые для Вас кажутся "хитрыми", поделитесь ими.
P.P.S.
Не сомневайтесь умные книги я тоже читаю(все лето читал) и продолжаю читать:)
