uva 12096 - The SetStack Computer(STL) - c++编程基础

TOP

uva 12096 - The SetStack Computer(STL)

2015-07-20 17:50:31 来源: 作者: 【大中小】浏览:1次

Tags：uva 12096 The SetStack Computer STL

题目链接：uva 12096 - The SetStack Computer

题目大意：一个栈，有5种操作；

PUSH：向栈中放一个空集合。
DUP：复制栈顶集合。
UNION：取栈顶的两个集合，取并集后放回。
INTERSECT：取栈顶的两个集合，取交集后放回。

ADD：取栈顶两个集合，将第一个集合作为元素放到第二个集合中，并将第二个集合放回栈。

每次操作后输出栈定集合中元素的个数。

解题思路：将所有集合映射成一个值，用map记录，然后模拟操作即可。

#include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            using namespace std; typedef set
           
             sint; typedef set
            
             ::iterator iter; int hn; stack
             
               stak; map
              
                g; void hashadd (sint u) { if (g.count(u)) return; g[u] = hn++; } void putsize () { if (stak.empty()) return; printf("%d\n", (int)stak.top().size()); } void sf_push () { sint u; hashadd(u); stak.push(u); } void sf_dup () { sint u = stak.top(); stak.push(u); } void sf_union () { sint f = stak.top(); stak.pop(); sint u = stak.top(); stak.pop(); for (iter i = f.begin(); i != f.end(); i++) u.insert(*i); hashadd(u); stak.push(u); } void sf_inct () { sint u; sint f = stak.top(); stak.pop(); sint s = stak.top(); stak.pop(); for (iter i = f.begin(); i != f.end(); i++) { if (s.count(*i)) u.insert(*i); } hashadd(u); stak.push(u); } void sf_add () { sint f = stak.top(); stak.pop(); sint s = stak.top(); stak.pop(); s.insert(g[f]); hashadd(s); stak.push(s); } void solve () { char order[10]; scanf("%s", order); switch (order[0]) { case 'P': sf_push(); break; case 'D': sf_dup(); break; case 'U': sf_union(); break; case 'I': sf_inct(); break; case 'A': sf_add(); break; } putsize(); } int main () { int cas, n; scanf("%d", &cas); while (cas--) { hn = 0; g.clear(); while (!stak.empty()) stak.pop(); scanf("%d", &n); while (n--) solve(); printf("***\n"); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 1517 - Tracking RFIDs(STL+..	下一篇：C++变量的存储类别与作用域

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: