Member 13244314 Ответов: 1

Количество пар наборов

Существует N множеств целых чисел от 1 до K включительно. Найдите число пар множеств, объединение которых содержит все K элементов.

Что я уже пробовал:

я использовал set_union, но он дает TLE, что я должен сделать, чтобы оптимизировать его ?

Patrice T

"что я должен сделать, чтобы оптимизировать его ?"
Что ты наделал ?

OriginalGriff

Не видя соответствующих фрагментов кода, мы даже не можем начать догадываться, как улучшить вашу скорость выполнения или время-это как вы пытаетесь улучшить вкус моего Рогана Джоша через интернет, когда я не могу описать вам текущий вкус!
Используйте виджет" улучшить вопрос", чтобы отредактировать свой вопрос и предоставить более подробную информацию.

1 Ответов

Рейтинг:
2

CPallini

Вам не нужно полностью выполнять объединение каждой пары: откажитесь от процесса вычисления объединения по первому отсутствующему элементу, например

Предполагать 

k=5, s1 = {1,2,5}, s2 = {1,4}


с 3 отсутствует в обоих s1 и s2 тогда вам не нужно полностью выполнять объединение двух наборов, чтобы обнаружить, что они плохие кандидаты.