|
531 / 272 / 220
Регистрация: 14.11.2016
Сообщений: 1,052
|
|
Std::set проглатывает std::string{"b"}28.09.2019, 18:11. Показов 1377. Ответов 2
Метки нет (Все метки)
Олимпиадное задание.
Задание
Мультиклавиатура — это обычная клавиатура с множеством выходов, каждый из которых можно подключить к одному персональному компьютеру.
Недавно в серверную одной очень большой и очень секретной конторы установили мультиклавиатуру. Последняя была подключена к N компьютерам. Таким образом, при нажатии клавиши, символ печатается сразу на всех машинах. Но вот незадача: кабели мультиклавиатуры оказались чрезвычайно хлипкими, и если отсоединить кабель от компьютера, то подключить его вновь не удастся. Рабочий день уже в самом разгаре, и срочно требуется напечатать на каждом компьютере по заданной строке. В конце набора на каждом компьютере должна быть набрана в точности заданная строка. Определите, за какое минимальное количество нажатий клавиш мультиклавиатуры возможно напечатать все заданные строки на компьютерах. Входные данные В первой строке входного файла задано целое число T — количество тестов (1 ≤ T ≤ 100). Далее следует T блоков. В первой строке блока задано целое число N — количество компьютеров, к которым подключена мультиклавиатура (1 ≤ N ≤ 10^5). В каждой i-ой из следующих строк задана непустая строка Si-я , которую требуется напечатать на i-ом компьютере. Выходные данные В выходной файл выведите T строк, в i-й строке — ответ на i-й тестовый пример. Если напечатать заданные строки невозможно, ответом должно быть слово Impossible. В противном случае требуется вывести одно целое число — минимальное количество нажатий клавиш мультиклавиатуры, с помощью которых можно напечатать заданные строки. Пример input.txt файла
2
3 aba abacaba abca 2 hello hell Пример output.txt файла
Impossible
5 Реализовал код с использованием vector, и с использованием set. КОД
#include <iostream>
#include <fstream> #include <string> #include <algorithm> #include <set> #include <vector> #include <cctype> #define TEST // Выбрать контейнер сдесь!!! //#define SET #define VECTOR struct greater { greater(void) = default; bool operator()(const std::string &lhs, const std::string &rhs) { return (lhs.size() > rhs.size()); } }; int main() { std::fstream fin{ "input.txt", std::ios_base::in }; std::fstream fout{ "output.txt", std::ios_base::out | std::ios_base::trunc }; std::size_t testNums{}; // Считываем кол-во тестов fin >> testNums; #ifdef TEST std::cout << "All tests: " << testNums << std::endl; #endif // Идем по каждому из тестов for (std::size_t i{}; i < testNums; ++i) { #ifdef TEST std::cout << "\n________ Test #" << (i + 1) << " ________" << std::endl; #endif // Считываем кол-во строк std::size_t strNums{}; fin >> strNums; #ifdef TEST std::cout << "All strings: " << strNums << std::endl << std::endl; #endif #ifdef SET std::set<std::string, greater> data{}; // строки отсортированные по размеру (от больших к меньшим) #endif #ifdef VECTOR std::vector<std::string> data{}; #endif { // Читаем строки и сохраняем в data std::string str{}; for (std::size_t j{}; j < strNums; ++j) { fin >> str; #ifdef TEST std::cout << "["<< (j + 1) <<"] Readed string: '" << str << "'" << std::endl; #endif #ifdef SET data.insert(std::move(str)); #endif #ifdef VECTOR data.emplace_back(std::move(str)); #endif } } // Сортировка строк по размеру. От длинных к коротким. #ifdef VECTOR std::sort(data.begin(), data.end(), greater{}); #endif #ifdef TEST std::cout << std::endl; std::cout << "\tData: " << std::endl; for (auto &it : data) { std::cout << "> '" << it << "'" << std::endl; } std::cout << std::endl; #endif // Получаем первую самую длинную строку auto itData = data.cbegin(); auto& sLongest = *itData++; // самая длинная строка bool isEnter = true; // Ввод строк возможен? // Идем по оставшимся строкам while (itData != data.cend()) { #ifdef TEST std::cout << "> Comparsion '" << sLongest << "' & '" << *itData << "'" << std::endl; #endif // Сравниваем первую строки по символьно с длинной строкой sLongest for (auto it = sLongest.cbegin(), it2 = itData->cbegin(); (it != sLongest.cend()) && (it2 != itData->cend()); ++it, ++it2) { if (*it != *it2) { // Если символы не сошлись, значит все строки ввести не получится #ifdef TEST std::cout << "!!! isEnter = false !!!" << std::endl; #endif isEnter = false; break; } } if (!isEnter) { break; } ++itData; // переход к следующей строке } if (!isEnter) { // Если строку ввести не возможно fout << "Impossible" << std::endl; #ifdef TEST std::cout << "ANSWER: " << "Impossible" << std::endl << std::endl; #endif } else { // Если строку ввести возможно // !!! Количество символов в самой длинной строке и будет кол-вом минимальных нажатий !!! fout << sLongest.size() << std::endl; #ifdef TEST std::cout << "ANSWER: " << sLongest.size() << std::endl << std::endl;; #endif } } #ifdef TEST std::system("pause"); #endif } Сделал тестовый набор. Тестовый набор (input.txt)
2
2 ab aba 3 ab a b НО, если использовать set, тогда во втором наборе теста читаются все строки, но почему-то set проглатывает b и её не обнаруживается в наборе и выдает output файл с ответами 3 2. Почему? С vector всё работает нормально. Для смены контейнеров set на vector, vector на set юзайте дефайны после инклюдов.
0
|
|
| 28.09.2019, 18:11 | |
|
Ответы с готовыми решениями:
2
ошибка error: cannot convert 'std::string {aka std::basic_string<char>}' to 'std::string* {aka std::basic_stri
STL std::set, std::pair, std::make_pair |
|
Вездепух
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,220
|
||
| 28.09.2019, 18:43 | ||
Сообщение было отмечено anapshy как решение
Решениеstd::set написали предикат greater который сравнивает только длины строк. Все строки одинаковой длины такой предикат считает одинаковыми. Разумеется, в ваш std::set теперь невозможно вставить больше одной строки каждой длины. Вставили "a". После этого "b" уже не вставится.
1
|
||
|
531 / 272 / 220
Регистрация: 14.11.2016
Сообщений: 1,052
|
|
| 28.09.2019, 19:13 [ТС] | |
|
TheCalligrapher, благодарю
0
|
|
| 28.09.2019, 19:13 | |
|
Помогаю со студенческими работами здесь
3
Запрошено преобразование от ‘const std::string*’ к нескалярному типу ‘std::string’
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование
. \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json>
Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом.
# Check if. . .
|
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так:
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347
Основана на STM32F303RBT6.
На борту пять. . .
|
Символьное дифференцирование
igorrr37 13.02.2026
/ *
Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет
значение производной при заданном х
Логарифм записывается как: (x-2)log(x^2+2) -. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|