UVA

UVALive 3634 熟悉一下STL

Posted by Cww97 on 2016-02-03

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50626269

由于一些狗屁不通的原因,在下决定删除本文的题目描述

直接用集合和栈操作,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<set>
#include<stack>
#include<cstdio>
#include<map>
using namespace std;
int cnt;
char st[20];
set<int>s1,s2;
stack<set<int> >s;
map<set<int>,int >mp;

void POP(){s1=s.top();s.pop();s2=s.top();s.pop();}
void PUSH(){set<int>t;s.push(t);puts("0");}
void DUP(){s.push(s.top());printf("%d\n",s.top().size());}

void UNION(){
POP();
for (set<int>::iterator i=s1.begin();i!=s1.end();i++)
s2.insert(*i);
s.push(s2);
printf("%d\n",s.top().size());
}

void INTERSECT(){
POP(); set<int>s3;
for (set<int>::iterator i=s1.begin();i!=s1.end();i++)
if (s2.find(*i)!=s2.end())s3.insert(*i);
s.push(s3);
printf("%d\n",s.top().size());
}

void ADD(){
POP();
if (s1.empty())s2.insert(0);
else{
if (!mp[s1])mp[s1]=cnt++;
s2.insert(mp[s1]);
}
s.push(s2);
printf("%d\n",s.top().size());
}

int main(){
freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
while (T--){
cnt=1;
int n;scanf("%d",&n);
while(!s.empty())s.pop();
mp.clear();
for (int i=0;i<n;i++){
scanf("%s",st);
if (st[0]=='P') PUSH();
if (st[0]=='D') DUP();
if (st[0]=='U') UNION();
if (st[0]=='I') INTERSECT();
if (st[0]=='A') ADD();
}
puts("***");
}
return 0;
}