5 集合栈计算机 (The SetStack Computer UVa 12096)

这道例题书上的代码不全,我来补齐。

这章出现了n多新内容,紫书上一掠而过,我是不是该去读一读C++ primer plus?

//#define LOCAL#include<set> //使用set容器#include<iostream>//使用c++输入输出流#include<map>//使用map映射#include<vector>//使用vector不定长数组#include<stack>//使用stack栈#include<algorithm>//使用算法set_union set_intersectionusing namespace std;//将标准名称空间std导入默认名称空间typedef set<int> Set;map<Set,int> IDcache; //把集合映射成IDvector<Set> Setcache; //根据ID取集合//查找给定集合x的ID。如果找不到,分配一个新IDint 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() //定义ALL宏,表示“所有的内容”#define INS(x) inserter(x,x.begin())//定义INS宏,表示“插入迭代器”int main() {#ifdef LOCALfreopen("lt5-5.in", "r", stdin);freopen("lt5-5.out", "w", stdout);#endifint t;//声明整型变量t,测试样例的数量cin>>t;//读入测试样例数量while(t–){stack<int> s; //定义栈sint n;//声明整型变量n,,样例中包含的操作数量cin >> n;//读入样例中包含的操作数量for(int i = 0; i < n; i++) { //依次执行操作,并输出操作后栈顶集合的大小string op; //声明字符串变量opcin >> op; //输入流赋值opif (op[0] == 'P') s.push(ID(Set()));//如果指令为PUSH,将空集压入栈else if (op[0] == 'D') s.push(s.top());//如果指令为DUP,将栈顶元素压入栈else {Set x1 = Setcache[s.top()]; s.pop();//将栈顶元素赋值给集合变量x1,并弹出栈顶元素Set x2 = Setcache[s.top()]; s.pop();//将栈顶元素赋值给集合变量x2,并弹出栈顶元素Set x;//声明集合变量x,用于存储指令操作结果if (op[0] == 'U') set_union (ALL(x1), ALL(x2), INS(x));//如果指令为UNION,使用set_union,把x1,x2的并集赋值给xif (op[0] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));//如果指令为INTERSECT,使用set_intersection,把x1,x2的交集赋值给xif (op[0] == 'A') { x = x2; x.insert(ID(x1)); }//如果指令为ADD,首先把x2赋值给x,然后使用set中的insert把x1插入xs.push(ID(x));//结果入栈}cout << Setcache[s.top()].size() << endl; //输出栈顶集合的元素数量后换行}cout << "***" << endl;//样例操作结束后输出“***”并换行}return 0;}

没有伞的孩子必须努力奔跑!

5 集合栈计算机 (The SetStack Computer UVa 12096)

相关文章:

你感兴趣的文章:

标签云: