You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

48 lines
1.3 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
//UVA12096 集合栈计算机
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) //注意宏的括号和inserter
typedef set<int> Set;
map<Set, int> IDCache;
vector<Set> setCache;
int t, n;
char cmd[10];
int getID(Set s) {
if (IDCache.count(s))return IDCache[s];
setCache.push_back(s); //将新集合加入Setcache
return IDCache[s] = setCache.size() - 1;//将ID加入map 同时返回新分配的ID值
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
stack<int> s;
while (n--) {
scanf(" %s", &cmd);
if (cmd[0] == 'P')s.push(getID(Set()));
else if (cmd[0] == 'D')s.push(s.top());
else {
Set s1 = setCache[s.top()];
s.pop();
Set s2 = setCache[s.top()];
s.pop();
Set x;
if (cmd[0] == 'U')set_union(ALL(s1), ALL(s2), INS(x));
if (cmd[0] == 'I')set_intersection(ALL(s1), ALL(s2), INS(x));
if (cmd[0] == 'A') {
x = s2;
x.insert(getID(s1));
}
s.push(getID(x));
}
printf("%d\n", setCache[s.top()].size());
}
puts("***");
}
}