petuhovskiy (06 января 2012 - 19:13) писал:
А_какое_там_свойство?
12 публикаций создано Andrew (учитываются публикации только с 04-июня 23)
Отправлено от Andrew в 12 января 2012 - 06:25 in Комбинаторика
Отправлено от Andrew в 17 января 2012 - 18:18 in Комбинаторика
//----------------------------------------------------------------------------------// // Название: GeneralDeployment // // Автор кода(именно кода): Andrew (Krasnobaev) // // Сайт: redcode.do.am (временно пуст) // // Описание: Размещение, занесённое в запись, в качестве метода(классов то тут нет) // //----------------------------------------------------------------------------------// type ArrType = array[0..65536] of byte; DepType = array[0..10000] of ArrType; Comb_Class = record procedure IntGeneralDeployment(ArrLength, DepLength: longint; Arr: ArrType; var DepArr: DepType; var DepCount: LongInt); var p, q: array [0..10000] of byte; i, j, k, d: longint; begin DepCount := 0; for i := 1 to ArrLength do p[i] := i; repeat for i := 0 to DepLength do q[i] := p[i]; while q[0] = 0 do begin while q[0] = 0 do begin inc(DepCount); for i := 1 to DepLength do DepArr[DepCount][i] := Arr[q[i]]; j := DepLength; while q[j - 1] > q[j] do dec(j); k := DepLength; while q[j - 1] > q[k] do dec(k); d := q[j - 1]; q[j - 1] := q[k]; q[k] := d; for i := j to (DepLength + j - 1) div 2 do begin d := q[DepLength + j - i]; q[DepLength + j - i] := q[i]; q[i] := d; end; end; end; j := DepLength; while (j > 0) and (p[j] = j + ArrLength - DepLength) do dec(j); if j > 0 then begin p[j] := p[j] + 1; for i := j + 1 to DepLength do p[i] := p[i - 1] + 1; end; until j = 0; end; end; var Combinatorics: Comb_Class; ArrLength: 0..65536; DepLength, DepCount, i, j: LongInt; Arr: ArrType; DepArr: DepType; begin //Ввод и настройка параметров writeln('Entering:'); read( ArrLength, DepLength ); for i:=1 to ArrLength do read(Arr[i]); //Само размещение Combinatorics.IntGeneralDeployment( ArrLength, DepLength, Arr, DepArr, DepCount ); //Вывод writeln; writeln('Result:'); for i:=1 to DepCount do begin write('Deployment №',i,' is ( '); for j:=1 to DepLength do write(DepArr[i][j],' '); writeln(' );'); end; writeln('There are ',DepCount,' Deployments'); writeln('Press <Enter> to finish :'); readln; end.
Отправлено от Andrew в 17 января 2012 - 19:39 in Комбинаторика
Отправлено от Andrew в 16 января 2012 - 19:53 in Комбинаторика
Отправлено от Andrew в 22 декабря 2011 - 08:33 in Комбинаторика
Отправлено от Andrew в 17 января 2012 - 18:23 in Комбинаторика
LVP (23 декабря 2011 - 12:37) писал:
Отправлено от Andrew в 14 ноября 2012 - 15:42 in Структуры данных
Отправлено от Andrew в 14 ноября 2012 - 11:07 in Структуры данных
Отправлено от Andrew в 10 ноября 2012 - 19:29 in Структуры данных
Куча - структура данных, дерево, элементы которых удовлетворяют некоторым условиям. Существует много разных типов куч, но самой распространённой является двоичная или бинарная куча. Все её элементы должны выполнять два условия:
// Перечесление типов кучи enum heapType { MaxHeap, MinHeap }; template <class type> class heap { public: // Конструктор heap(heapType ht = MaxHeap) { length = 0; heapT = ht; } // Перегрузка оператора type& operator[](int index) { return data[index]; } // Всплытие элемента под номером. Возвращает новый номер этого же элемента int shiftUp(int index) { while (index > 1 && data[index / 2] < data[index] && heapT == MaxHeap || index > 1 && data[index / 2] > data[index] && heapT == MinHeap) { swap(data[index], data[index / 2]); index = index / 2; } return index; } // Потопление элемента под номером. Возвращает новый номер этого же элемента int shiftDown(int index) { bool finish = false; while (2 * index <= length && !finish) { int temp = index; if (data[2 * index] > data[temp] && heapT == MaxHeap || data[2 * index] < data[temp] && heapT == MinHeap) temp = 2 * index; if (2 * index + 1 <= length && (data[2 * index + 1] > data[temp] && heapT == MaxHeap || data[2 * index + 1] < data[temp] && heapT == MinHeap)) temp = 2 * index + 1; if (index == temp) finish = true; else swap(data[index], data[temp]); index = temp; } return index; } // Преобразование массива в кучу void build() { for (int i = length / 2; i > 0; i--) shiftDown(i); } // Сортирует кучу по неубыванию void sort() { build(); int t = length; while (length > 1) { swap(data[1], data[length]); length--; shiftDown(1); } length = t; } // Добовляет к этой куче кучу heap void concat(heap heap) { for (int i = 1; i <= heap.length; i++) add(heap[i]); } // Добовление value в кучу. Возвращает новый номер этого же элемента int add(int value) { length++; data[length] = value; return shiftUp(length); } // Удаляет элемент под номером index из кучи int remove(int index) { data[index] = data[1] + 1; shiftUp(index); data[1] = data[length]; length--; if (length) return shiftDown(1); return 0; } // Возвращает первый элемент и удаляет его type first() { if (length) { type temp = data[1]; remove(1); return temp; } else return 0; } // Ставит элемент под номером index на своё место. Возвращает новый номер этого же элемента int test(int index) { int f = shiftUp(index); if (f != index) return f; return shiftDown(index); } // Массив кучи type data[100000]; // Длина кучи int length; // Тип кучи heapType heapT; };
Увеличение приоритета №1164 на informatics.mccme.ru
#include <iostream> using namespace std; //ЗДЕСЬ КЛАСС КУЧИ int main() { heap<int> heap; int n; cin >> n; for (int i = 1; i <= n; i++) { int t; cin >> t; heap.add(t); } cin >> n; for (int i = 1; i <= n; i++) { int a, b; cin >> a >> b; heap[a] += b; cout << heap.test(a) << "\n"; } for (int i = 1; i <= heap.length; i++) cout << heap[i] << " "; system("pause > nul"); return 0; }