首页 > 代码库 > UVALive 3634 数据结构模拟

UVALive 3634 数据结构模拟

这题真是坑啊,题意不明,其实就是往桟里面压入空的set集合,所以之前的询问大小都是只有0,只有add的时候,才会产生新的占空间的集合

用stack和set直接进行模拟

#include <iostream>#include <cstdio>#include <cstring>#include <set>#include <stack>#include <map>using namespace std;int cnt;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> tmp;    s.push(tmp);    puts("0");}void dup(){    s.push(s.top());    printf("%d\n",s.top().size());}void uni(){    pop();    for (set<int>::iterator it=s1.begin();it!=s1.end();it++){        s2.insert(*it);    }    s.push(s2);    printf("%d\n",s2.size());}void inter(){    pop();    set<int> s3;    for (set<int>::iterator it=s1.begin();it!=s1.end();it++){        if (s2.find(*it)!=s2.end()){            s3.insert(*it);        }    }    s.push(s3);    printf("%d\n",s3.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",s2.size());}int main(){    int t;    scanf("%d",&t);    char str[20];    while (t--)    {        cnt=1;        int m;        scanf("%d",&m);        while (!s.empty()) s.pop();        mp.clear();        while (m--)        {            scanf("%s",str);            if (str[0]==‘P‘) push();            if (str[0]==‘D‘) dup();            if (str[0]==‘A‘) add();            if (str[0]==‘U‘) uni();            if (str[0]==‘I‘) inter();        }        puts("***");    }    return 0;}