Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 17:54:27 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
быть может это поможет Вам: Your text to link here...
спасибо, после 40 минут просмотра и разбора я вроде бы понял эту статью. Но у меня созрел вопрос: чем отличается stack от vector-а? Вроде бы и там и там с одной стороны засовывают и с одной забирают.
Меня часто пытаются переубедить, но мне кажется, что std::stack побыстрее, чем std::vector. Всё-таки std::stack — это не урезанная версия std::vector, и было бы логично реализовать структуру с меньшим функционалом оптимальнее, чем со сложным.
(Правда, это урезанная версия std::deque...)
Лол. Что там убеждать-то, и так видно.
http://codeforces.me/contest/490/submission/8894056 http://codeforces.me/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 стороны прямоугольника, то наверное может пройти.