LTF►XLor

The Setstack Computer UVa12096

本题的思想很重要，题意中的集合概念较抽象，因此对每种集合编号。 stack为题意所描述的stack computer，存放着抽象集合对应的唯一编号，而编号所对应的集合里面也存放着集合的编号，形成了抽象集合的嵌套关系。 函数getID(set)：set ==> 编号，通过映射ID将每个集合对应唯一编号，以此保证集合元素的互异性，接口返回编号或者分配新的编号。 向量getSet：编号 ==> set，通过编号找到对应set，获取集合大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <iterator>
#include <algorithm>
using namespace std;
map<set<int>, int> ID;
vector<set<int>> getSet;

int getID(set<int> x)
{
	if (ID.count(x))
		return ID[x];
	getSet.push_back(x);
	return ID[x] = getSet.size() - 1;
}
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		stack<int> s;
		int n;
		cin >> n;
		while (n--)
		{
			char cmd[10];
			cin >> cmd;
			if (cmd[0] == 'P')
				s.push(getID(set<int>()));
			else if (cmd[0] == 'D')
				s.push(s.top());
			else
			{
				set<int> x1 = getSet[s.top()];
				s.pop();
				set<int> x2 = getSet[s.top()];
				s.pop();
				set<int> x;
				if (cmd[0] == 'U')
					set_union(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x,x.begin()));
				else if (cmd[0] == 'I')
					set_intersection(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x, x.begin()));
				else if (cmd[0] == 'A')
				{
					x = x2;
					x.insert(getID(x1));
				}
				s.push(getID(x));
			}
			cout << getSet[s.top()].size() << endl;
		}
		cout << "***" << endl;
	}
	return 0;
}