Скачать все ссылки со страницы.

# for i in `lynx --dump $url | awk '/http/{print $2}'`; do wget $i; done

Модель аллокатора с использованием кучи и двусвязного списка

В распоряжении у менеджера памяти находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера - обрабатывать запросы приложений на выделение и освобождение памяти. Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом наш менеджер выделяет память из самого длинного свободного блока, а если таких несколько, то из них он выбирает тот, у которого номер первой ячейки - наименьший. После этого выделенный ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется. Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T - запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется. Требуется написать симуляцию менеджера памяти, удовлетворяющую приведенным критериям.
Количество ячеек 1<=N<=2^(31)-1, количество запросов 1<=m<=10^5. На вход подаются числа N и M, а затем M чисел, если число положительное - выделение памяти, отрицательное - освобождение. Для каждого запроса на выделение памяти в выход выводится одно число на отдельной строке с результатом выполнения запроса. Если память была выделена, выводится номер первой ячейки памяти в выделенном блоке, иначе выводится -1.
Для хранения свободных отрезков используется куча с итераторами на отрезки из двусвязного списка, в котором хранятся все отрезки. Приведенное решение имеет асимптотику O(m log(m)).

#include <vector>
#include <list>
#include <algorithm>
#include <cstdio>

using std::vector;
using std::list;
using std::swap;

struct Chunk {
  int start_;
  int length_;
  bool is_free_;
  int index_;

  Chunk(int start = 0, int length = 0, bool is_free = false, int index = 0):
      start_(start), length_(length), is_free_(is_free), index_(index) {}

  bool operator <(const Chunk& other) const {
    if (length_ < other.length_) {
      return true;
    }
    if (length_ == other.length_) {
      return start_ > other.start_;
    }
    return false;
  }

  bool operator ==(const Chunk& other) const {
    return start_ == other.start_ && length_ == other.length_ &&
        is_free_ == other.is_free_ && index_ == other.index_;
  }

  bool operator >(const Chunk& other) const {
    return other < *this;
  }
};

class MaxChunkHeap {
private:
  vector<list<Chunk>::iterator> array;
public:
  bool empty() const {
    return array.empty();
  }

  void Heapify(int root_index) {
    int left_son_index, right_son_index, largest_index;
    left_son_index = 2 * root_index + 1;
    right_son_index = 2 * root_index + 2;
    largest_index = root_index;
    if (left_son_index < array.size() &&
        *(array[left_son_index]) > *(array[largest_index])) {
      largest_index = left_son_index;
    }
    if (right_son_index < array.size() &&
        *(array[right_son_index]) > *(array[largest_index])) {
      largest_index = right_son_index;
    }
    if (largest_index != root_index) {
      swap(array[root_index]->index_, array[largest_index]->index_);
      swap(array[root_index], array[largest_index]);
      Heapify(largest_index);
    }
  }

  void ChangeKey(int index, list<Chunk>::iterator new_key) {
    array[index] = new_key;
    new_key->index_ = index;
    Heapify(index);
    while (index > 0 && *(array[(index - 1) / 2]) < *(array[index])) {
      swap(array[(index - 1) / 2]->index_, array[index]->index_);
      swap(array[(index - 1) / 2], array[index]);
      index = (index - 1) / 2;
    }
  }

  void Insert(list<Chunk>::iterator new_key) {
    array.push_back(new_key);
    ChangeKey(array.size() - 1, new_key);
  }

  list<Chunk>::iterator GetMax() {
    return array[0];
  }

  list<Chunk>::iterator ExtractMax() {
    list<Chunk>::iterator max_element = array[0];
    array[0] = array[array.size() - 1];
    array[0]->index_ = 0;
    array.pop_back();
    Heapify(0);
    return max_element;
  }

  void Remove(int index) {
    if (array.empty())
      return;
    array[index] = array[array.size() - 1];
    array[index]->index_ = index;
    array.pop_back();
    ChangeKey(index, array[index]);
  }

  MaxChunkHeap() {}
};

class Allocator {
private:
  MaxChunkHeap memory_heap_;
  list<Chunk> chunks_list_;
  vector<list<Chunk>::iterator> allocated_chunks_;
  int operations_counter_;
public:
  Allocator(int size_of_memory) {
    chunks_list_.push_back(Chunk(1, size_of_memory , true, 0));
    memory_heap_.Insert(chunks_list_.begin());
    operations_counter_ = 0;
  }

  int allocateMemory(int size) {
    ++operations_counter_;
    allocated_chunks_.resize(operations_counter_, chunks_list_.end());

    if (memory_heap_.empty()) {
      return -1;
    }

    if (memory_heap_.GetMax()->length_ < size) {
      return -1;
    }

    list<Chunk>::iterator free_chunk = memory_heap_.ExtractMax();
    Chunk new_chunk(free_chunk->start_, size, false);
    allocated_chunks_[operations_counter_ - 1] =
        chunks_list_.insert(free_chunk, new_chunk);

    if (free_chunk->length_ == size) {
      chunks_list_.erase(free_chunk);
      return allocated_chunks_[operations_counter_ - 1]->start_;
    }

    free_chunk->length_ -= size;
    free_chunk->start_ += size;
    memory_heap_.Insert(free_chunk);
    return allocated_chunks_[operations_counter_ - 1]->start_;
  }

  void deallocateMemory(int num) {
    ++operations_counter_;
    if (allocated_chunks_[num - 1] == chunks_list_.end()) {
      return;
    }

    allocated_chunks_[num - 1]->is_free_ = true;

    // Merge with prev
    if (allocated_chunks_[num - 1] != chunks_list_.begin()) {
      list<Chunk>::iterator prev_chunk = allocated_chunks_[num - 1];
      --prev_chunk;
      if (prev_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += prev_chunk->length_;
        allocated_chunks_[num - 1]->start_ = prev_chunk->start_;
        memory_heap_.Remove(prev_chunk->index_);
        chunks_list_.erase(prev_chunk);
      }
    }
    // Merge with next
    if (allocated_chunks_[num - 1] != --(chunks_list_.end())) {
      list<Chunk>::iterator next_chunk = allocated_chunks_[num - 1];
      ++next_chunk;
      if (next_chunk->is_free_) {
        allocated_chunks_[num - 1]->length_ += next_chunk->length_;
        memory_heap_.Remove(next_chunk->index_);
        chunks_list_.erase(next_chunk);
      }
    }

    memory_heap_.Insert(allocated_chunks_[num - 1]);
  }
};


void readInputToVector(vector<int> *vec) {
  int number_of_numbers, cur_number;
  scanf("%d", &number_of_numbers);
  for (int i = 0; i < number_of_numbers; ++i) {
    scanf("%d", &cur_number);
    vec->push_back(cur_number);
  }
}

void performRequests(const vector<int> &requests, vector<int> *output_vec,
                     Allocator *allocator) {
  for (vector<int>::const_iterator it = requests.begin(); it != requests.end();
  ++it) {
    if (*it > 0) {
      output_vec->push_back(allocator->allocateMemory(*it));
    }
    if (*it < 0) {
      allocator->deallocateMemory(-(*it));
    }
  }
}

void writeOutput(const vector<int> &vec) {
  for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    printf("%d\n", *it);
  }
}

int main() {
  int size_of_memory;
  scanf("%d", &size_of_memory);
  Allocator allocator(size_of_memory);
  vector<int> requests;
  readInputToVector(&requests);
  vector<int> output_vec;
  performRequests(requests, &output_vec, &allocator);
  writeOutput(output_vec);
  return 0;
}

Универсальное хеширование

Реализован класс для хранения множества целых чисел. FixedSet при вызове Initialize получает набор целых чисел, который впоследствии и будет хранить. Набор чисел не будет изменяться с течением времени (до следующего вызова Initialize). Операция Contains возвращает true, если число number содержится в наборе. Мат. ожидание времени работы Initialize составляет O(n), где n - количество элементов в numbers. Затраты памяти порядка O(n). Операция Contains выполняется за O(1).

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

#include <cstdio>
#include <vector>
#include <cstdlib>

using std::vector;

const long long g_BigPrimeNumber = 2147483647;

inline long long hashFunction(long long a_coefficient,
                              long long b_coefficient,
                              long long x) {
  return (((a_coefficient * x + b_coefficient) % g_BigPrimeNumber) +
      g_BigPrimeNumber) % g_BigPrimeNumber;
}

inline void generateHashFunctionCoefficients(long long *a, long long *b) {
  *a = rand() % (g_BigPrimeNumber - 1) + 1;
  *b = rand() % g_BigPrimeNumber;
}

class FixedSet {
 private:
  struct PrimaryHashTable {
    long long a_coefficient_, b_coefficient_;  // Hash function coefficients.
    struct SecondaryHashTable {
      long long a_coefficient_, b_coefficient_;  // Hash function coefficients.
      vector<int> numbers_to_store;
      vector<int> numbers;
      vector<int> numbers_empty;  // numbers_empty[i] is true while numbers[i]
                                  // is empty

      SecondaryHashTable(): a_coefficient_(0), b_coefficient_(0) {}
    };

    vector<SecondaryHashTable> secondary_hash_tables_;

    // Returns number of cell needed to keep hash table.
    unsigned long long memoryToKeepNumbers() const {
      unsigned long long result = 0;
      for (vector<SecondaryHashTable>::const_iterator sht =
           secondary_hash_tables_.begin(); sht != secondary_hash_tables_.end();
           ++sht) {
        result += sht->numbers_to_store.size() * sht->numbers_to_store.size();
      }
      return result;
    }

    void cleanNumbersToStore() {
      for (vector<SecondaryHashTable>::iterator sht =
           secondary_hash_tables_.begin(); sht != secondary_hash_tables_.end();
           ++sht) {
        sht->numbers_to_store.clear();
      }
    }

    // Resizes each secondary hash table to numbers_of_numbers_^2 size and
    // generates coefficients a and b for it.
    void prepareSecondaryHashTables() {
      for (vector<SecondaryHashTable>::iterator sht_iter
           = secondary_hash_tables_.begin();
           sht_iter != secondary_hash_tables_.end(); ++sht_iter) {
        sht_iter->numbers.resize(sht_iter->numbers_to_store.size() *
                                   sht_iter->numbers_to_store.size());
        sht_iter->numbers_empty.resize(sht_iter->numbers_to_store.size() *
                                       sht_iter->numbers_to_store.size(), true);
        generateHashFunctionCoefficients(&(sht_iter->a_coefficient_),
                                         &(sht_iter->b_coefficient_));
      }
    }

    void fillHashTable() {
      for (vector<SecondaryHashTable>::iterator sht_iter
           = secondary_hash_tables_.begin();
           sht_iter != secondary_hash_tables_.end(); ++sht_iter) {
        bool success = false;
        while (!success) {
          generateHashFunctionCoefficients(&(sht_iter->a_coefficient_),
                                           &(sht_iter->b_coefficient_));
          // Clear stored numbers.
          sht_iter->numbers_empty.assign(sht_iter->numbers_empty.size(), true);
          // Try to refill secondary hash table.
          success = true;
          for (vector<int>::const_iterator number_iter =
               sht_iter->numbers_to_store.begin();
               number_iter != sht_iter->numbers_to_store.end(); ++number_iter) {
            long long hash_in_sht = hashFunction(sht_iter->a_coefficient_,
                                                 sht_iter->b_coefficient_,
                                                 *number_iter) %
              sht_iter->numbers_to_store.size();
            if (sht_iter->numbers_empty[hash_in_sht]) {
              sht_iter->numbers[hash_in_sht] = *number_iter;
              sht_iter->numbers_empty[hash_in_sht] = false;
            } else if (sht_iter->numbers[hash_in_sht] != *number_iter) {
              // Fail. Collision again.
              success = false;
              break;
            }
          }
        }
      }
    }
  } primary_hash_table_;

  int total_number_of_numbers_;

  static const int k_MemoryLimitMultiplier = 4;

 public:

  void preparePrimaryHashTable(const vector<int> &numbers) {
    primary_hash_table_.secondary_hash_tables_.resize(numbers.size());
    do {
      generateHashFunctionCoefficients(&(primary_hash_table_.a_coefficient_),
                                       &(primary_hash_table_.b_coefficient_));
      primary_hash_table_.cleanNumbersToStore();
      for (vector<int>::const_iterator it  = numbers.begin();
      it != numbers.end(); ++it) {
        primary_hash_table_.secondary_hash_tables_[hashFunction(
            primary_hash_table_.a_coefficient_,
            primary_hash_table_.b_coefficient_, *it) % numbers.size()].
              numbers_to_store.push_back(*it);
      }
    } while (primary_hash_table_.memoryToKeepNumbers() >
             k_MemoryLimitMultiplier * numbers.size());
  }

  void Initialize(const vector<int> &numbers) {
    total_number_of_numbers_ = numbers.size();
    preparePrimaryHashTable(numbers);
    primary_hash_table_.prepareSecondaryHashTables();
    primary_hash_table_.fillHashTable();
  }

  explicit FixedSet() {}

  bool Contains(int number) const {
    int number_of_sht = hashFunction(primary_hash_table_.a_coefficient_,
                                     primary_hash_table_.b_coefficient_,
                                     number) % total_number_of_numbers_;
    if (primary_hash_table_.secondary_hash_tables_[number_of_sht].
        numbers_to_store.size() == 0) {
      return false;
    }
    int hash_in_sht = hashFunction(
      primary_hash_table_.secondary_hash_tables_[number_of_sht].a_coefficient_,
      primary_hash_table_.secondary_hash_tables_[number_of_sht].b_coefficient_,
      number) % primary_hash_table_.secondary_hash_tables_[number_of_sht].
        numbers_to_store.size();
    return (!primary_hash_table_.secondary_hash_tables_[number_of_sht].
              numbers_empty[hash_in_sht] &&
            primary_hash_table_.secondary_hash_tables_[number_of_sht].
              numbers[hash_in_sht] == number);
  }
};

void readInputToVector(vector<int> *result_vector) {
  int number_of_numbers, current_int;
  scanf("%d", &number_of_numbers);
  for (int i = 0; i < number_of_numbers; ++i) {
    scanf("%d", &current_int);
    result_vector->push_back(current_int);
  }
}

void testNumbers(const FixedSet &fixed_set,
                 const vector<int> &numbers_to_test,
                 vector<bool> *result_of_test) {
  for (vector<int>::const_iterator it = numbers_to_test.begin();
       it != numbers_to_test.end(); ++it) {
    result_of_test->push_back(fixed_set.Contains(*it));
  }
}

void writeOutput(const vector<bool> &output_vector) {
  for (vector<bool>::const_iterator it = output_vector.begin();
       it != output_vector.end(); ++it) {
    *it ? printf("Yes\n") : printf("No\n");
  }
}

int main() {
  srand(2010);
  vector<int> numbers, numbers_to_test;
  vector<bool> result_of_test;
  readInputToVector(&numbers);
  readInputToVector(&numbers_to_test);
  FixedSet fixed_set;
  fixed_set.Initialize(numbers);
  testNumbers(fixed_set, numbers_to_test, &result_of_test);
  writeOutput(result_of_test);
  return 0;
}

Кириллица в библиотеке MySQLdb языка python

MySQLdb перед выполнением запроса пытается кодировать запрос в latin-1, поэтому когда в запросе есть кириллические символы в юникоде, вылетает такая ошибка:

"UnicodeEncodeError:'latin-1' codec can't encode character ...".

После того, как я провозился с этим пол дня, я нашел решение в гугле вот здесь http://www.dasprids.de/blog/2007/12/17/python-mysqldb-and-utf-8 (огромное спасибо этому парню). Вкратце необходимо выполнить эти команды после установления соединения:

db.set_character_set('utf8')
dbc.execute('SET NAMES utf8;')
dbc.execute('SET CHARACTER SET utf8;')
dbc.execute('SET character_set_connection=utf8;')

Где db - результат MySQLdb.connect, dbc - результат db.cursor().

Наибольшая общая подпоследовательность

По идее можно решать за O(nlogn), но здесь за O(n^2) простой динамикой:

#include <vector>
#include <iostream>
#include <algorithm>

using std::vector;
using std::cin;
using std::cout;
using std::max_element;

int countLongestCommonSubsequenceLength(const vector<int> &first_sequence,
                                        const vector<int> &second_sequence) {
  vector< vector<int> > common_prefix_length(first_sequence.size() +
    1, vector<int>(second_sequence.size() + 1, 0));
  for (size_t first_number = 1;
       first_number <= first_sequence.size();
       ++first_number) {
    for (size_t second_number = 1;
         second_number <= second_sequence.size();
         ++second_number) {
      if (first_sequence[first_number - 1] ==
          second_sequence[second_number - 1]) {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number - 1][second_number - 1] + 1;
      } else if (common_prefix_length[first_number - 1][second_number] >=
          common_prefix_length[first_number][second_number - 1]) {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number - 1][second_number];
      } else {
        common_prefix_length[first_number][second_number] =
          common_prefix_length[first_number][second_number - 1];
      }
    }
  }
  return common_prefix_length.back().back();
}

void readSequence(vector<int> *sequence) {
  int length, tmp_int;
  cin >> length;
  for (int element_number = 0; element_number < length; ++element_number) {
    cin >> tmp_int;
    sequence->push_back(tmp_int);
  }
}

int main() {
  vector<int> first_sequence, second_sequence;
  readSequence(&first_sequence);
  readSequence(&second_sequence);
  cout << countLongestCommonSubsequenceLength(first_sequence, second_sequence)
       << std::endl;
  return 0;
}

Циклический сдвиг последовательности на заданное число позиций

Параметры begin и end могут быть либо указателями на ячейки массива, либо итераторами, указывающими на начало и конец последовательности. Параметр k может принимать отрицательные значения, что означает сдвиг в другом направлении. Продемонстрирована работа функции с обычным массивом и вектором.

#include <vector>
#include <iostream>
#include <algorithm>

using std::vector;
using std::cout;
using std::endl;
using std::swap;

template <typename T> void rotate(T begin, T end, int k) {
  if (k > 0) {
    for (int i = 0; i < k; ++i) {
      for (T j = end - 1; j != begin; --j) {
        swap(*j, *(j-1));
      }
    }
  }
  if (k < 0) {
    for (int i = 0; i > k; --i) {
      for (T j = begin; j != end - 1; ++j) {
        swap(*j, *(j+1));
      }
    }
  }
}

// Test.
int main() {
  vector<int> a;
  a.push_back(1);
  a.push_back(2);
  a.push_back(3);
  a.push_back(4);
  rotate(a.begin(), a.end(), 2);
  for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
  int b[] = {1,2,3,4};
  rotate(b+0, b+4, -1);
  for (int i = 0; i < 4; i++) {
    cout << b[i] << " ";
  }
  cout << endl;
  return 0;
}

Метод деления пополам

Нахождение корня передаваемой в качестве параметра монотонной функции f на отрезке [a, b] методом деления пополам.

//Fuction returns b+1 if solution does not exist.
double solve(double a, double b, double (*f)(double)) {
  if (a > b) {
    return b+1;
  }
  if (f(a) * f(b) >= 0) {
    if (f(a) == 0) {
      return a;
    }
    if (f(b) == 0) {
      return b;
    }
    return b+1;
  }
  double x = (a + b) / 2;
  if (f(a) * f(x) <= 0) {
    return solve(a, x, f);
  }
  if (f(x) * f(b) <= 0) {
    return solve(x, b, f);
  }
  return b+1;
}