本文共 1191 字，大约阅读时间需要 3 分钟。
为每个不同的集合分配一个唯一的ID，则每个集合都可以表示成所包含元素的ID集合，这样就可以用STL的set<int>来表示了，而整个栈则是一个stack<int>。
#include #include #include #include #include #include #include #include using namespace std;#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())int T,n;typedef set Set;map IDcache; //将集合映射成IDvector Setcache; //根据ID取集合int ID(Set x){ if(IDcache.count(x)) return IDcache[x]; Setcache.push_back(x); return IDcache[x] = Setcache.size() - 1;}int main(){ scanf("%d",&T); while(T--){ char op[10]; IDcache.clear(); //其实不用clear也没关系 只是取个ID而已 对结果没影响 Setcache.clear(); //速度反而会更快 stack s; cin>>n; while(n--){ scanf("%s",&op[0]); //cin读取大规模数据太慢 if(op[0] == 'P') s.push(ID(Set())); else if(op[0] == 'D') s.push(s.top()); else{ Set a = Setcache[s.top()];s.pop(); Set b = Setcache[s.top()];s.pop(); Set x; if(op[0] == 'U') set_union(ALL(a),ALL(b),INS(x)); if(op[0] == 'I') set_intersection(ALL(a),ALL(b),INS(x)); if(op[0] == 'A'){ x = b,x.insert(ID(a));} // 插入的是ID 不像上面是集合操作 s.push(ID(x)); } printf("%d\n",Setcache[s.top()].size()); } printf("***\n"); } return 0;}
转载于:https://www.cnblogs.com/JingwangLi/p/10202742.html