{"id":999,"date":"2014-10-02T13:27:27","date_gmt":"2014-10-02T05:27:27","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=999"},"modified":"2016-08-24T19:33:57","modified_gmt":"2016-08-24T11:33:57","slug":"2013-acmicpc-asia-regional-hangzhou-onsite","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/2013-acmicpc-asia-regional-hangzhou-onsite\/","title":{"rendered":"2013 ACM\/ICPC Asia Regional Hangzhou Onsite"},"content":{"rendered":"

http:\/\/acmicpc.info\/archives\/1636<\/a><\/p>\n

<\/p>\n

Problem A. Lights Against Dudely<\/h2>\n

Brief description: <\/h3>\n

There are at most fifteen vulnerable rooms in the bank.<\/quote><\/p>\n

Analysis: <\/h3>\n

\u679a\u4e3e + \u72b6\u6001\u538b\u7f29 DP\u3002<\/p>\n

\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int dx[] = {-1, 0, 1, 0, -1};\r\nconst int dy[] = {0, 1, 0, -1, 0};\r\n\r\nconst int NN = 15, N = 209;\r\nchar Map[N][N]; int id[N][N]; int dp[1<<NN];\r\nint n, m, nn;\r\n\r\nbool inGrid(int x, int y){\r\n    return x >= 0 && y >= 0 && x < n && y < m;\r\n}\r\n\r\nstruct rec{\r\n    int x, y, s;\r\n    rec(int x = 0, int y = 0):x(x),y(y){\r\n    }\r\n    void init(int o = 0){\r\n        s = _1(id[x][y]);\r\n        REP(d, 2){\r\n            int xx = x + dx[o+d], yy = y + dy[o+d];\r\n            if (!inGrid(xx, yy)) continue;\r\n            if (Map[xx][yy] == '.') s |= _1(id[xx][yy]);\r\n            else{\r\n                s = 0;\r\n                return;\r\n            }\r\n        }\r\n    }\r\n} A[NN];\r\n\r\nint f(int id, int off){\r\n\r\n    REP(i, nn){\r\n        if (i == id) A[i].init(off);\r\n        else A[i].init();\r\n    }\r\n\r\n    FLC(dp, 0x3f); dp[0] = 0;\r\n    REP(s, _1(nn)){\r\n        REP(i, nn) if (!_1(s, i)){\r\n            int ss = s | A[i].s;\r\n            checkMin(dp[ss], dp[s] + 1);\r\n        }\r\n    }\r\n    return dp[_U(nn)];\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    while (RD(n, m)){\r\n        REP(i, n) RS(Map[i]);\r\n        nn = 0; REP_2(i, j, n, m) if (Map[i][j] == '.'){\r\n            id[i][j] = nn;\r\n            A[nn++] = rec(i, j);\r\n        }\r\n\r\n        if (!nn){\r\n            OT(0);\r\n            continue;\r\n        }\r\n\r\n        int res = INF; REP(i, nn) REP(d, 4){\r\n            checkMin(res, f(i, d));\r\n        }\r\n        if (res == INF) res = -1;\r\n        OT(res);\r\n    }\r\n}\r\n<\/pre>\n
Problem F. Infinite Go<\/h2>\n
Brief description: <\/h3>\n
\u9898\u76ee\u610f\u601d\u5c31\u662f\u7ed9\u4f60\u4e0b\u56f4\u68cb\u7684\u4f4d\u7f6e\uff0c\u9ed1\u5b50\u5148\u4e0b\uff0c\u9ed1\u767d\u5b50\u4ea4\u66ff\u7684\u4e0b\uff0c\u9014\u4e2d\u4f1a\u51fa\u73b0\u68cb\u5b50\u88ab\u5403\u6389\u7684\u60c5\u51b5\uff0c\u8ba9\u4f60\u8f93\u51fa\u6700\u540e\u9ed1\u8272\u548c\u767d\u8272\u7684\u68cb\u5b50\u5404\u6709\u591a\u5c11\u4e2a\u3002
\n\u68cb\u5b50\u88ab\u5403\u6389\u7684\u6761\u4ef6\u662f\uff1a\u4e0a\u4e0b\u5de6\u53f3\u56db\u4e2a\u65b9\u5411\u76f8\u90bb\u7684\u540c\u8272\u7684\u68cb\u5b50\u6240\u5f62\u6210\u7684\u7684\u8054\u901a\u5feb\u7684\u8fb9\u7f18\u6ca1\u6709\u7a7a\u4f4d\uff08\u76ee\uff09\u3002\u7a7a\u4f4d\u53ea\u9700\u8981\u8003\u8651\u4e0a\u4e0b\u5de6\u53f3\u56db\u4e2a\u65b9\u5411\u3002<\/p>\n
Analysis: <\/h3>\n
\u5e76\u67e5\u96c6\u7ef4\u62a4\u68cb\u5b50\u6240\u5728\u7684\u8054\u901a\u5757\uff0cf[] \u7ef4\u62a4 \u201c\u76ee\u201d\u3002
\n\u6518\u5916\u5fc5\u5148\u5b89\u5185\uff0c\u5f53\u52a0\u5165\u65b0\u68cb\u5b50\u65f6\uff0c\u5e94\u4e25\u683c\u6309\u7167\uff0c\u5148\u7ef4\u62a4\u81ea\u8eab\u76ee\u6570\uff0c\u518d\u5904\u7406\u5403\u5bf9\u9762\u7684\u60c5\u51b5\uff0c\u518d\u5904\u7406\u5408\u5e76\uff0c\u518d\u8003\u8651\u662f\u5426\u81ea\u8eab\u88ab\u5403\u56db\u4e2a\u6b65\u9aa4\u3002\u3002\u3002
\n\uff08\u5148\u51fa\u57fa\u672c\u88c5\u3001Gank \u4e00\u6ce2\uff0c\u518d\u548c\u961f\u53cb\u62b1\u56e2\u3002\u3002\uff09\u3002\u3002\u3002<\/p>\n
\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e4) + 9;\r\nmap<PII, int> B; \/\/ Board\r\nint x[N], y[N], f[N], p[N];\r\nint n, n1, n2;\r\n\r\nint Find(int x){\r\n    return p[x] == x ? x : p[x] = Find(p[x]);\r\n}\r\n\r\nvoid Union(int x, int y){\r\n    x = Find(x), y = Find(y); if (x == y) return;\r\n    p[x] = y; f[y] += f[x];\r\n}\r\n\r\nvoid del(int n){\r\n    if (n&1) --n2; else --n1; B.erase(MP(x[n], y[n]));\r\n    REP(d, 4){\r\n        int xx = x[n] + dx[d], yy = y[n] + dy[d];\r\n        if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;\r\n        int m = B[MP(xx, yy)];\r\n        if ((n^m)&1) ++f[Find(m)]; else del(m);\r\n    }\r\n}\r\n\r\nvoid print(){\r\n    FOR_1(a, 1, 10){\r\n        FOR_1(b, 1, 10){\r\n            if (!CTN(B, MP(a, b))) putchar('.');\r\n            else putchar(B[MP(a, b)]&1 ? '&' : '*');\r\n        }\r\n        puts("");\r\n    }\r\n    puts("");\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    Rush{\r\n        CLR(B), n = n1 = n2 = 0; Rush{\r\n            RD(x[n], y[n]); p[n] = B[MP(x[n], y[n])] = n; f[n] = 0;\r\n            if (n&1) ++n2; else ++n1;\r\n\r\n            REP(d, 4){\r\n                int xx = x[n] + dx[d], yy = y[n] + dy[d];\r\n                if (!xx || !yy || CTN(B, MP(xx, yy))) continue;\r\n                ++f[n];\r\n            }\r\n            REP(d, 4){\r\n                int xx = x[n] + dx[d], yy = y[n] + dy[d];\r\n                if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;\r\n                int m = Find(B[MP(xx, yy)]);\r\n                --f[m]; if ((m^n)&1 && !f[m]) del(m);\r\n            }\r\n            REP(d, 4){\r\n                int xx = x[n] + dx[d], yy = y[n] + dy[d];\r\n                if (!xx || !yy || !CTN(B, MP(xx, yy))) continue;\r\n                int m = Find(B[MP(xx, yy)]);\r\n                if (!((m^n)&1)) Union(m, n);\r\n            }\r\n\r\n            if (!f[Find(n)]) del(n);\r\n\r\n            ++n;\r\n        }\r\n        printf("%d %d\\n", n1, n2);\r\n    }\r\n}\r\n\r\n<\/pre>\n
Problem G. Ants<\/h2>\n
fork: https:\/\/www.shuizilong.com\/house\/archives\/poj-3764-the-xor-longest-path\/<\/a><\/p>\n
http:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=2818548<\/a><\/p>\n
Problem H. Rabbit Kingdom<\/h2>\n
Brief description: <\/h3>\n
\u7ed9\u51fa n \u4e2a\u6570\uff0c\u6709 m \u4e2a\u67e5\u8be2\uff0c\u6bcf\u6b21\u67e5\u8be2\u8be2\u95ee\u533a\u95f4 [L, R] \u4e2d\u6700\u591a\u6709\u591a\u5c11\u4e2a\u6570\u4e0e\u533a\u95f4\u4e2d\u5176\u4ed6\u6570\u90fd\u4e0d\u4e92\u8d28\u3002<\/p>\n
Analysis: <\/h3>\n
\u79bb\u7ebf + \u6811\u72b6\u6570\u7ec4\u3002\uff08\u7c7b\u4f3c Dquery\uff09<\/p>\n
\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(2e5) + 9;\r\nint n;\r\n\r\nnamespace BIT{\r\n    typedef int intt;\r\n    intt C[N], S;\r\n    void Add(int x, int d){\r\n        if (!x) return;\r\n        for (;x<=n;x+=low_bit(x)) C[x] += d;\r\n        S += d;\r\n    }\r\n    intt Sum(int x){\r\n        intt res = 0; for (;x;x^=low_bit(x)) res += C[x];\r\n        return res;\r\n    }\r\n    intt Sum(int l, int r){\r\n        return Sum(r) - Sum(l-1);\r\n    }\r\n} using namespace BIT;\r\n\r\n\/\/\u6700\u5c0f\u7d20\u56e0\u5b50\u3002\u3002\r\nconst int PMAX = N;\r\nVI P; bitset<PMAX> isC; int p[PMAX];\r\n#define ii (i*P[j])\r\nvoid sieve(){\r\n    FOR(i, 2, PMAX){\r\n        if (!isC[i]) P.PB(i),p[i]=i;\r\n        for (int j=0;j<SZ(P)&&ii<PMAX;++j){\r\n            isC[ii]=1; p[ii]=P[j]; if (!(i%P[j])) break;\r\n        }\r\n    }\r\n}\r\n#undef ii\r\n\r\nint A[N], suc[N], prd[N], last[N];\r\nVII qry[N], rls[N]; int res[N];\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    sieve();\r\n\r\n    int q; while (RD(n, q)){\r\n\r\n        RST(C); S = 0; REP_1(i, n) RD(A[i]), CLR(qry[i], rls[i]);\r\n\r\n        REP(i, q){\r\n            int l, r; RD(l, r);\r\n            qry[r].PB(MP(l, i));\r\n        }\r\n\r\n        RST(last); REP_1(i, n){\r\n            int x = A[i]; prd[i] = 0;\r\n            while (x != 1){\r\n                int px = p[x]; checkMax(prd[i], last[px]); last[px] = i;\r\n                do x \/= px; while (p[x] == px);\r\n            }\r\n        }\r\n\r\n        FLC(last, 0x3f); DWN_1(i, n, 1){\r\n            int x = A[i]; suc[i] = INF;\r\n            while (x != 1){\r\n                int px = p[x]; checkMin(suc[i], last[px]);\r\n                last[px] = i;\r\n                do x \/= px; while (p[x] == px);\r\n            }\r\n        }\r\n\r\n        REP_1(i, n) if (suc[i] == INF) suc[i] = 0;\r\n\r\n        REP_1(i, n){\r\n\r\n            Add(i, 1); A[i] = 1; int l = prd[i], r = suc[i];\r\n\r\n            Add(l, -1);\r\n            rls[r].PB(MP(i, -1));\r\n            rls[r].PB(MP(l, 1));\r\n\r\n            ECH(it, rls[i]){\r\n                Add(it->fi, it->se);\r\n            }\r\n\r\n            ECH(it, qry[i]){\r\n                int l = it->fi, id = it->se;\r\n                res[id] = S - BIT::Sum(l-1);\r\n            }\r\n\r\n            \/\/REP_1(i, n) cout << Sum(i, i) << " "; puts("");\r\n        }\r\n        \/\/puts("");\r\n        REP(i, q) OT(res[i]);\r\n    }\r\n}\r\n\r\n\r\n<\/pre>\n
Problem I. Gems Fight!<\/h2>\n
Brief description: <\/h3>\n
\u7565\u3002\uff09<\/p>\n
Analysis: <\/h3>\n
\u72b6\u6001\u538b\u7f29 + \u535a\u5f08 DP\u3002<\/p>\n
\uff08\u4e3b\u8981\u662f The Gems collected are stored in a shared cooker<\/font>.
\n\u5982\u679c\u6ca1\u6709\u8fd9\u4e2a\u6761\u4ef6\u3002\u3002\u72b6\u6001\u5c06\u4f1a\u6709\u540e\u6548\u6027\u3002\u3002\u53ea\u80fd\u641c\uff1f\uff09<\/p>\n
\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 21, M = 9;\r\nint F[1<<N], S[1<<N], n, m, s0;\r\n\r\nvoid init(){\r\n\r\n    VVI I; REP(i, n){\r\n        VI t; Rush t.PB(RD()-1);\r\n        I.PB(t);\r\n    }\r\n\r\n    static int cnt[M]; REP(s, _1(n)){\r\n        RST(cnt); REP(i, n) if (_1(s, i)) ECH(it, I[i]) ++cnt[*it];\r\n        S[s] = 0; REP(i, m) S[s] += cnt[i] \/ s0;\r\n    }\r\n\r\n    FLC(F, -1);\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    while (RD(m,n,s0)){\r\n\r\n        init(); FLC(F, 0x8f); F[_U(n)] = 0; DWN(s, _1(n), 1){\r\n            REP(i, n) if (_1(s, i)){\r\n                int ss = s ^ _1(i), d = S[s]-S[ss];\r\n                if (d) checkMax(F[ss], F[s] + d);\r\n                else checkMax(F[ss], -F[s]);\r\n            }\r\n        }\r\n\r\n        OT(F[0]);\r\n    }\r\n}\r\n\r\n<\/pre>\n
Problem K. Candy Factory<\/h2>\n
Brief description: <\/h3>\n
\u7565\u3002\uff09<\/p>\n
Analysis: <\/h3>\n
\u7f51\u7edc\u6d41<\/p>\n
\u5efa\u6a21 1\uff1a\u4e0a\u4e0b\u754c\u6700\u5c0f\u8d39\u7528\u6d41
\nS -> M -> C0 <-> C1 -> T<\/code>
\nhttp:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=2823256<\/a><\/p>\n
\u5efa\u6a21 2\uff1a\u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41
\nS -> M -> C0 -> C1 -> T<\/code>
\nS ------> C2 -> C1 -> T<\/code>
\nhttp:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=2822981<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
http:\/\/acmicpc.info\/archives\/1636<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[164],"tags":[],"class_list":["post-999","post","type-post","status-publish","format-standard","hentry","category-onsite"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-g7","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/999","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=999"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/999\/revisions"}],"predecessor-version":[{"id":1000,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/999\/revisions\/1000"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=999"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=999"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=999"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}