| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
http://codeforces.me/contest/844/problem/B Не смог ее решить контесте, правильно. Но и не понимаю, как это сделать. Возможно я не прав, в том смысле, что не понимаю зачем нужен блог, прошу не гневаться если это так и сюда нельзя задавать такие вопросы. Так же прошу не приводить полное решение, а лишь навести на мысль, ссылку на мат тему, или просто ее название.
Заранее спасибо ))
Для каждой строки и для каждого столбца посчитаем количество единиц и нулей в них.
Сколькими способами можно выбрать непустое подмножество из K элементов?
2^k — 1
Каждый элемент матрицы будет подсчитан дважды, поэтому вычтем m*n.
То есть циклы для 0 и 1, в каждом из которых от 1 до k, где k счетчик в циклах для 0, 1? Тогда O(n)=V^3, где V=m*n, я правильно понял?
Нет. Пусть в множестве есть K элементов. Выбрать непустое подмножество можно 2^K — 1 способами.
Посчитать количество единиц и нулей в каждой строке и в каждом столбце можно за О(n*m)
row[i][0] += (a[i][j] == 0); row[i][1] += (a[i][j] == 1); col[j][0] += (a[i][j] == 0); col[j][1] += (a[i][j] == 1);
ответом будет являться сумма 2^row[i][0] — 1 + 2^row[i][0] — 1 по всем i + сумма 2^col[j][0] — 1 + 2^col[j][1] — 1 по всем j
Ну и вычесть n*m.