http://acm.hust.edu.cn/vjudge/contest/128220#problem/E
第五题我看了很久，之前就是因为第五题理解不了，才重新看了一边前面的题目，没想到第二次到了这里，还是很困惑。
先说说思路，思路还是非常清晰的
直接分成几个if（else if）—》其中U I A操作是有重复的—》先将重复的部分写在前面，再进行判断没最后输出结果
但是 这里就遇到了几个问题了
！空集如何表示？
！{} 和{{}}一样吗？
！用什么去储存空集？
！各种操作的函数是什么？
！各个空集之间如何进行区分？
以下为源代码
#include<iostream>//I/O
#include<string>//string
#include<set>//集合
#include<map>映射
#include<stack>栈
#include<vector>vector容器
#include<algorithm>//set_union ： 并集 set_intersection ： 交集 set_difference ： 差集
using namespace std;
typedef set<int> Set;
//定义一个int型集合对象Set,当前没有任何元素.
map<Set,int> IDcache;//把集合映射成ID
vector<Set> Setcache;
//查找集合的ID.如果找不到，分配一个新ID
int ID(Set x)
{
if(IDcache.count(x)) return IDcache[x];
Setcache.push_back(x);
return IDcache[x]=Setcache.size()-1;
}
#define All(x) x.begin(),x.end()//定义了有关于迭代器的宏
#define INS(x) inserter(x,x.begin())
int main()
{
int T;
cin>>T;
while(T--)
{
stack<int> s;//定义栈
int i,n;
cin>>n;
for(i=0; i<n; i++)
{
string op;
cin>>op;
if(op[0]=='P') s.push(ID(Set()));//插入ID
else if(op[0]=='D') s.push(s.top());
else
{
Set x1=Setcache[s.top()];
s.pop();
Set x2=Setcache[s.top()];
s.pop();
Set x;
if(op[0]=='U') set_union(All(x1),All(x2),INS(x));
if(op[0]=='I') set_intersection(All(x1),All(x2),INS(x));
if(op[0]=='A')
{
x=x2;
x.insert(ID(x1));
}
s.push(ID(x));
}
cout<<Setcache[s.top()].size()<<endl;//输出ID对应的集合的大小
}
}
return 0;
}
现在 可以解答了
！空集如何表示？
Set()
！{} 和{{}}一样吗？
并不，所以对应id不同
！用什么去储存空集？
用vector 每个id对应一个集合 每个集合也因为做了id的判断所以只会储存一次
！！那么这里有有个问题 既然只储存一次，那如何进行那些交并集的操作呢？
其实那些操作是通过栈里的整数（id）调用vector中对应的集合，同意集合如果需要，可以进行任意次数的调用
！各种操作的函数是什么？
这个对于小白的我有一些困难，就把标程中的写一些
！！栈 push() pop() top()
！！vector push_back() size()(虽然不只是关于vector容器)
！！集合 set_union(迭代1，迭代2，inserter（迭代3）) set_intersection(同上)
！各个空集之间如何进行区分？
用映射给不同集合分配不同id，并存在vector里，随时进行调用
一开始理解不了的地方在
Setcache.push_back(x);
return IDcache[x]=Setcache.size()-1;
cout<<Setcache[s.top()].size()<<endl;
这两句，一直以为是这样的
0 1 2 3......
0 {}
1 {{}}
2 {{{}}}
...
实际上是这样的
0 1 2 3
{} {{}} {{{}}} {{{{}}}}...
而栈里是这样的
|0|1|3|2|1|0|1|
所以栈里的数字对应的其实就是相应的id，取vector中相应的唯一set，当需要合并的时候 是取set两个变量来以stack里的数值来取出vector里的set
下面是网上抄的一段摘要 ——————————————————————————————
这道题是一个编码问题，即将某种数据结构通过一定的方法转化为独特的整数。这样就可以用整数来进行操作，大大简化了程序。
对于这道题中的集合来说，一个集合包含了0或多个集合，并且可能有多层嵌套，无法用STL的set来模拟。但是我们可以给每一种集合分配一个ID。比如我们给{}分配1，{{}}就可以表示成{1}，我们给他分配2。{{},{}}就可以表示为{1, 1}，我们给他分配3。{ {} , {{}} , {{},{}} }就可以表示为{1, 2, 3}，我们可以给这个集合分配4。这样，我们就可以把集合的集合变成整数的集合，即便有再多嵌套，都可以用一个简单的整数来表示。
于是在读入操作的时候，我们判断新生成的集合是否出现过。如果出现过，直接用它对应的ID替换他。如果没出现过，则给他分配一个新的ID，并把它存在数组中ID的位置上
判断最顶部集合的大小，只需要根据ID去数组中找到这个集合，并查看这个集合中多少个元素。
——————————————————————————————————————————
大概就是这样了 至于迭代器，明天再加深了解，今天得做完这章。
