UVa 12096 (STL) The SetStack Computer

题意:

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

分析:

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

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

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

 #include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std; typedef set<int> Set;
map<Set, int> IDcache;
vector<Set> Setcache; #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) int ID(Set x)
{
if(IDcache.count(x)) return IDcache[x];
Setcache.push_back(x);
return IDcache[x] = Setcache.size() - ;
} int main()
{
//freopen("in.txt", "r", stdin); int T;
scanf("%d", &T);
while(T--)
{
stack<int> s;
int n;
scanf("%d", &n);
for(int i = ; i < n; ++i)
{
string op;
cin >> op;
if(op[] == 'P') s.push(ID(Set()));
else if(op[] == 'D') s.push(s.top());
else
{
Set x1 = Setcache[s.top()]; s.pop();
Set x2 = Setcache[s.top()]; s.pop();
Set x;
if(op[] == 'U') set_union(ALL(x1), ALL(x2), INS(x));
if(op[] == 'I') set_intersection(ALL(x1), ALL(x2), INS(x));
if(op[] == 'A') { x = x2; x.insert(ID(x1)); }
s.push(ID(x));
}
printf("%d\n", Setcache[s.top()].size());
} puts("***");
} return ;
}

代码君

上一篇:短信验证倒计时60s


下一篇:【字符编码】字符编码 && Base64编码算法