{"id":258,"date":"2012-06-19T17:37:49","date_gmt":"2012-06-19T09:37:49","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=258"},"modified":"2012-06-19T17:37:49","modified_gmt":"2012-06-19T09:37:49","slug":"coci-20112012-round-2","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/coci-20112012-round-2\/","title":{"rendered":"COCI 2011\/2012 Round #2"},"content":{"rendered":"

<\/p>\n

Brief description: <\/h3>\n

Problem A. najboljih
\n\u2026<\/p>\n

Problem B. okret
\n\u95ee\u8ff7\u5bab\u662f\u5426\u6709\u6b7b\u8def\u3002<\/p>\n

Problem C. zadaca
\n\u95ee\u4e24\u4e2a\u5de8\u5927\u6574\u6570\u7684 gcd \u7684\u540e 9 \u4f4d\u6570\u5b57\uff0c\u5de8\u5927\u6574\u6570\u7528 N \u4e2a integer \u7684\u4e58\u79ef\u8868\u793a\u3002
\n( .. .N <= 1,000 .. .)\n\nProblem D. kompici\n\u95ee N \u4e2a\u6570\u53ef\u4ee5\u7ec4\u6210\u591a\u5c11\u5bf9 pair\uff0c pair \u5b9a\u4e49\u4f4d\u6709\u81f3\u5c11\u4e00\u4e2a\u76f8\u540c\u7684 digit \u3002\u3002\n( .. N <= 1,000,000 ..)\n\nProblem E. funkcija\n\u6709\u4e00\u5b9a\u7a0b\u5ea6\u4f9d\u8d56\u7684 for \u5faa\u73af\u8ba1\u6570\u95ee\u9898... .\n\nProblem F. raspored\n\u3002\u3002\u3002\n\n\n\n

Analysis: <\/h3>\n

(\u524d\u7565\u3002\u3002)<\/p>\n

Problem E. funkcija<\/p>\n

E \u662f\u4e00\u9053\u5f88\u503c\u5f97\u8fdb\u4e00\u6b65\u601d\u8003\u7684\u95ee\u9898\u3002\u3002
\n\u9996\u5148\u3002\u3002\u50cf\u662f\u8fd9\u6837\u7684\u4e00\u7ec4 Input \u3002\u3002<\/p>\n

Input:
\n3
\n2 3
\n1 a
\nb a
\nOutput:
\n9<\/p>\n

\uff08\u9898\u76ee\u91cc\u8981\u6c42\u8bf4\u3002\u3002Xi, Yi \u4e0d\u53ef\u4ee5\u540c\u65f6\u4e3a\u5b57\u6bcd\u3002\u3002\u4f46\u662f\u53bb\u9664\u8fd9\u4e2a\u9650\u5236\u3002\u4e5f\u662f\u4e00\u4e2a will defined \u7684\u95ee\u9898\u3002\u3002\u4f46\u4f3c\u4e4e\u5c31\u4e0d\u89e3\u4e86\u3002\u3002\uff09
\n\u3002\u3002\u3002\u4e8e\u662f\u4f9d\u8d56\u5173\u7cfb\u5f62\u6210\u6709\u6839\u6811\u68ee\u6797\uff08\u6709\u591a\u4e2a\u5de6\u5b69\u5b50\u548c\u53f3\u5b69\u5b50\u7684\u201c\u4e8c\u53c9\u6811\u201d\u3002\u3002\uff09
\n\u3002\u3002\u4e4b\u540e\u8fce\u5203\u7167\u505a\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\uff08\u5229\u7528\u90e8\u5206\u548c\u8fdb\u884c\u72b6\u6001\u8f6c\u79fb\u3002\u3002\u5177\u4f53\u505a\u6cd5\u4e5f\u53ef\u4ee5\u53c2\u8003\u8fd9\u91cc\u3002\u3002\uff09<\/p>\n

Problem F. raspored
\n\u3002F \u9996\u5148\u7b2c\u4e00\u95ee\u53ef\u4ee5\u901a\u8fc7\u6392\u5e8f\u540e\u8d2a\u5fc3\u7684\u65b9\u6cd5\u5f97\u5230\u3002\u3002\u539f\u7406\u53c2\u7167\u6392\u5e8f\u4e0d\u7b49\u5f0f\u3002\u3002
\n\u3002\u3002\u4ee5\u4e0b\u5047\u5b9a\u8bfb\u8005\u9ed8\u8ba4\u6392\u5e8f\u4e0d\u7b49\u5f0f\u7684\u6b63\u786e\u6027\u3002\u3002<\/p>\n

\u4e8e\u662f\u5904\u7406\u7b2c\u4e8c\u95ee\u3002\u3002\u53d1\u73b0\u4fee\u6539\u8fc7\u7a0b\u3002\u3002\u3002\u9700\u8981\u7684\u662f\u4e00\u79cd\u652f\u6301 O(1) \u63d2\u5165\u3001O(1) \u5220\u9664 \u548c \u4e8c\u5206\u67e5\u627e\u7684\u6570\u636e\u7ed3\u6784\u3002\u3002
\n\u8fdb\u4e00\u6b65\u5206\u6790\u53ef\u4ee5\u5c06\u9898\u76ee\u4e2d\u6240\u8bf4\u7684\u4e24\u79cd\u4ee3\u4ef7\u5206\u79bb\u3002\u3002\u7b2c\u4e00\u4e2a\u53ef\u4ee5\u76f4\u63a5 O(1) \u7ef4\u62a4\u3002\u3002\u7b2c\u4e8c\u4e2a\u5c06\u6240\u6709\u7684\u9700\u6c42\u65f6\u95f4\u63d2\u5165\u5230\u4e00\u9897\u5e73\u8861\u6811\u4e2d\u52a8\u6001\u7ef4\u62a4\u3002\u3002\u3002<\/p>\n

\u9700\u8981\u989d\u5916\u6dfb\u52a0\u4e00\u4e9b\u57df\u3002\u3002<\/p>\n

1. sz[] \u7528\u4ee5\u7ef4\u62a4\u5b50\u6811\u7684\u89c4\u6a21
\n2. ss[] \u7ef4\u62a4\u5b50\u6811\u7684\u5173\u952e\u5b57\u6743\u548c\u3002
\n3. cost[] \u7ef4\u62a4\u5b50\u6811\u6240\u5f15\u8d77\u7684\u4ee3\u4ef7\u3002\u3002<\/p>\n

\u56e0\u4e3a\u9700\u8981 sz[] \u57df\u6240\u4ee5\u8003\u8651\u7528 sbt \u5b9e\u73b0\u5e73\u8861\u6811\u3002\u3002\u3002\u4e8e\u662f\u8fd9\u9053\u9898\u7684\u771f\u6b63\u6838\u5fc3\u662f\uff1a<\/p>\n

\r\ncost[x] = cost[lx] + cost[rx] + LL(ss[lx] + key[x]) * (sz[rx] + 1) \u3002\u3002\u3002\r\n<\/pre>\n
\u2026<\/p>\n
\r\n...\r\nint A[8], O[8];\r\n \r\nbool comp(int a, int b){\r\n    return A[a] > A[b];\r\n}\r\n \r\nint main(){\r\n    REP(i, 8) RD(A[i]), O[i] = i;\r\n    sort(O, O+8, comp);\r\n \r\n    int s = 0; REP(i, 5) s += A[O[i]];\r\n    cout << s << endl;\r\n \r\n    REP(i, 8) A[O[i]] = i;\r\n \r\n    s = 5; REP(i, 8) if (A[i] < 5){\r\n        if (--s) cout << i + 1 << " ";\r\n        else cout << i + 1 << endl;\r\n    }\r\n}\r\n<\/pre>\n
\r\n.. .\r\nconst int N = 11;\r\nbool Map[N][N];\r\nint n, m;\r\n \r\nint main(){\r\n \r\n    \/\/freopen("in.txt", "r", stdin);\r\n \r\n    RD(n, m); char t; REP_2(i, j, n, m){\r\n        RC(t); if (t == '.') Map[i][j] = true;\r\n        else Map[i][j] = false;\r\n    }\r\n \r\n    int Dead = 0; REP_2(x, y, n, m) if (Map[x][y]){\r\n        int cnt = 0; REP(ii, 4){\r\n            int xx = x + dx[ii], yy = y + dy[ii];\r\n            if (xx < 0 || yy < 0 || xx >= n || yy >= m) continue;\r\n            if (Map[xx][yy]) ++cnt;\r\n        }\r\n \r\n        if (cnt == 1) Dead = 1;\r\n    }\r\n \r\n    cout << Dead << endl;\r\n}\r\n<\/pre>\n
\r\n.. .\r\ntemplate<class T> inline void OT(const T &x){\r\n    if (flag) REP(i, 9 - log(D) \/ log(10)) putchar('0');\r\n    printf("%d\\n", x);\r\n}\r\n \r\ninline void MUL(int &a, int b){\r\n    LL t = (LL)a * b; if (t > MOD) flag = true;\r\n    a = t % MOD;\r\n}\r\n \r\nconst int N = 1009;\r\nint D, a[N], b[N]; bool flag = false;\r\nint n, m;\r\n \r\nint main(){\r\n \r\n    \/\/freopen("in.txt", "r", stdin);\r\n \r\n    D = 1; REP_C(i, _RD(n)) RD(a[i]); REP_C(i, _RD(m)) RD(b[i]);\r\n \r\n    int d; REP_2(i, j, n, m){\r\n        d = __gcd(a[i], b[j]);\r\n        a[i] \/= d, b[j] \/= d, MUL(D, d);\r\n    }\r\n \r\n    OT(D);\r\n}\r\n<\/pre>\n
\r\nLL A[1024]; int mask;\r\nLL res, t;\r\n \r\nLL Cn2(LL x){\r\n    return x * (x - 1) \/ 2;\r\n}\r\n \r\nint main(){\r\n \r\n    \/\/freopen("in.txt", "r", stdin);\r\n \r\n    Rush {\r\n        for (mask = 0,RD(t); t; t \/= 10) mask |= _1(t % 10);\r\n        ++A[mask];\r\n    }\r\n \r\n    FOR(s, 1, 1024) {\r\n        res += Cn2(A[s]);\r\n        FOR(t, s+1, 1024) if (s&t)\r\n        res += A[s] * A[t];\r\n    }\r\n \r\n    OT(res);\r\n}\r\n<\/pre>\n
\r\n.. .\r\nconst int N = 26, C = 100000, CC = C + 9;\r\nVI lc[N], rc[N]; int s[N][CC], ls[N][CC], rs[N][CC], l[N], r[N]; bool root[N];\r\nstring buff; int res, n;\r\n \r\nint stoi(const string &s){\r\n    int res = 0; REP(i, SZ(s)){\r\n        res *= 10, res += s[i] - '0';\r\n    }\r\n    return res;\r\n}\r\n \r\nvoid stat(int x){\r\n    REP_1(i, C) ls[x][i] = sum(ls[x][i-1], s[x][i]);\r\n    DWN_1(i, C, 1) rs[x][i] = sum(rs[x][i+1], s[x][i]);\r\n}\r\n \r\nint main(){\r\n \r\n    \/\/freopen("in.txt", "r", stdin);\r\n \r\n    FLC(root, true); REP_C(i, _RD(n)){\r\n        l[i] = 1, r[i] = C;\r\n        cin >> buff; if ('a' <= buff[0] && buff[0] <= 'z') root[i] = false, lc[buff[0] - 'a'].PB(i); else l[i] = stoi(buff);\r\n        cin >> buff; if ('a' <= buff[0] && buff[0] <= 'z') root[i] = false, rc[buff[0] - 'a'].PB(i); else r[i] = stoi(buff);\r\n    }\r\n \r\n    DWN(i, n, 0) {\r\n        FOR_1(j, l[i], r[i]) {\r\n            s[i][j] = 1;\r\n            REP(ii, SZ(lc[i])) MUL(s[i][j], rs[lc[i][ii]][j]);\r\n            REP(ii, SZ(rc[i])) MUL(s[i][j], ls[rc[i][ii]][j]);\r\n        }\r\n        stat(i);\r\n    }\r\n \r\n    res = 1; REP(i, n) if (root[i]){\r\n        MUL(res, rs[i][1]);\r\n    }\r\n \r\n    OT(res);\r\n}\r\n<\/pre>\n
\r\n.. .\r\n \r\nconst int N = 400009;\r\nint lc[N], rc[N], key[N], sz[N]; LL ss[N], cost[N]; int root, tot;\r\nint L[N], T[N]; LL S;\r\nint n, m, v;\r\n \r\n#define lx lc[x]\r\n#define rx rc[x]\r\n \r\ninline void Update(int x){\r\n    if (x){\r\n        sz[x] = sz[lx] + sz[rx] + 1, ss[x] = ss[lx] + ss[rx] + key[x];\r\n        cost[x] = cost[lx] + cost[rx] + (ss[lx] + key[x]) * (sz[rx] + 1);\r\n    }\r\n}\r\n \r\ninline void rotate(int &x, int lc[], int rc[]){\r\n    int t = rx; rx = lc[t], lc[t] = x;\r\n    Update(x), Update(t), x = t;\r\n}\r\n \r\ninline void maintain(int &x, int lc[], int rc[]){\r\n    if (sz[lc[lx]] > sz[rx]) rotate(x, rc, lc);\r\n    else {\r\n        if (sz[rc[lx]] > sz[rx]) rotate(lx, lc, rc), rotate(x, rc, lc);\r\n        else return;\r\n    }\r\n    maintain(::lx, ::lc, ::rc), maintain(::rx, ::rc, ::lc);\r\n    maintain(x, ::rc, ::lc), maintain(x, ::lc, ::rc);\r\n}\r\n \r\ninline void Insert(int &x = root){\r\n    if (!x){\r\n        x = ++tot, sz[x] = 1;\r\n        cost[x] = ss[x] = key[x] = v;\r\n    }\r\n    else {\r\n        Insert(v < key[x] ? lx : rx), Update(x);\r\n \r\n        \/\/if (v < key[x]) if (sz[lc[lx]] > sz[rx]) rotate(x, rc, lc); else;\r\n        \/\/else if (sz[rc[rx]] > sz[lx]) rotate(x, lc, rc);\r\n \r\n        if (v < key[x]) maintain(x, lc, rc);\r\n        else maintain(x, rc, lc);\r\n    }\r\n \r\n}\r\n \r\ninline int Delete(int &x = root){\r\n    int res; if (v == key[x] || v < key[x] && !lx || v > key[x] && !rx){\r\n        res = key[x];\r\n        if (!lx || !rx) x = lx + rx;\r\n        else {\r\n            int _v = v; v = key[x] + 1;\r\n            key[x] = Delete(lx), v = _v;\r\n        }\r\n    }\r\n    else {\r\n        res = v < key[x] ? Delete(lx) : Delete(rx);\r\n    }\r\n \r\n    Update(x);\r\n    return res;\r\n \r\n}\r\n \r\nint main(){\r\n \r\n    \/\/freopen("in.txt", "r", stdin);\r\n \r\n    RD(n, m); REP(i, n){\r\n        RD(L[i], T[i]), S += L[i];\r\n        v = T[i], Insert();\r\n    }\r\n \r\n    OT(S - cost[root]);\r\n \r\n    int x, l, t, rk; DO(m){\r\n        RD(x, l, t), --x, S -= L[x], S += L[x] = l;\r\n        v = T[x], Delete(), v = T[x] = t, Insert();\r\n        OT(S - cost[root]);\r\n    }\r\n}\r\n<\/pre>\n
\r\n.. .\r\nconst int N = 400009;\r\nint lc[N], rc[N], key[N], sz[N]; LL ss[N], cost[N]; int root, tot;\r\nint L[N], T[N]; LL S;\r\nint n, m, v;\r\n \r\n#define lx lc[x]\r\n#define rx rc[x]\r\n \r\n#define Update ss[x] = ss[lx] + ss[rx] + key[x], cost[x] = cost[lx] + cost[rx] + LL(ss[lx] + key[x]) * (sz[rx] + 1)\r\n \r\ninline void Insert(int &x = root){\r\n    if (!x){\r\n        x = ++tot, sz[x] = 1;\r\n        cost[x] = ss[x] = key[x] = v;\r\n    }\r\n    else {\r\n        ++sz[x], Insert(v < key[x] ? lx : rx);\r\n        Update;\r\n    }\r\n}\r\n \r\ninline int Delete(int &x = root){\r\n    int res; --sz[x]; if (v == key[x] || v < key[x] && !lx || v > key[x] && !rx){\r\n        res = key[x];\r\n        if (!lx || !rx) x = lx + rx;\r\n        else {\r\n            int _v = v; v = key[x] + 1;\r\n            key[x] = Delete(lx), v = _v;\r\n        }\r\n    }\r\n    else {\r\n        res = v < key[x] ? Delete(lx) : Delete(rx);\r\n    }\r\n \r\n    Update;\r\n    return res;\r\n}\r\n \r\nint main(){\r\n \r\n    \/\/freopen("in.txt", "r", stdin);\r\n \r\n    RD(n, m); REP(i, n){\r\n        RD(L[i], T[i]), S += L[i];\r\n        v = T[i], Insert();\r\n    }\r\n \r\n    OT(S - cost[root]);\r\n \r\n    int x, l, t, rk; DO(m){\r\n        RD(x, l, t), --x, S -= L[x], S += L[x] = l;\r\n        v = T[x], Delete(), v = T[x] = t, Insert();\r\n        OT(S - cost[root]);\r\n    }\r\n}\r\n<\/pre>\n
External link: <\/h3>\n
http:\/\/user.qzone.qq.com\/251815992\/blog\/1241924135<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"","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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[62],"tags":[],"class_list":["post-258","post","type-post","status-publish","format-standard","hentry","category-coci"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-4a","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/258","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=258"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/258\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}