-6

Всем, привет. Будучи школьником 10 класса, я активно готовлюсь к олимпиадам по информатике, в т.ч. по программированию( Это ведь основная часть)
Для подготовки я часто решаю задачи прошлых лет. Вот недавно я стал решать задачи 2017г. Личного чемпионата самарского университета среди новичков. И нашел таки 2 задачи, над которыми 3 вечера - клянусь, и никак, ну не могу решить.
Хотел бы вам представить это задачи, был бы очень рад , если бы мне помогли решить их.
Не настаиваю на комментариях кода, я люблю сам в нем разбираться, буду не меньше рад голому коду без комментариев. С битовыми операциями у меня всегда проблемы, сложная для меня тема, а в первой задаче не могу правильно составить двойной цикл( как мне кажется, который нужен) так, чтобы при любых данных все корректно отрабатывало.
Ниже приведены сами задачи, решение требуется на С++, но я и не против другого языка, мне главное суть понять)
Стандартный ввод осуществляется с файла input.txt, вывод - output.txt. Спасибо всем за потраченное время, да и просто, что прочитали этот текст :)
Есть наработки, однако они типичные - подключить такие то библиотеки, создать файлы вывода, прочитать переменные. Более сложную часть не получается релизовать, взрыв мозга :(

Задача 1[![Вторая

вторая задача

7
  • Во второй задаче вам видимо сначала нужно посчитать за один проход побитовое И для всех чисел, а потом за второй проход пробовать удалять из результата по одному элементу, правда вот как удалять я не знаю, возможно понадобится сделать побитовое исключающее или(XOR) с удаляемым элементом или что-нибудь типа того. Я бы с такого подхода начал.
    – vt-egorov
    21 сен 2018 в 15:35
  • К первой: k элементов с максимальной разностью a-итого и b-итого (Без модуля соответственно), отправите если я не прав. 21 сен 2018 в 16:21
  • @MrBin Возьмём a1=5,b1=1. a2=2000,b2=1500; Разность максимальная во втором случае, а отношение в первом. И самое сложное, что надо брать еще не одну строку, а взять такие k штук a и b, чтобы они были с одной строки 21 сен 2018 в 16:54
  • Добавьте ограничения кстати - по памяти и по времени
    – vt-egorov
    21 сен 2018 в 17:47
  • 1
    Вопрос следует разбить на два отдельных, иначе он подлежит закрытию
    – MBo
    21 сен 2018 в 18:11

1 ответ 1

3

Для решения второй задачи соображения следующие:

  1. Те битовые позиции, в которых элементы массива содержат 2 и более нулевых битов, на решение задачи не влияют - какое бы мы число ни вычеркнули, результат общего "И" в этих позициях будет содержать нулевой бит.

  2. Те битовые позиции, в которых элементы массива не содержат нулевых битов, на решение задачи не влияют - какое бы мы число ни вычеркнули, результат общего "И" в этих позициях будет содержать единичный бит.

  3. Поэтому нас интересуют только те битовые позиции, в которых элементы массива имеют ровно 1 нулевой бит. Нам надо найти элемент массива, содержащий самый "дорогой" набор нулей в этих позициях.

    Если интересующие нас битовые позиции выразить единицами в маске mask, то вычеркивать надо элемент a[i], дающий максимальное mask & ~a[i].

В два прохода задача решается элементарно: первым проходом определяем интересующие нас битовые позиции, а вторым проходом находим искомый элемент. (Вычислить результирующее значение "И" можно в рамках этих двух проходов - третьего не нужно.)

Примеры, к сожалению, приведены неинтересные. Для второго примера нас будет интересовать только бит 4 и вычеркивать надо будет именно число 211, что позволит нам "спасти" бит 4 и получить результат 8.

int main()
{
  const unsigned N = 7;
  unsigned a[N] = { 123, 211, 1390, 121, 984, 184, 911 };

  unsigned has_zero = 0, has_second_zero = 0;

  for (unsigned i = 0; i < N; ++i)
  {
    unsigned inverse = ~a[i];
    has_second_zero |= inverse & has_zero;
    has_zero |= inverse;
  }

  unsigned mask = has_zero & ~has_second_zero;

  unsigned total_and = -1, max_zeros = 0, exclude = -1;

  for (unsigned i = 0; i < N; ++i)
  {
    total_and &= a[i];

    unsigned zeros = mask & ~a[i];
    if (zeros > max_zeros)
    {
      max_zeros = zeros;
      exclude = a[i];
    }
  }

  total_and |= mask & ~exclude;

  std::cout << total_and << std::endl;
}

Но по здравом размышлении становится ясно, что максимум значения mask & ~a[i] будет очевидно достигаться на том значении a[i], которое содержит самый старший из интересующих нас нулевых битов. Если на первом проходе мы будем запоминать, какой элемент массива дал нам нулевой бит в каждой битовой позиции, то задачу можно будет решить за один проход по массиву a[]. Для хранения дополнительной информации нам понадобится массив размера log2 106, т.е. 20

int main()
{
  const unsigned N = 7;
  unsigned a[N] = { 123, 211, 1390, 121, 984, 184, 911 };

  const unsigned N_BITS = 20;
  struct Z { unsigned n, i; } zeros[N_BITS] = {};

  unsigned total_and = -1, mask = 0;

  for (unsigned i = 0; i < N; ++i)
  {
    unsigned v = a[i];
    total_and &= v;

    for (unsigned b = 0, test = 1; b < N_BITS; ++b, test <<= 1)
      if ((v & test) == 0)
        if (++zeros[b].n == 1)
        {
          zeros[b].i = i;
          mask |= test;
        }
        else
          mask &= ~test;
  }

  for (unsigned b = N_BITS; b-- > 0; )
    if (zeros[b].n == 1)
    {
      total_and |= mask & ~a[zeros[b].i];
      break;
    }

  std::cout << total_and << std::endl;
}
0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.