STL初步:栈,队列和优先队列 一时失言乱红尘 2022-11-27 12:15 166阅读 0赞 ### 集合栈计算机(The SetStack Computer) ### 有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈,并且支持以下操作: * PUSH:空集“\{\}”入栈 * DUP:把当前栈顶元素复制一份后再入栈 * UNION:出栈两个集合,然后把两者的并集入栈 * INTERSECT:出栈两个集合,然后把二者的交集入栈 * ADD:出栈两个集合,然后把先出栈的集合加入到后出栈的集合中,把结果入栈 每次操作后,输出栈顶集合的大小(即元素个数)。例如栈顶元素是A=\{ \{\}, \{ \{\}\} \}, 下一个元素是B=\{ \{\}, \{ \{ \{\}\}\} \},则: * UNION操作将得到\{ \{\}, \{ \{\}\}, \{ \{ \{\}\}\} \},输出3. * INTERSECT操作将得到\{ \{\} \},输出1 * ADD操作将得到\{ \{\}, \{ \{ \{\}\}\}, \{ \{\}, \{ \{\}\} \} \},输出3. 样例输入 6 PUSH PUSH UNION PUSH PUSH ADD 样例输出 0 0 0 0 0 1 #include<set> #include<stack> #include<iostream> #include<map> #include<vector> #include<algorithm> using namespace std; typedef set<int> Set; map<Set,int> IDcache; //把集合映射为id vector<Set> SetCache; //根据id取集合 stack<int> s; //题目中的栈 int ID(Set x) //查找给定集合的id。如果找不到,分配一个新id { if(!IDcache.count(x)) { SetCache.push_back(x); //添加新集合 IDcache[x]=SetCache.size()-1; } return IDcache[x]; } int n; int main() { cin>>n; while(n--) { string exec; cin>>exec; if(exec[0] == 'P') s.push(ID(Set())); else if(exec[0] == 'D') s.push(s.top()); else { Set x1 = SetCache[s.top()]; s.pop(); Set x2 = SetCache[s.top()]; s.pop(); Set x; if(exec[0] == 'U') set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));//!!!inserter if(exec[0] == 'I') set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));//!!!inserter if(exec[0] == 'A'){ x=x2; x.insert(ID(x1)); } s.push(ID(x)); } cout<<SetCache[s.top()].size()<<endl; } } 队列是符合“先进先出”原则的“公平队列”。 STL队列定义在头文件`<queue>`中,可用`queue<int>s`方式定义,用push()和pop()进行元素的入队和出队操作,front()取队首元素,但不删除。 ### 团体队列(Team Queue) ### 有t个团队的人正在排一个长队。每次新来一个人时,如果他有队友在排队,那么这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队,则他会排到长队的队尾。 输入每个团队中所有队员的编号,要求支持如下3种指令(前两种指令可以穿插进行) * ENQUEUE x:编号为x的人进入长队 * DEQUEUE: 长队列队首出队 * STOP: 停止模拟 对于每一个DEQUEUE指令,输出出对人的编号. #include<cstdio> #include<queue> #include<map> using namespace std; const int maxt = 1000 + 10; int main() { int t, kase = 0; while (scanf("%d", &t) == 1 && t) { map<int, int>team; //记录所有人的团队编号 for (int i = 0; i<t; i++) //team[x]表示编号为x的人所在的团队编号 { int n, x; scanf("%d", &n); while (n--) { scanf("%d", &x); team[x] = i; } } printf("Scenario #%d\n", ++kase); queue<int>q, q2[maxt]; //模拟 for(;;) { int x; char cmd[10]; scanf("%s", cmd); if (cmd[0] == 'S') { break; } else if (cmd[0] == 'D') { int t = q.front(); printf("%d\n", q2[t].front()); //打印首元素 q2[t].pop(); //首元素出队(先进先出) if (q2[t].empty()) q.pop(); //团队t全体出队列 } else if (cmd[0] == 'E') { scanf("%d", &x); int t = team[x]; if (q2[t].empty()) //团队t进入队列 { q.push(t); } q2[t].push(x); } } printf("\n"); } return 0; } ###### 优先队列 ###### 先出队列是队列中优先级最高的元素,STL中用`priority_queue<int>pq`来声明,出队方法为top()。 自定义类型也可以组成优先队列,但必须为每个元素定义一个优先级。 例如,要实现一个“个位数大的整数优先级反而小”的优先队列,可以定义一个结构体cmp,重载“()”运算符,用`priority_queue<int,vector<int>,cmp> pq`的方式定义。 struct cmp { bool operator() (const int a,const int b)const //a的优先级比b小时返回true { return a%10>b%10; } }; 简便定义方法: priority_queue<int,vector<int>,great<int> >pq 注:可用push()和pop()进行元素的入队和出队操作,top()取队首元素,但不删除。 ### 丑数 ### 丑数指不能被2,3,5以外其他素数整除的数。把丑数从小到大排列起来,结果如下: 1,2,3,4,5,6,8,9,10,12,15… 求第1500个丑数。 /*最小的丑数是1,而对于任意丑数,2x,3x,5x也都是丑数。可以用一个优先队列保存所有已生成的丑数,每次取出最小的丑数,生成3个新的丑数。 */ #include<iostream> #include<vector> #include<queue> #include<set> using namespace std; typedef long long ll; const int coeff[3]={ 2,3,5}; int main() { priority_queue<ll,vector<ll>,greater<ll> > pq; set<ll> s; pq.push(1); s.insert(1); for(int i=1;;i++) { ll x=pq.top(); pq.pop(); if(i==1500) { cout<<"The 1500'th ugly number is "<<x<<".\n"; break; } for(int j=0;j<3;j++) { ll x2=x*coeff[j]; if(!s.count(x2)) { s.insert(x2); pq.push(x2); } } } return 0; }
还没有评论,来说两句吧...