首页 > 代码库 > UVa 12096 (STL) The SetStack Computer

UVa 12096 (STL) The SetStack Computer

2024-11-05 21:05:39   204人阅读

题意：

有一个集合栈计算机，栈中的元素全部是集合，还有一些相关的操作。输出每次操作后栈顶集合元素的个数。

分析：

这个题感觉有点抽象，集合还能套集合，倒是和题中配的套娃那个图很贴切。

把集合映射成ID，就可以用 stack<int>来模拟题中的集合栈，然后用 vector<Set> 来根据下标进行集合的索引。

代码虽短，但还须多体会。

技术分享
 1 #include <cstdio> 2 #include <string> 3 #include <vector> 4 #include <stack> 5 #include <set> 6 #include <map> 7 #include <iostream> 8 #include <algorithm> 9 using namespace std;10 11 typedef set<int> Set;12 map<Set, int> IDcache;13 vector<Set> Setcache;14 15 #define ALL(x) x.begin(),x.end()16 #define INS(x) inserter(x,x.begin())17 18 int ID(Set x)19 {20     if(IDcache.count(x)) return IDcache[x];21     Setcache.push_back(x);22     return IDcache[x] = Setcache.size() - 1;23 }24 25 int main()26 {27     //freopen("in.txt", "r", stdin);28 29     int T;30     scanf("%d", &T);31     while(T--)32     {33         stack<int> s;34         int n;35         scanf("%d", &n);36         for(int i = 0; i < n; ++i)37         {38             string op;39             cin >> op;40             if(op[0] == ‘P‘) s.push(ID(Set()));41             else if(op[0] == ‘D‘) s.push(s.top());42             else43             {44                 Set x1 = Setcache[s.top()]; s.pop();45                 Set x2 = Setcache[s.top()]; s.pop();46                 Set x;47                 if(op[0] == ‘U‘) set_union(ALL(x1), ALL(x2), INS(x));48                 if(op[0] == ‘I‘) set_intersection(ALL(x1), ALL(x2), INS(x));49                 if(op[0] == ‘A‘) { x = x2; x.insert(ID(x1)); }50                 s.push(ID(x));51             }52             printf("%d\n", Setcache[s.top()].size());53         }54 55         puts("***");56     }57 58     return 0;59 }
代码君

 

UVa 12096 (STL) The SetStack Computer


联系
我们