4509. Вася и множества

 

Васе нравится всё формализировать. Вот например, у бабушки на огороде Вася видит множество овощей, у младшего брата – множество игрушек. А что же будет, если попытаться объединить или пересечь n множеств? Причём больших и разных: вплоть до миллиона элементов (включительно)!

Так как Вася мечтает стать математиком, то свои исследования он решил начать с исследования более простых множеств, а именно множеств целых чисел.

 

Вход. В первой строке задано количество разных множеств n (1 ≤ n ≤ 20). Далее задано n множеств в следующем формате:

·        В первой строке число t (1 ≤ t ≤ 106) – количество чисел в следующей строке.

·        Во второй строке t чисел xi (1 ≤ xi ≤ 106), являющихся элементами множества.

Следующая строка содержит количество запросов m (1 ≤ m ≤ 100). Далее в m строках заданы запросы одного из двух типов:

·        INTERSECTION a b, где 1 ≤ a, b ≤ n

·        UNION a b, где 1 ≤ a, b ≤ n

 

Выход. Для каждого запроса нужно вывести:

·        Для запроса первого типа количество элементов в пересечении a-го и b-го множеств.

·        Для запроса второго типа количество элементов в объединении a-го и b-го множества.

 

Пример входа

Пример выхода

2

2

1 2

2

2 3

2

INTERSECTION 1 2

UNION 1 2

1

3

 

 

 

РЕШЕНИЕ

динамическое программирование - маски

 

Анализ алгоритма

Всего 20 множеств, каждое из них хранит числа от 1 до 106. Объявим массив bitset<1000001> bs[20]; для их хранения. Далее следует выполнить операции над множествами.

 

Элементами множеств являются числа от 1 до 106. Множеств всего не более 20, перенумеруем их начиная с 0. Объявим массив b длины 106, в ячейке b[i] которого будем хранить множество (маску) номеров множеств, которым принадлежит число i. Рассмотрим приведенный пример:

·        число 1 принадлежит нулевому множеству: b[1] = (1 << 0) = 12 = 1;

·        число 2 принадлежит нулевому и первому множеству: b[2] = (1 << 0) || (1 << 1) = 112 = 3;

·        число 3 принадлежит первому множеству: b[3] = (1 << 1) = 102 = 2;

 

Для определения количества элементов в пересечении (объединении) a-го и b-го множеств следует перебрать все числа от 1 до 106 и подсчитать сколько из них принадлежат множествам a и / или b.

 

Реализация алгоритма

Объявим массив bs для хранения 20 множеств.

 

#define MAX 1000001

bitset<MAX> bs[20];

 

Читаем входные данные.

 

scanf("%d", &n);

for(i = 0; i < n; i++)

{

 

Читаем размер множества t.

 

  scanf("%d", &t);

 

Читаем t элементов множества.

 

  while(t--)

  {

    scanf("%d", &x);

 

Во множестве номер i устанавливаем x-ый бит в единицу.

 

    bs[i][x] = 1;

  }

}

 

Читаем количество запросов m.

 

  scanf("%d\n", &m);

  while(m--)

  {

    scanf("%s%d%d\n", s, &t, &x);

    t--; x--;

 

Выполняем операцию заданную в s над множествами номер t и x. В условии задачи нумерация задается с 1. У нас – с нуля. Вычитаем единицу из номеров множеств.

 

    bitset<MAX> cur;

    if(s[0] == 'U')

    {

      cur = bs[t] | bs[x];

      printf("%d\n", cur.count());

    }

    else

    {

      cur = bs[t] & bs[x];

      printf("%d\n", cur.count());

    }

  }

}

 

Реализация алгоритма – множества, битмаски

 

#define MAX 1000000

int b[MAX];

char c[20];

 

Читаем n множеств.

 

scanf("%d", &n);

for(i = 0; i < n; i++)

{

 

Очередное множество содержит t элементов.

 

  scanf("%d", &t);

  for(j = 0; j < t; j++)

  {

    scanf("%d",&a);

 

Число a содержится во множестве номер i. Установим i-ый бит в маске b[a] в единицу.

 

    b[a] |= (1 << i);

  }

}

 

Обрабатваем q запросов.

 

scanf("%d\n", &q);

while(q--)

{

 

Читаем тип запроса.

 

  scanf("%s %d %d\n", c, &x, &y);

  x--; y--;

 

  ans = 0;

 

Проходим по всем числам j от 1 до 106. Если число j принадлежит множеству x и / или y, то к результирующему количеству элементов res прибавляем единицу.

 

  if(c[0] == 'U')

    for(j = 1; j < MAX; j++)

      ans += ((b[j] & (1 << x)) || (b[j] & (1 << y)));

  else

    for(j = 1; j < MAX; j++)

      ans += ((b[j] & (1 << x)) && (b[j] & (1 << y)));

 

Выводим ответ.

 

  printf("%d\n", ans);

}