Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 154 |
| 6 | nor | 153 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.06.2024 13:54:54 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
быть может это поможет Вам: Your text to link here...
спасибо, после 40 минут просмотра и разбора я вроде бы понял эту статью. Но у меня созрел вопрос: чем отличается stack от vector-а? Вроде бы и там и там с одной стороны засовывают и с одной забирают.
Меня часто пытаются переубедить, но мне кажется, что std::stack побыстрее, чем std::vector. Всё-таки std::stack — это не урезанная версия std::vector, и было бы логично реализовать структуру с меньшим функционалом оптимальнее, чем со сложным.
(Правда, это урезанная версия std::deque...)
Лол. Что там убеждать-то, и так видно.
http://codeforces.com/contest/490/submission/8894056 http://codeforces.com/contest/490/submission/8894061
Разница только в параметрах шаблона стека в дереве фенвика. По умолчанию при чем там deque, если не указать иное.
P.S. На segment_tree_t не смотри, он с прошлых посылок остался, с ним даже со вектором внутри стека не заходит.
Было бы логично, но так не делают.
Сравнение не совсем корректно.
std::stack не контейнер, а адаптер. Стандартные контейнеры это std::list, std::vector и std::deque. "Под капотом" у стека всегда есть какой-то контейнер, по умолчанию в g++ это deque.
То есть по сути сравнивая stack и vector ты сравниваешь deque (при условии того, что его пользуют как стек) и vector (при тех же условиях).
В чём же заключается сложность функционала std::vector?
Если нужны только операции взятия и удаления, то лучше использовать стек, ИМХО
Вектор только если нужны еще какие-либо функции
где эта задача находится на онлайн ресурсе"Чистую" задачу я не нашёл, но вот эта задача сводится к поиску максимальной подматрицы.
Вот похожая задача на топкодере: ссылка
сайт contest.bsuir.by там [Practice. Dynamic programming] problem I
сайт [practice.Dynamic programming], задача I.мистер средний
ACMP — фермер 2
вот, спасибо, когда-то решал эту задачу, вспоминал о ней, но не мог найти ее и своего решения. Но решал я эту задачу и совсем не так, как написано на е-максе, а так: линк. Но думаю, для прямоугольников такой метод не прокатит.
Хотя если хранить в каждой клетке динамики 2 стороны прямоугольника, то наверное может пройти.