Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи и алгоритмы на C++

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Май 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Виктор Журавлев

Статистика

1.725 подписчиков
-1 за неделю
←   Все выпуски   →

Олимпиадные задачи и алгоритмы на C++


Информационный Канал Subscribe.Ru

Олимпиадные задачи и алгоритмы на C++

    Здравствуйте, уважаемые подписчики.

Решение задачи №3 "Префикс-подстрока" (5 баллов).

    У этой задачи есть как минимум два возможных решения. Первое решение является более простым с "идейной" точки зрения. Оно заключается в двоичном поиске искомой длины префикса. Если для проверки префикса использовать КМП-поиск, то алгоритм будет иметь сложность O(n*log(n)). Второе решение короче и имеет сложность O(n), но требует более глубокого знания метода КМП. На самом деле в код, приведенный во втором выпуске рассылки, достаточно внести минимальные изменения. Искомая длина префикса будет равна максимуму по значениям переменной k после каждой итерации второго цикла. Вот и все!

    Ниже приведен текст программы. Код КМП-поиска немного отличается от приведенного ранее, потому что здесь используется индексация массивов с 0. 


#include <stdio.h>
#include <stdlib.h>

const int max = 30001;       // максимальная длина строки

void main()
{
   char a[max], b[max];
   int c[max];
   int i, j, k, m, t;
      
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
   scanf("%s %s", a, b);     // вводим данные
   
// первая часть КМП-поиска, заполняем массив c
   c[0] = k = 0;
   for (i = 1; a[i]; i++)
   {
      while (k && a[i] != a[k]) k = c[k-1];
      if (a[i] == a[k]) k++;
      c[i] = k;
   }
   t = i;   // запомним длину первой строки
   
   m = 0;   // в переменной m будет храниться максимальная длина префикса

// вторая часть КМП-поиска
   k = 0;
   for (i = 0; b[i]; i++)
   {
      while (k && b[i] != a[k]) k = c[k-1];
      if (b[i] == a[k]) k++;
      if (k > m) m = k;    // берем максимум по значениям k
      if (k == t) break;   // длина префикса не может быть больше длины строки
   }
   
   printf("%d\n", m);  // вывод ответа
      
   exit(0);
}

Результаты по задаче №3 "Префикс-подстрока" (5 баллов).

НикРезультат
artiwrong answer on test #3
boltwrong answer on test #1
DEathkNIghtS  accepted

Решение задачи №4 "Палиндром" (8 баллов).

    Задача очень простая. Палиндромы делятся на два вида: четной длины и нечетной длины. Мы перебираем позицию для центра подпалиндрома. И для каждой позиции находим максимальный подпалиндром нечетной и четной длины. Сложность алгоритма получается O(n2), что приемлемо при ограничении n <= 2000.

    Текст программы: 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(a,b) (((a)>(b))?(a):(b))

const int max=2001;

int f(int n, char a[], int i, int j)
{
   while (0 <= i - 1 && j + 1 < n && a[i - 1] == a[j + 1]) i--, j++;
   return (j - i + 1);   
}

void main()
{
   int n, i, p, m;
   char a[max];
   
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
   scanf("%s", a);       // вводим данные
   
   n = strlen(a);
   m = 0;
   for (i = 0; i < n; i++)    // перебираем центр
   {
      p = f(n, a, i, i);         // нечетный палиндром
      m = max(m, p);
      if (i + 1 < n && a[i + 1] == a[i])
      {
         p = f(n, a, i, i + 1);  // четный палиндром
         m = max(m, p);
      } 
   }
   
   printf("%d\n", m);    // выводим результат
   exit(0);
}

Результаты по задаче №4 "Палиндром" (8 баллов).

НикРезультат
artiaccepted
boltwrong answer on test #5
DEathkNIghtS  accepted

    Условия задач, тесты и решения вы всегда можете найти на сайте accepted.narod.ru.

Ведущий рассылкой: Виктор Журавлев
Вопросы, пожелания, предложения пишите на мой e-mail.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное