Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя Jmar4

Как решить данную задачу?
Автор Jmar4, история, 7 лет назад, По-русски

http://codeforces.me/contest/844/problem/B Не смог ее решить контесте, правильно. Но и не понимаю, как это сделать. Возможно я не прав, в том смысле, что не понимаю зачем нужен блог, прошу не гневаться если это так и сюда нельзя задавать такие вопросы. Так же прошу не приводить полное решение, а лишь навести на мысль, ссылку на мат тему, или просто ее название.

Заранее спасибо ))

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Для каждой строки и для каждого столбца посчитаем количество единиц и нулей в них.

Сколькими способами можно выбрать непустое подмножество из K элементов?

Спойлер

Каждый элемент матрицы будет подсчитан дважды, поэтому вычтем m*n.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    То есть циклы для 0 и 1, в каждом из которых от 1 до k, где k счетчик в циклах для 0, 1? Тогда O(n)=V^3, где V=m*n, я правильно понял?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Нет. Пусть в множестве есть K элементов. Выбрать непустое подмножество можно 2^K — 1 способами.

      Посчитать количество единиц и нулей в каждой строке и в каждом столбце можно за О(n*m)

      code

      ответом будет являться сумма 2^row[i][0] — 1 + 2^row[i][0] — 1 по всем i + сумма 2^col[j][0] — 1 + 2^col[j][1] — 1 по всем j

      Ну и вычесть n*m.

      → Ответить