1 Отредактировано manof (2009-09-01 20:23:28)

Тема: Теоретический минимум для нубов.

Всем привет! Я начинающий "спортивный программист" поэтому не очень сильно шарю в алгоритмах.
Захотелось определить приоритеты изучения алгоритмов(обучаюсь самостоятельно), пожалуйста помогите мне.
   
Начальный знания:
#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.
Не сомневайтесь умные книги я тоже читаю(все лето читал) и продолжаю читать:)

2

Re: Теоретический минимум для нубов.

manof пишет:

4. Граф является деревом если E/2 == V - 1, где E - кол-во ребер, V - кол-во вершин.

Вообще-то просто E = V - 1;

3 Отредактировано manof (2009-09-01 20:36:55)

Re: Теоретический минимум для нубов.

2rf пишет:

Вообще-то просто E = V - 1;

Точно, спасибо, я просто со старого кода списывал, а там видимо ребро за два считалось как то вот и поделил на два;)

Еще интересные штучки из старого архива сайта e-maxx:
1. CTRL+SHIFT+8 в Visual Studio.
2. Зарегистрировать тип(чтоб подсвечивался как int,char... ) файл usertype.dat добавить в \Microsoft Visual Studio 8\Common7\IDE, в файле в каждой строе должна быть одна запись(например можно заставить светиться string)).

4

Re: Теоретический минимум для нубов.

В C++ много всяких "хитростей", и если хорошо знать язык, то можно умело применять разные конструкции даже в олимпиадных задачах. Но вот описывать всё это на форуме, в виде таких обрывков - вряд ли от этого будет много толка smile

5

Re: Теоретический минимум для нубов.

2rf пишет:
manof пишет:

4. Граф является деревом если E/2 == V - 1, где E - кол-во ребер, V - кол-во вершин.

Вообще-то просто E = V - 1;



На самом деле это не совсем верно : )

Пример :
4 3 -- 4 вершины, 3 ребра
1 2 -- ребро из 1й вершины во 2ю
2 3
3 1

В рез-те ваш "алгоритм" скажет, что данный граф -- дерево, что вопиющий гон : )
Граф должен еще не иметь циклов : )

6

Re: Теоретический минимум для нубов.

Ну лично для меня олимпиадное программирование -- это только ради диплома на всеросе и радости от придуманного алгоритма : ) Вообще, я, видимо, после всероса 2010 вообще забью на такого рода проганье, ибо уже задолбало нереалне имхо % )
Кстати, как считаете, вот с таким подходом к жизни, куда стоит идти -- на ВМК МГУ или на МехМат МГУ?
И да, а кто откуда?( я имею в виду универы и факультеты  : ) )

7

Re: Теоретический минимум для нубов.

chum пишет:

В рез-те ваш "алгоритм" скажет, что данный граф -- дерево, что вопиющий гон : )
Граф должен еще не иметь циклов : )

Ну здесь проще сказать, что компонента связности, у которой |E| = |V|-1 является деревом.

8 Отредактировано manof (2009-09-09 11:20:32)

Re: Теоретический минимум для нубов.

уточнение:
Если граф связан(существует путь между двумя любыми вершинами) и E = V - 1, то данный граф является деревом.

Ну лично для меня олимпиадное программирование -- это только ради диплома на всеросе и радости от придуманного алгоритма : ) Вообще, я, видимо, после всероса 2010 вообще забью на такого рода проганье, ибо уже задолбало нереалне имхо % )
Кстати, как считаете, вот с таким подходом к жизни, куда стоит идти -- на ВМК МГУ или на МехМат МГУ?

Лично для меня как для нуба, спортивное программирование(СП) увлекательное интересное занятие, и я сам по себе.

С точки зрения такого подхода:
имхо куда бы вы не поступили, все равно будете заниматься тем чем вам угодно, поэтому я считаю что лучше не тратить время, и сразу идти туда куда хочется.

С точки зрения престижности:
Тогда поступать надо в МГУ)

9

Re: Теоретический минимум для нубов.

Подскажите, какие самоучилки книги хорошие есть? А то нереально просто разобраться