{"id":282,"date":"2010-06-14T10:03:00","date_gmt":"2010-06-14T02:03:00","guid":{"rendered":"http:\/\/localhost\/?p=282"},"modified":"2010-06-14T10:03:00","modified_gmt":"2010-06-14T02:03:00","slug":"shoi2007_setstack_collection_stack_machine","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=282","title":{"rendered":"[Shoi2007]Setstack \u96c6\u5408\u5806\u6808\u673a"},"content":{"rendered":"\n

[Shoi2007]Setstack \u96c6\u5408\u5806\u6808\u673a <\/p>\n

Time Limit:1000MS Memory Limit:65536K
Total Submit:22 Accepted:8<\/p>\n

Description <\/strong><\/p>\n

\u4e2d\u5b66\u6570\u5b66\u91cc\u96c6\u5408\u7684\u5143\u7d20\u5f80\u5f80\u662f\u5177\u4f53\u7684\u6570\u5b57\uff0c\u6bd4\u5982A = {1,2,3}\uff0cB = {}\uff08\u7a7a\u96c6\uff09\u7b49\u7b49\u3002\u4f46\u662f\u8981\u7279\u522b\u6ce8\u610f\uff0c\u96c6\u5408\u7684\u5143\u7d20\u4e5f\u53ef\u4ee5\u662f\u53e6\u4e00\u4e2a\u96c6\u5408\uff0c\u6bd4\u5982\u8bf4C = {{}}\uff0c\u5373\u8bf4\u660eC\u6709\u4e14\u4ec5\u6709\u4e00\u4e2a\u5143\u7d20——\u7a7a\u96c6B\uff0c\u6240\u4ee5\u79f0B\u662fC\u7684\u5b50\u96c6\u6216\u8005\u79f0B\u662fC\u7684\u5143\u7d20\u90fd\u662f\u6b63\u786e\u7684\u3002\u6240\u8c13\u4e00\u4e2a\u96c6\u5408\u7684\u52bf\uff0c\u5c31\u662f\u8fd9\u4e2a\u96c6\u5408\u7684\u5143\u7d20\u4e2a\u6570\uff0c\u4e00\u822c\u8bb0\u4e3a|S|\uff0c\u7a7a\u96c6\u7684\u52bf\u4e3a0\u3002\u5728\u4e0a\u4f8b\u4e2d\uff0c|A| = 3\uff0c|B| = 0\uff0c|C| = 1\u3002
\u9274\u4e8e\u96c6\u5408\u8bba\u662f\u73b0\u4ee3\u6570\u5b66\u7684\u57fa\u7840\u7406\u8bba\u8fd9\u4e00\u4e8b\u5b9e\uff0c\u4e00\u7fa4\u5f02\u60f3\u5929\u5f00\u7684\u79d1\u5b66\u5bb6\u5f00\u59cb\u7740\u624b\u5efa\u9020\u4e00\u53f0\u65b0\u5f0f\u7684\u8d85\u7ea7\u8ba1\u7b97\u673a——\u96c6\u5408\u5806\u6808\u673aAlpha\uff0c\u8fd9\u53f0\u673a\u5668\u64cd\u4f5c\u7684\u5c06\u662f\u96c6\u5408\u800c\u4e0d\u662f\u6570\u5b57\u3002\u4e0d\u8fc7\u7531\u4e8eAlpha\u7684\u7ae3\u5de5\u4e4b\u65e5\u9065\u9065\u65e0\u671f\uff0c\u79d1\u5b66\u5bb6\u4eec\u5e0c\u671b\u4f60\u4e3a\u4ed6\u4eec\u7f16\u5199\u4e00\u53f0\u865a\u62df\u673a\uff0c\u597d\u8ba9\u4ed6\u4eec\u68c0\u67e5\u81ea\u5df1\u7684\u539f\u578b\u8bbe\u8ba1\u662f\u5426\u5408\u7406\u3002
Alpha\u7684\u5b58\u50a8\u8bbe\u5907\u53ea\u6709\u4e00\u4e2a\u6808\uff0c\u6808\u7684\u6bcf\u4e2a\u5355\u5143\u90fd\u53ea\u80fd\u653e\u7f6e\u4e00\u4e2a\u96c6\u5408\u3002\u4e00\u5f00\u59cb\uff0c\u6808\u662f\u7a7a\u7684\uff0c\u5728\u6bcf\u4e2a\u64cd\u4f5c\u7ed3\u675f\u540e\uff0c\u8ba1\u7b97\u673a\u5c31\u4f1a\u8f93\u51fa\u4f4d\u4e8e\u6808\u9876\u5355\u5143\u7684\u90a3\u4e2a\u96c6\u5408\u7684\u52bf\u3002Alpha\u62e5\u6709\u4e94\u79cd\u4e0d\u540c\u7684\u6307\u4ee4\uff0c\u5206\u522b\u4e3a\uff1aPUSH\u3001DUP\u3001UNION\u3001INTERSECT\u548cADD\uff0c\u4ed6\u4eec\u7684\u529f\u80fd\u5982\u4e0b\uff1a
<\/p>\n

Input <\/strong><\/p>\n

\u7b2c\u4e00\u884c\u53ea\u6709\u4e00\u4e2a\u6574\u6570n\uff080\u2264n\u22642000\uff09\uff0c\u4ee3\u8868\u5c06\u8981\u6267\u884c\u7684\u6307\u4ee4\u6761\u6570\u3002\u63a5\u4e0b\u6765\u6709n\u884c\uff0c\u6bcf\u884c\u6709\u5305\u542b\u4e00\u6761\u5927\u5199\u7684\u6307\u4ee4\uff0c\u6211\u4eec\u4fdd\u8bc1\u6bcf\u6761\u6307\u4ee4\u90fd\u662f\u4e0a\u8ff0\u4e94\u6761\u6307\u4ee4\u4e2d\u7684\u4e00\u6761\uff0c\u5e76\u4e14\u865a\u62df\u673a\u603b\u662f\u80fd\u6b63\u786e\u6267\u884c\u5b8c\u6240\u6709\u7684\u6307\u4ee4\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u8f93\u51fa\u865a\u62df\u673a\u7684\u8f93\u51fa\u7ed3\u679c\u5373\u53ef\u3002\u6bcf\u884c\u8f93\u51fa\u4e00\u4e2a\u5927\u4e8e\u6216\u7b49\u4e8e0\u7684\u6574\u6570\uff0c\u4ee3\u8868\u865a\u62df\u673a\u6267\u884c\u8be5\u6761\u6307\u4ee4\u540e\u7684\u8f93\u51fa\u3002\u9009\u624b\u4eec\u52a1\u5fc5\u4ed4\u7ec6\u8003\u91cf\u7a0b\u5e8f\u7684\u6267\u884c\u6548\u7387\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Hint <\/strong><\/p>\n

\u5bf9\u4e8e20%\u7684\u6570\u636e\uff0cn \u2264 10\u3002
\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0cn \u2264 2000\u3002 <\/p>\n

Source
\u989d\u3002\u3002\u8fd9\u9053\u9898\u76ee\u53ea\u8981\u7ed9\u6bcf\u4e2a\u96c6\u5408\u8bbe\u8ba1\u4e00\u4e2aHash\u51fd\u6570\u5c31\u597d\u529e\u4e86\u3002\u3002\u6211\u770boimaster\u5927\u795e\u8bf4\u7684\u662f
\u5168\u90e8xor\u4e00\u4e2a\u503c\u7136\u540e\u4e58\u8d77\u6765\u3002\u3002\u7136\u540e\u6211\u81ea\u5df1\u4e5f\u60f3\u4e86\u4e00\u4e2a\u3002\u3002\u5c31\u662f\u628a\u6240\u6709\u7684\u5b50\u96c6\u7684Hash\u503c\u6392\u5e8f\u4e00\u4e0b
\u7136\u540e\u76f4\u63a5\u6548\u4effRabin—Karp..\u5173\u952e\u662f\u5982\u679c\u8fd9\u4e48\u641e\u5168\u662f0.\u3002\u3002\u6240\u4ee5\u518d\u52a0\u4e2a\u4fee\u6b63\u503c\u3002\u3002\u3002\u795e\u5947\u76841A\u56e7\u3002\u3002
Code\uff1a
#include <vector><\/strong>
#include <stack>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
const int seed=13331;
using namespace std;
typedef unsigned long long ull;
typedef vector<ull> set;
ull Code(const set&s)
{
    ull ret=0;
    rep(i,s.size())ret*=seed,ret+=s[i]+78;
    return ret;
}
void Normal(set&s)
{
    sort(All(s));
    s.resize(unique(All(s))-s.begin());
}
stack<set> S;
int main()
{
    int n;scanf("%d",&n);char cmd[10];set a,b;
    while(n–)
    {
        scanf("%s",cmd);
        switch(cmd[0])
        {
            case ‘P’:S.push(set());break;
            case ‘D’:S.push(S.top());break;
            case ‘A’:a=S.top();S.pop();b=S.top();S.pop();b.pb(Code(a));
                    Normal(b);S.push(b);break;
            default:a=S.top();S.pop();b=S.top();S.pop();set c(a.size()+b.size());
                if(cmd[0]==’U’)c.resize(set_union(All(a),All(b),c.begin())-c.begin());
                else c.resize(set_intersection(All(a),All(b),c.begin())-c.begin());
                Normal(c);S.push(c);break;
        }
        printf("%dn",S.top().size());
    }
}<\/p>\n<\/p>\n

001011222<\/p>\n

9PUSHDUPADDPUSHADDDUPADDDUPUNION <\/p>\n","protected":false},"excerpt":{"rendered":"

[Shoi2007]Setstack \u96c6\u5408\u5806\u6808\u673a Time Limit:1000MS Memory Limit:65536KTotal Submit:22 Accepted:8 Description \u4e2d\u5b66\u6570\u5b66\u91cc\u96c6\u5408\u7684\u5143\u7d20\u5f80\u5f80\u662f\u5177\u4f53\u7684\u6570\u5b57\uff0c\u6bd4\u5982A = {1,2,3}\uff0cB = {}\uff08\u7a7a\u96c6\uff09\u7b49\u7b49\u3002\u4f46\u662f\u8981\u7279\u522b\u6ce8\u610f\uff0c\u96c6\u5408\u7684\u5143\u7d20\u4e5f\u53ef\u4ee5\u662f\u53e6\u4e00\u4e2a\u96c6\u5408\uff0c\u6bd4\u5982\u8bf4C = {{}}\uff0c\u5373\u8bf4\u660eC\u6709\u4e14\u4ec5\u6709\u4e00\u4e2a\u5143\u7d20——\u7a7a\u96c6B\uff0c\u6240\u4ee5\u79f0B\u662fC\u7684\u5b50\u96c6\u6216\u8005\u79f0B\u662fC\u7684\u5143\u7d20\u90fd\u662f\u6b63\u786e\u7684\u3002\u6240\u8c13\u4e00\u4e2a\u96c6\u5408\u7684\u52bf\uff0c\u5c31\u662f\u8fd9\u4e2a\u96c6\u5408\u7684\u5143\u7d20\u4e2a\u6570\uff0c\u4e00\u822c\u8bb0\u4e3a|S|\uff0c\u7a7a\u96c6\u7684\u52bf\u4e3a0\u3002\u5728\u4e0a\u4f8b\u4e2d\uff0c|A| = 3\uff0c|B| = 0\uff0c|C| = 1\u3002 \u9274\u4e8e\u96c6\u5408\u8bba\u662f\u73b0\u4ee3\u6570\u5b66\u7684\u57fa\u7840\u7406\u8bba\u8fd9\u4e00\u4e8b\u5b9e\uff0c\u4e00\u7fa4\u5f02\u60f3\u5929\u5f00\u7684\u79d1\u5b66\u5bb6\u5f00\u59cb\u7740\u624b\u5efa\u9020\u4e00\u53f0\u65b0\u5f0f\u7684\u8d85\u7ea7\u8ba1\u7b97\u673a——\u96c6\u5408\u5806\u6808\u673aAlpha\uff0c\u8fd9\u53f0\u673a\u5668\u64cd\u4f5c\u7684\u5c06\u662f\u96c6\u5408\u800c\u4e0d\u662f\u6570\u5b57\u3002\u4e0d\u8fc7\u7531\u4e8eAlpha\u7684\u7ae3\u5de5\u4e4b\u65e5\u9065\u9065\u65e0\u671f\uff0c\u79d1\u5b66\u5bb6\u4eec\u5e0c\u671b\u4f60\u4e3a\u4ed6\u4eec\u7f16\u5199\u4e00\u53f0\u865a\u62df\u673a\uff0c\u597d\u8ba9\u4ed6\u4eec\u68c0\u67e5\u81ea\u5df1\u7684\u539f\u578b\u8bbe\u8ba1\u662f\u5426\u5408\u7406\u3002 Alpha\u7684\u5b58\u50a8\u8bbe\u5907\u53ea\u6709\u4e00\u4e2a\u6808\uff0c\u6808\u7684\u6bcf\u4e2a\u5355\u5143\u90fd\u53ea\u80fd\u653e\u7f6e\u4e00\u4e2a\u96c6\u5408\u3002\u4e00\u5f00\u59cb\uff0c\u6808\u662f\u7a7a\u7684\uff0c\u5728\u6bcf\u4e2a\u64cd\u4f5c\u7ed3\u675f\u540e\uff0c\u8ba1\u7b97\u673a\u5c31\u4f1a\u8f93\u51fa\u4f4d\u4e8e\u6808\u9876\u5355\u5143\u7684\u90a3\u4e2a\u96c6\u5408\u7684\u52bf\u3002Alpha\u62e5\u6709\u4e94\u79cd\u4e0d\u540c\u7684\u6307\u4ee4\uff0c\u5206\u522b\u4e3a\uff1aPUSH\u3001DUP\u3001UNION\u3001INTERSECT\u548cADD\uff0c\u4ed6\u4eec\u7684\u529f\u80fd\u5982\u4e0b\uff1a Input \u7b2c\u4e00\u884c\u53ea\u6709\u4e00\u4e2a\u6574\u6570n\uff080\u2264n\u22642000\uff09\uff0c\u4ee3\u8868\u5c06\u8981\u6267\u884c\u7684\u6307\u4ee4\u6761\u6570\u3002\u63a5\u4e0b\u6765\u6709n\u884c\uff0c\u6bcf\u884c\u6709\u5305\u542b\u4e00\u6761\u5927\u5199\u7684\u6307\u4ee4\uff0c\u6211\u4eec\u4fdd\u8bc1\u6bcf\u6761\u6307\u4ee4\u90fd\u662f\u4e0a\u8ff0\u4e94\u6761\u6307\u4ee4\u4e2d\u7684\u4e00\u6761\uff0c\u5e76\u4e14\u865a\u62df\u673a\u603b\u662f\u80fd\u6b63\u786e\u6267\u884c\u5b8c\u6240\u6709\u7684\u6307\u4ee4\u3002 Output \u8f93\u51fa\u865a\u62df\u673a\u7684\u8f93\u51fa\u7ed3\u679c\u5373\u53ef\u3002\u6bcf\u884c\u8f93\u51fa\u4e00\u4e2a\u5927\u4e8e\u6216\u7b49\u4e8e0\u7684\u6574\u6570\uff0c\u4ee3\u8868\u865a\u62df\u673a\u6267\u884c\u8be5\u6761\u6307\u4ee4\u540e\u7684\u8f93\u51fa\u3002\u9009\u624b\u4eec\u52a1\u5fc5\u4ed4\u7ec6\u8003\u91cf\u7a0b\u5e8f\u7684\u6267\u884c\u6548\u7387\u3002 Sample Input Sample Output Hint \u5bf9\u4e8e20%\u7684\u6570\u636e\uff0cn \u2264 10\u3002 \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0cn \u2264 2000\u3002 Source \u989d\u3002\u3002\u8fd9\u9053\u9898\u76ee\u53ea\u8981\u7ed9\u6bcf\u4e2a\u96c6\u5408\u8bbe\u8ba1\u4e00\u4e2aHash\u51fd\u6570\u5c31\u597d\u529e\u4e86\u3002\u3002\u6211\u770boimaster\u5927\u795e\u8bf4\u7684\u662f\u5168\u90e8xor\u4e00\u4e2a\u503c\u7136\u540e\u4e58\u8d77\u6765\u3002\u3002\u7136\u540e\u6211\u81ea\u5df1\u4e5f\u60f3\u4e86\u4e00\u4e2a\u3002\u3002\u5c31\u662f\u628a\u6240\u6709\u7684\u5b50\u96c6\u7684Hash\u503c\u6392\u5e8f\u4e00\u4e0b\u7136\u540e\u76f4\u63a5\u6548\u4effRabin—Karp..\u5173\u952e\u662f\u5982\u679c\u8fd9\u4e48\u641e\u5168\u662f0.\u3002\u3002\u6240\u4ee5\u518d\u52a0\u4e2a\u4fee\u6b63\u503c\u3002\u3002\u3002\u795e\u5947\u76841A\u56e7\u3002\u3002Code\uff1a#include <vector>#include <stack>#include <cstdio>#include <algorithm>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define All(x) x.begin(),x.end()const int seed=13331;using namespace […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/282"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=282"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/282\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}