{"id":147,"date":"2018-12-19T00:00:37","date_gmt":"2018-12-18T16:00:37","guid":{"rendered":"http:\/\/wwwwodddd.com\/?p=147"},"modified":"2019-04-17T13:43:59","modified_gmt":"2019-04-17T05:43:59","slug":"usaco-2018-dec","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/usaco-2018-dec\/","title":{"rendered":"USACO 2018 DEC"},"content":{"rendered":"

<\/p>\n

Bronze<\/h1>\n

B1 \/ 843<\/h2>\n

\u6a21\u62df$100$\u6b21\uff0c\u4f3c\u4e4e\u6ca1\u53d1\u73b0\u7b80\u5355\u7684\u5199\u6cd5\u3002<\/p>\n

import sys\nsys.stdin = open('mixmilk.in', 'r')\nsys.stdout = open('mixmilk.out', 'w')\nc = [0, 0, 0]\nm = [0, 0, 0]\nc[0], m[0] = map(int, raw_input().split())\nc[1], m[1] = map(int, raw_input().split())\nc[2], m[2] = map(int, raw_input().split())\nfor i in range(100):\n    m[(i + 1) % 3] += m[i % 3]\n    m[i % 3] = 0\n    if m[(i + 1) % 3] > c[(i + 1) % 3]:\n        m[i % 3] = m[(i + 1) % 3] - c[(i + 1) % 3]\n        m[(i + 1) % 3] = c[(i + 1) % 3]\nprint m[0]\nprint m[1]\nprint m[2]\n<\/code><\/pre>\n
B2 \/ 844<\/h2>\n
\u6bcf\u4e2a\u725b\u76f8\u5f53\u4e8e\u533a\u95f4\u52a0\u4e00\u4e2a\u6570\u5b57\u3002
\n\u6ce8\u610f\u5230\u533a\u95f4\u957f\u5ea6\u548c\u64cd\u4f5c\u6b21\u6570\u90fd\u5f88\u5c11\uff0c\u66b4\u529b\u505a\uff0c\u6216\u8005\u5dee\u5206\u518d\u524d\u7f00\u548c\u90fd\u53ef\u4ee5\u3002<\/p>\n
import sys\nsys.stdin = open('blist.in', 'r')\nsys.stdout = open('blist.out', 'w')\nn = input()\na = [0 for i in range(1000)]\nfor i in range(n):\n    s, t, b = map(int, raw_input().split())\n    for j in range(s - 1, t):\n        a[j] += b\nprint max(a)\n<\/code><\/pre>\n
B3 \/ 845<\/h2>\n
\u4e0d\u9700\u8981\u8003\u8651\u62ff\u8fc7\u53bb\uff0c\u518d\u62ff\u56de\u6765\u76f8\u540c\u7684\u6876\u7684\u60c5\u51b5\u3002
\n\u679a\u4e3e\u4e24\u904d\u62ff$0, 1, 2$\u4e2a\u5230\u5bf9\u9762\uff0c\u5c31\u53ef\u4ee5\u4e86\u3002
\n\u5f53\u7136\uff0c\u62ff\u4e24\u4e2a\u8fc7\u53bb\u7684\u65f6\u5019\uff0c\u4e0d\u80fd\u62ff\u76f8\u540c\u7684$2$\u4e2a\u3002<\/p>\n
import sys\nsys.stdin = open('backforth.in', 'r')\nsys.stdout = open('backforth.out', 'w')\na = map(int, raw_input().split())\nb = map(int, raw_input().split())\ns = set([])\ns.add(0)\nfor i in range(10):\n    for j in range(10):\n        s.add(a[i] - b[j])\nfor i in range(10):\n    for j in range(10):\n        for k in range(i):\n            for l in range(j):\n                s.add(a[i] + a[k] - b[j] - b[l])\nprint len(s)\n<\/code><\/pre>\n
Silver<\/h1>\n
S1 \/ 846<\/h2>\n
\u663e\u7136\u6ee1\u8db3\u4e8c\u5206\u6027\u8d28\uff0c\u4e8c\u5206\u4e00\u4e2a\u65f6\u95f4$x$\uff0c\u6bcf\u4e2a\u8f66\u4e0a\u7684\u725b\u9700\u8981\u6ee1\u8db3\u4e24\u4e2a\u6761\u4ef6\uff1a
\n\u4e2a\u6570 <= $c$\uff0c\u6700\u665a\u51cf\u53bb\u6700\u65e9 <= $x$\uff0c\u8ba1\u7b97\u51fa\u6700\u5c0f\u7684\u8f66\u6570\uff0c\u7136\u540e\u548c$m$\u6bd4\u8f83\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m, c;\nint a[100020];\nbool ok(int x) {\n    int cnt = 0;\n    for (int i = 0; i < n;) {\n        int j = i;\n        while (j < n && j - i < c) {\n            if (a[j] - a[i] > x) {\n                break;\n            }\n            j++;\n        }\n        cnt++;\n        i = j;\n    }\n    return cnt <= m;\n}\nint main() {\n    freopen(\"convention.in\", \"r\", stdin);\n    freopen(\"convention.out\", \"w\", stdout);\n    scanf(\"%d%d%d\", &n, &m, &c);\n    for (int i = 0; i < n; i++) {\n        scanf(\"%d\", &a[i]);\n    }\n    sort(a, a + n);\n    int L = -1;\n    int R = 1e9;\n    while (L < R - 1) {\n        int M = (L + R) \/ 2;\n        if (ok(M)) {\n            R = M;\n        } else {\n            L = M;\n        }\n    }\n    printf(\"%d\\n\", R);\n    return 0;\n}\n<\/code><\/pre>\n
S2 \/ 847<\/h2>\n
\u4f18\u5148\u961f\u5217\uff08\u6216set\uff09\u8d2a\u5fc3
\n\u7b2c\u4e00\u6b21\u6392\u5e8f\uff0c\u6309\u5230\u8fbe\u65f6\u95f4\u6392\u3002
\n\u7136\u540e\u4e00\u4e2awhile<\/code>
\n\u5982\u679c\u6709\u725b\u7684\u5230\u8fbe\u65f6\u95f4\u5c0f\u4e8e\u7b49\u4e8e\u5f53\u524d\u65f6\u95f4\uff0c\u5c31\u52a0\u5165\u8fdb\u6765\u3002
\n\u7279\u522b\u7684\u6ce8\u610f\u5230\u52a0\u5165\u5230\u5806\u91cc\u4e4b\u540e\uff0c\u725b\u662f\u6309\u6807\u53f7\u6392\u7684\u3002
\n\u5982\u679c\u52a0\u4e86\u4e4b\u540e\uff0c\u96c6\u5408\u8fd8\u662f\u7a7a\u7684\uff0c\u90a3\u4e48\u8bf4\u660e\u8fd9\u6bb5\u65f6\u95f4\u4e00\u4e2a\u725b\u90fd\u6ca1\u6709\uff0c\u5c06\u65f6\u95f4\u8bbe\u4e3a\u4e0b\u4e00\u5934\u725b\u5230\u8fbe\u7684\u65f6\u95f4\u5373\u53ef\uff0c\u5e76\u4e14continue<\/code>\u76f4\u63a5\u6267\u884c\u4e0b\u4e00\u8f6e\u5faa\u73af\u3002
\n\u7136\u540e\u601d\u8003\u4e0b\u4e00\u5934\u5f00\u59cb\u7684\u725b\u662f\u8c01\uff0c\u4ed6\u5e94\u8be5\u662f\u5f53\u524d\u96c6\u5408\u4e2d\u6807\u53f7\u6700\u5c0f\u7684\u3002
\n\u66f4\u65b0\u4e00\u4e0b\u7b54\u6848\u3002
\n\u66f4\u65b0\u4e00\u4e0b\u5f53\u524d\u65f6\u95f4
\n\u628a\u8fd9\u5934\u725b\u5220\u6389\uff0c\u8fdb\u5165\u4e0b\u4e00\u8f6e\u3002<\/p>\n
#include <bits\/stdc++.h>\n#define X first\n#define Y second\nusing namespace std;\nint n;\npair<pair<int, int>, int> a[100020];\nint main() {\n    freopen(\"convention2.in\", \"r\", stdin);\n    freopen(\"convention2.out\", \"w\", stdout);\n    scanf(\"%d\", &n);\n    for (int i = 0; i < n; i++) {\n        scanf(\"%d%d\", &a[i].X.X, &a[i].Y);\n        a[i].X.Y = i;\n    }\n    sort(a, a + n);\n    int z = 0, i = 0, t = 0;\n    set<pair<pair<int, int>, int> > s;\n    while (true) {\n        while (i < n && a[i].X.X <= t) {\n            swap(a[i].X.X, a[i].X.Y);\n            s.insert(a[i++]);\n        }\n        if (s.size() == 0) {\n            if (i == n) {\n                break;\n            }\n            t = a[i].X.X;\n            continue;\n        }\n        z = max(z, t - s.begin()->X.Y);\n        t += s.begin() -> Y;\n        s.erase(s.begin());\n    }\n    printf(\"%d\\n\", z);\n    return 0;\n}\n<\/code><\/pre>\n
S3 \/ 848<\/h2>\n
\u901a\u8fc7\u641c\u7d22\uff08BFS\u6216DFS\uff09\u627e\u5230\u8fde\u901a\u7684\u533a\u57df\uff0c\u7136\u540e\u6d88\u53bb\uff0c\u7136\u540e\u6a21\u62df\u4e0b\u843d\u3002
\n\u57fa\u672c\u5c31\u662f mayan\u6e38\u620f \u96be\u5ea6
\n\u5b9e\u73b0\u7ec6\u8282\uff1a
\n1. \u4e00\u822c\u6765\u8bf4DFS\u6bd4BFS\u597d\u5199\uff0c\u5982\u679c\u53ef\u4ee5\u9009\u7684\u8bdd\uff0c\u5efa\u8baeDFS\u3002
\n2. \u8ba1\u6570\u548c\u67d3\u8272\u90e8\u5206\u5206\u5f00\u5199\uff0c\u5982\u679c\u5199\u5728\u4e00\u8d77\uff0c\u975e\u5e38\u9ebb\u70e6\u3002
\n3. \u4e0b\u843d\u7684\u90e8\u5206\uff0c\u6709\u4e0d\u9700\u8981\u989d\u5916\u6570\u7ec4\u7684\u5199\u6cd5\uff0c\u5efa\u8bae\u5b66\u4e60\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint dx[] = {0, 0, 1, -1};\nint dy[] = {1, -1, 0, 0};\nint n, k;\nchar s[120][12];\nbool v[120][12];\nbool in(int x, int y) {\n    return 0 <= x && x < n && 0 <= y && y < 10;\n}\nint dfs(int x, int y, char c) {\n    v[x][y] = true;\n    int re = 1;\n    for (int i = 0; i < 4; i++) {\n        int nx = x + dx[i];\n        int ny = y + dy[i];\n        if (in(nx, ny) && s[nx][ny] == c && !v[nx][ny]) {\n            re += dfs(nx, ny, c);\n        }\n    }\n    return re;\n}\nvoid color(int x, int y, char c) {\n    s[x][y] = '0';\n    for (int i = 0; i < 4; i++) {\n        int nx = x + dx[i];\n        int ny = y + dy[i];\n        if (in(nx, ny) && s[nx][ny] == c) {\n            color(nx, ny, c);\n        }\n    }\n}\nbool gao() {\n    bool flag = false;\n    memset(v, 0, sizeof v);\n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < 10; j++) {\n            if (!v[i][j] && s[i][j] != '0') {\n                int sz = dfs(i, j, s[i][j]);\n                if (sz >= k) {\n                    flag = true;\n                    color(i, j, s[i][j]);\n                }\n            }\n        }\n    }\n    return flag;\n}\nvoid fall() {\n    for (int j = 0; j < 10; j++) {\n        int c = 0;\n        for (int i = 0; i < n; i++) {\n            if (s[i][j] != '0') {\n                s[c++][j] = s[i][j];\n            }\n        }\n        while (c < n) {\n            s[c++][j] = '0';\n        }\n    }\n}\nint main() {\n    freopen(\"mooyomooyo.in\", \"r\", stdin);\n    freopen(\"mooyomooyo.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &k);\n    for (int i = n - 1; i >= 0; i--) {\n        scanf(\"%s\", s[i]);\n    }\n    while (gao()) {\n        fall();\n    }\n    for (int i = n - 1; i >= 0; i--) {\n        printf(\"%s\\n\", s[i]);\n    }\n    return 0;\n}\n<\/code><\/pre>\n
Gold<\/h1>\n
G1 \/ 849<\/h2>\n
\u6c42\u6bcf\u4e2a\u70b9\u5230\u7ec8\u70b9\u7684\u8ddd\u79bb\uff0c\u663e\u7136\u662f\u4ece\u7ec8\u70b9\u53cd\u5411dijkstra\u3002
\n\u7b2c\u4e8c\u6b21\u628a\u6240\u6709haybale\u7684\u8ddd\u79bb\u521d\u59cb\u5316\u4e3a\u7b2c\u4e00\u6b21\u7684\u8ddd\u79bb\u51cf\u53bb\u6536\u76ca\u3002
\n\u8fd9\u4e2a\u503c\u53ef\u80fd\u662f\u8d1f\u6570\uff0c\u518d\u505a\u4e00\u6b21dijkstra\u3002\uff08\u8fb9\u548c\u7b2c\u4e00\u6b21\u662f\u4e00\u6837\u7684\uff09
\n\u7b2c\u4e8c\u6b21dijkstra\u7684\u65f6\u5019\uff0c\u76f8\u5f53\u4e8e\u6709\u591a\u4e2a\u8d77\u70b9\u3002
\n\u5982\u679c\u7b2c\u4e00\u6b21\u8ddd\u79bb<\u7b2c\u4e8c\u6b21\u8ddd\u79bb\uff0c\u90a3\u4e48\u4e0d\u53ef\u80fd\uff0c\u5426\u5219\u53ef\u80fd\u3002<\/p>\n
\u8f93\u5165\u975e\u5e38\u7ed9\u9762\u5b50\uff0chaybale\u7684\u6240\u6709\u4fe1\u606f\u90fd\u4e0d\u9700\u8981\u5b58\u50a8\uff0c\u7528\u540e\u5373\u5f03\u3002
\ndijk\u4e2d\uff0c\u521a\u5f00\u59cb\u628a\u6240\u6709\u70b9\u5165\u961f\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nvector<pair<int, int> > a[50020];\nint n, m, k;\nint d1[50020];\nint d2[50020];\nset<pair<int, int> > s;\nvoid dijk(int *d) {\n    for (int i = 1; i <= n; i++) {\n        s.insert(make_pair(d[i], i));\n    }\n    while (s.size()) {\n        int u = s.begin() -> second;\n        s.erase(s.begin());\n        for (int i = 0; i < a[u].size(); i++) {\n            if (d[a[u][i].first] > d[u] + a[u][i].second) {\n                s.erase(make_pair(d[a[u][i].first], a[u][i].first));\n                d[a[u][i].first] = d[u] + a[u][i].second;\n                s.insert(make_pair(d[a[u][i].first], a[u][i].first));\n            }\n        }\n    }\n}\nint main() {\n    freopen(\"dining.in\", \"r\", stdin);\n    freopen(\"dining.out\", \"w\", stdout);\n    scanf(\"%d%d%d\", &n, &m, &k);\n    for (int i = 0; i < m; i++) {\n        int x, y, z;\n        scanf(\"%d%d%d\", &x, &y, &z);\n        a[x].push_back(make_pair(y, z));\n        a[y].push_back(make_pair(x, z));\n    }\n    memset(d1, 0x3f, sizeof d1);\n    d1[n] = 0;\n    dijk(d1);\n    memset(d2, 0x3f, sizeof d2);\n    for (int i = 0; i < k; i++) {\n        int x, y;\n        scanf(\"%d%d\", &x, &y);\n        d2[x] = d1[x] - y;\n    }\n    dijk(d2);\n    for (int i = 1; i < n; i++) {\n        printf(\"%d\\n\", d1[i] >= d2[i]);\n    }\n}\n<\/code><\/pre>\n
G2 \/ 850<\/h2>\n
\u6ce8\u610f\u5230\u6bcf\u4e2a\u725b\u53ea\u6709$5$\u4e2a\u7231\u597d\u7684\uff0c\u679a\u4e3e$32$\u4e2a\u5b50\u96c6\uff0c\u5bb9\u65a5\u8ba1\u6570\u3002
\n\u7136\u540e\u8003\u8651\u6bcf\u4e2a\u96c6\u5408\u51fa\u73b0\u591a\u5c11\u6b21<\/p>\n
\u5982\u679c\u4e00\u4e2a\u5927\u5c0f\u4e3a\u5076\u6570\uff08\u5305\u62ec$0$\uff09\u7684\u96c6\u5408\u51fa\u73b0$c$\u6b21\uff0c\u90a3\u4e48\u8d21\u732e\u662f$c * (c – 1) \/ 2$
\n\u5982\u679c\u4e00\u4e2a\u5927\u5c0f\u4e3a\u5947\u6570\u7684\u96c6\u5408\u51fa\u73b0$c$\u6b21\uff0c\u90a3\u4e48\u8d21\u732e\u662f$-c * (c – 1) \/ 2$<\/p>\n
\u5982\u679c\u4ea4\u96c6\u975e\u7a7a\uff0c\u90a3\u4e48\u4ea4\u96c6\u7684\u5b50\u96c6\u4e2d\uff0c\u5927\u5c0f\u4e3a\u5947\u6570\u548c\u5927\u5c0f\u4e3a\u5076\u6570\u7684\u4e2a\u6570\u76f8\u7b49\uff0c\u6b63\u8d1f\u62b5\u6d88\u3002
\n\u5982\u679c\u4ea4\u96c6\u4e3a\u7a7a\uff0c\u90a3\u4e48\u4ea4\u96c6\u7684\u5b50\u96c6\u4e2d\uff0c\u53ea\u6709\u4e00\u4e2a\u7a7a\u96c6\uff0c\u8d21\u732e\u6070\u597d\u662f$1$\u3002<\/p>\n
\u4e0b\u9762\u8fd9\u4efd\u4ee3\u7801\u5b9e\u73b0\u7684\u4e0d\u662f\u5f88\u597d\uff0ckey<\/code>\u7684\u90e8\u5206\u57fa\u672c\u662f\u4e71\u5199\u7684\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\ntypedef unsigned long long ull;\ntypedef pair<ull, ull> key;\nmap<key, int> g[2];\nint n, a[5];\nlong long z;\nint main() {\n    freopen(\"cowpatibility.in\", \"r\", stdin);\n    freopen(\"cowpatibility.out\", \"w\", stdout);\n    scanf(\"%d\", &n);\n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < 5; j++) {\n            scanf(\"%d\", &a[j]);\n        }\n        sort(a, a + 5);\n        for (int j = 0; j < 32; j++) {\n            key r;\n            int c = 0;\n            for (int k = 0; k < 5; k++) {\n                if (j >> k & 1) {\n                    r.first = r.first * 233412337 + a[k];\n                    r.second = r.second * 318927319 ^ a[k];\n                    c++;\n                }\n            }\n            g[c % 2][r]++;\n        }\n    }\n    for (pair<key, int> i: g[0]) {\n        z += (long long)i.second * (i.second - 1) \/ 2;\n    }\n    for (pair<key, int> i: g[1]) {\n        z -= (long long)i.second * (i.second - 1) \/ 2;\n    }\n    printf(\"%lld\\n\", z);\n    return 0;\n}\n<\/code><\/pre>\n
G3 \/ 851<\/h2>\n
$O(NK)$\u7684DP\u3002<\/p>\n
f[i]<\/code>\u8868\u793a\u524d$i$\u4e2a\u6570\u5b57\u7684\u6700\u4f18\u89e3\u3002
\nf[i] = f[i - j] + j * max(a[j + 1], a[j + 2], ..., a[i]); (1 <= j <= k)<\/code>
\n\u7136\u540e$i – j \\geq 0$\u5373\u53ef\u3002<\/p>\n
import java.util.Scanner;\nimport java.io.File;\nimport java.io.IOException;\nimport java.io.PrintStream;\n\npublic class Main {\n    static public void main(String[] args) throws IOException {\n        Scanner in = new Scanner(new File(\"teamwork.in\"));\n        PrintStream out = new PrintStream(new File(\"teamwork.out\"));\n        int n = in.nextInt();\n        int k = in.nextInt();\n        int []a = new int[n];\n        for (int i = 0; i < n; i++) {\n            a[i] = in.nextInt();\n        }\n        int []f = new int[n + 1];\n        for (int i = 0; i < n; i++) {\n            int mx = a[i];\n            for (int j = 1; j <= k; j++) {\n                f[i + j] = Math.max(f[i + j], f[i] + j * mx);\n                if (i + j < n) {\n                    mx = Math.max(mx, a[i + j]);\n                } else {\n                    break;\n                }\n            }\n        }\n        out.println(f[n]);\n    }\n}\n<\/code><\/pre>\n
Platinum<\/h1>\n
P1 \/ 852<\/h2>\n
\u51f8\u5305\u3002
\n\u5982\u679c\u521d\u59cb\u5728$i (L \\leq i \\leq R)$\uff0c\u5e76\u4e14$a[L]$\u548c$a[R]$\u5747\u5927\u4e8e$a[i]$\u3002
\n\u90a3\u4e48\u5fc5\u7136\u53ef\u4ee5\u4ee5$a[L]$\u6216\u8005$a[R]$\u7ed3\u675f\u3002
\n\u5982\u679c\u4ece$i$\u51fa\u53d1\uff0c\u6bcf\u6b21\u5411\u5de6\u6216\u5411\u53f3\u8d70\uff0c\u8d70\u5230$L$\u6216$R$\u505c\u6b62\uff0c\u90a3\u4e48
\n\u6700\u7ec8\u505c\u5728$R$\u7684\u6982\u7387\u4e3a$(i – L) \/ (R – L)$\u3002
\n\u6700\u7ec8\u505c\u5728$L$\u7684\u6982\u7387\u4e3a$(R – i) \/ (R – L)$\u3002
\n\u6362\u53e5\u8bdd\u8bf4\uff0c\u8bbe$p_i$\u662f\u505c\u5728$R$\u7684\u6982\u7387\uff0c\u663e\u7136\u6709$p_L = 0, p_R = 1$\u3002
\n\u4e2d\u95f4\u7684$p_i$\u662f\u4e00\u4e2a\u7b49\u5dee\u6570\u5217\u3002<\/p>\n
\u6240\u4ee5\u8bf4\uff0c\u4ece$i$\u51fa\u53d1\uff0c\u6bcf\u6b21\u5411\u5de6\u6216\u5411\u53f3\u8d70\uff0c\u8d70\u5230$L$\u6216$R$\u505c\u6b62\uff0c\u8fd9\u4e2a\u7b56\u7565\u7684\u6536\u76ca\u662f$(a[L] * (R – i) + a[R] * (i – L)) \/ (R – L)$
\n\u6362\u53e5\u8bdd\u8bf4\uff0c\u5982\u679c\u70b9$(i, a_i)$\u5728\u4ece$(L, a[L])$\u5230$(R, a[R])$\u7684\u4e0b\u9762\uff0c\u90a3\u4e48\u4ed6\u5c31\u53ef\u4ee5\u5220\u53bb\u4e86\uff0c\u5269\u4e0b\u7684\u70b9\u6070\u597d\u662f\u4e00\u4e2a\u51f8\u5305\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\ntypedef unsigned long long ull;\nint n;\ndouble a[100020];\nint s[100020], ss;\nlong long xm(long long x1, long long y1, long long x2, long long y2) {\n    return x1 * y2 - x2 * y1;\n}\nint main() {\n    freopen(\"balance.in\", \"r\", stdin);\n    freopen(\"balance.out\", \"w\", stdout);\n    scanf(\"%d\", &n);\n    s[ss++] = 0;\n    for (int i = 1; i <= n + 1; i++) {\n        if (i <= n) {\n            scanf(\"%lf\", &a[i]);\n        }\n        while (ss >= 2 && xm(s[ss - 1] - s[ss - 2], a[s[ss - 1]] - a[s[ss - 2]],\n            i - s[ss - 2], a[i] - a[s[ss - 2]]) > 0) {\n            ss--;\n        }\n        s[ss++] = i;\n    }\n    int t = 0;\n    for (int i = 1; i <= n; i++) {\n        while (i > s[t]) {\n            t++;\n        }\n        ull res = (ull)a[s[t]] * (i - s[t - 1]) + (ull)a[s[t - 1]] * (s[t] - i);\n        res *= 100000;\n        res \/= s[t] - s[t - 1];\n        printf(\"%llu\\n\", res);\n    }\n    return 0;\n}\n<\/code><\/pre>\n
P2 \/ 853<\/h2>\n
\u663e\u7136\u5269\u4e0b\u7684\u90e8\u5206\u76f8\u5bf9\u987a\u5e8f\u4e0d\u4f1a\u6539\u53d8\u3002
\n\u4e5f\u5c31\u662f\u5269\u4e0b\u7684\u90e8\u5206\u5fc5\u987b\u662f\u4e00\u4e2a\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\u3002
\n\u8981\u6c42\u64cd\u4f5c\u7684\u5b57\u5178\u5e8f\u7b2c$k$\u5c0f\uff0c\u4e5f\u5c31\u662f\u5269\u4e0b\u7684\u90e8\u5206\u5b57\u5178\u5e8f\u7b2c$k$\u5927\u3002
\n\u6c42\u5b57\u5178\u5e8f\u7b2ck\u5927\u7684\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\u3002
\n\u5206\u4e3a\u4e24\u90e8\u5206\u6765\u601d\u8003\u3002<\/p>\n
    \n
  1. \u5982\u4f55\u6c42\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\u7684\u4e2a\u6570\uff1f
    \n\u8fd9\u662f\u4e00\u4e2a51nod\u4e0a\u7684\u9898\u76ee\uff0c\u4e0d\u8981\u7528\u4f20\u7edf\u7684\u4e8c\u5206\uff0c\u8d2a\u5fc3\u7684\u601d\u8def\u3002
    \n\u6362\u6210\u6309\u503c\uff0c\u52a8\u6001\u89c4\u5212\uff0c\u6700\u540e\u7528\u7ebf\u6bb5\u6811\u4f18\u5316\u7684\u601d\u8def\u3002<\/p>\n<\/li>\n
  2. \n
    \u5982\u4f55\u627e\u5230\u5b57\u5178\u5e8f\u6700\u5927\u7684\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\uff1f
    \n\u5bf9\u4e8e\u6bcf\u4e2a\u6570\u5b57\uff0c\u5982\u679c\u4ed6\u80fd\u51fa\u73b0\u5728\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\u4e2d\uff0c\u90a3\u4e48\u4ed6\u7684\u4f4d\u7f6e\u662f\u552f\u4e00\u7684\u3002
    \n\u5012\u7740DP\uff0c\u4ece\u7b2c\u4e00\u4f4d\u5411\u540e\u4e00\u4f4d\u4e00\u4f4d\u7684\u786e\u5b9a\u5373\u53ef\u3002<\/p>\n<\/li>\n<\/ol>\n
    #include <bits\/stdc++.h>\nusing namespace std;\ntypedef long long ll;\nint n;\nll k, inf = 4e18;\nint a[262147];\nvector<int> b[262147];\npair<int, ll> t[262147];\nint v[262147];\npair<int, ll> add(pair<int, ll> a, pair<int, ll> b) {\n    if (a.first > b.first) {\n        return a;\n    } else if (a.first < b.first) {\n        return b;\n    } else {\n        return make_pair(a.first, min(a.second + b.second, inf));\n    }\n}\n\npair<int, ll> query(int l, int r, int x, int L, int R) {\n    if (r < L || R < l) {\n        return make_pair(-1, 0);\n    }\n    if (L <= l && r <= R) {\n        return t[x];\n    }\n    int m = (l + r) \/ 2;\n    return add(query(l, m, x * 2, L, R), query(m + 1, r, x * 2 + 1, L, R));\n}\n\nvoid change(int l, int r, int x, int p, pair<int, ll> w) {\n    if (l == r) {\n        t[x] = w;\n        return;\n    }\n    int m = (l + r) \/ 2;\n    if (p <= m) {\n        change(l, m, x * 2, p, w);\n    } else {\n        change(m + 1, r, x * 2 + 1, p, w);\n    }\n    t[x] = add(t[x * 2], t[x * 2 + 1]);\n}\n\nint main() {\n    freopen(\"itout.in\", \"r\", stdin);\n    freopen(\"itout.out\", \"w\", stdout);\n    scanf(\"%d%lld\", &n, &k);\n    for (int i = 1; i <= n; i++) {\n        scanf(\"%d\", &a[i]);\n    }\n    change(1, n + 1, 1, n + 1, make_pair(0, 1));\n    for (int i = n; i > 0; i--) {\n        pair<int, ll> res = query(1, n + 1, 1, a[i], n + 1);\n        res.first++;\n        change(1, n + 1, 1, a[i], res);\n    }\n    for (int i = 1; i <= n; i++) {\n        pair<int, ll> res = query(1, n + 1, 1, i, i);\n        b[res.first].push_back(i);\n    }\n    pair<int, ll> ans = query(1, n + 1, 1, 1, n + 1);\n    int st = 1;\n    int last = 0;\n    assert(k <= ans.second);\n    for (int i = ans.first; i > 0; i--) {\n        for (int jj = b[i].size() - 1; jj >= 0; jj--) {\n            int j = b[i][jj];\n\/\/          if (j < last) {\n\/\/              continue;\n\/\/          }\n            pair<int, ll> res = query(1, n + 1, 1, j, j);\n\/\/          printf(\"pre %d %d %d %lld\\n\", i, j, res.first, res.second);\n            if (k > res.second) {\n                k -= res.second;\n            } else {\n                v[j] = 1;\n                last = j;\n\/\/              printf(\"choose %d\\n\", j);\n                for (; a[st] != j; st++) {\n                    change(1, n + 1, 1, a[st], make_pair(0, 0));\n                }\n                break;\n            }\n        }\n    }\n    printf(\"%d\\n\", n - ans.first);\n    for (int i = 1; i <= n; i++) {\n        if (!v[i]) {\n            printf(\"%d\\n\", i);\n        }\n    }\n    return 0;\n}\n<\/code><\/pre>\n
    P3 \/ 854<\/h2>\n
    \/\/\uff08\u4fdd\u8bc1\u6709\u89e3\uff0c\u867d\u7136\u9898\u76ee\u4f3c\u4e4e\u6ca1\u8bf4\uff09
    \n\/\/\uff08\u65e0\u803b\u7684USACO\u8d5b\u540e\u6539\u6570\u636e\u4e86\uff0c\u5386\u53f2\u5fc5\u5c06\u8bb0\u4e0b\u8fd9\u4e00\u523b\uff01\uff09
    \n\u5927\u6982\u5c31\u662fLCA\uff0c\u5982\u679cx\u8981\u5148\u4e8ey\uff0c\u90a3\u4e48\u4ee5y\u4e3a\u6839\uff0cx\u6574\u4e2a\u5b50\u6811\uff08\u5305\u62ecx\uff09\u90fd\u4e0d\u53ef\u80fd\u662f\u89e3\u3002
    \n\u90a3\u4e48\u4e00\u4e2a\u7b80\u5355\u7684\u5199\u6cd5\u5c31\u662f\uff0c\u627e\u5230\u4ecex\u5230y\u8def\u5f84\u4e0a\u7684\u7b2c\u4e00\u4e2a\u70b9f\u3002
    \n\u7136\u540e\u4ee5$f$\u4e3a\u6839\uff0c\u6807\u8bb0\u5b50\u6811$x$\u4e2d\u6240\u6709\u7684\u70b9\u3002<\/p>\n
    \u56e0\u4e3a\u6bcf\u4e2a\u70b9\u81f3\u591a\u6807\u8bb0\u4e00\u6b21\uff0c\u6240\u4ee5\u590d\u6742\u5ea6\u662f$O(n)$\u7684\u3002
    \n\u6838\u5fc3\u95ee\u9898\u662f\u4ecex\u5230y\u8def\u5f84\u4e0a\u7684\u7b2c\u4e00\u4e2a\u70b9f\uff0c\u8fd9\u4e2a\u5c31\u662fLCA\u3002<\/p>\n
    #include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nvector<int> a[100020];\nvector<int> b[100020];\nint deg[100020];\nint in[100020];\nint f[100020][18];\nint d[100020];\nint L[100020];\nint R[100020];\nint s[100020], ss;\nint v[100020];\nint c[100020];\nvoid dfs(int x, int y) {\n    L[x] = ss;\n    s[ss++] = x;\n    f[x][0] = y;\n    d[x] = d[y] + 1;\n    for (int i = 1; i < 18; i++) {\n        f[x][i] = f[f[x][i - 1]][i - 1];\n    }\n    for (int i: a[x]) {\n        if (i != y) {\n            dfs(i, x);\n        }\n    }\n    R[x] = ss;\n}\n\nint lca(int x, int y) {\n    if (d[x] < d[y]) {\n        swap(x, y);\n    }\n    int dd = d[x] - d[y];\n    for (int i = 0; i < 18; i++) {\n        if (dd >> i & 1) {\n            x = f[x][i];\n        }\n    }\n    if (x == y) {\n        return x;\n    }\n    for (int i = 17; i >= 0; i--) {\n        if (f[x][i] != f[y][i]) {\n            x = f[x][i];\n            y = f[y][i];\n        }\n    }\n    return f[x][0];\n}\n\nbool ok() {\n    queue<int> q;\n    for (int i = 1; i <= n; i++) {\n        if (deg[i] <= 1 && in[i] == 0 && v[i] == 0) {\n            q.push(i);\n            v[i] = 1;\n        }\n    }\n    int cnt = 0;\n    while (q.size()) {\n        int u = q.front();\n        q.pop();\n        cnt++;\n        for (int i: a[u]) {\n            deg[i]--;\n            if (deg[i] <= 1 && in[i] == 0 && v[i] == 0) {\n                q.push(i);\n                v[i] = 1;\n            }\n        }\n        for (int i: b[u]) {\n            in[i]--;\n            if (deg[i] <= 1 && in[i] == 0 && v[i] == 0) {\n                q.push(i);\n                v[i] = 1;\n            }\n        }\n    }\n    return cnt == n;\n}\nint main() {\n    freopen(\"gathering.in\", \"r\", stdin);\n    freopen(\"gathering.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &m);\n    for (int i = 1; i < n; i++) {\n        int x, y;\n        scanf(\"%d%d\", &x, &y);\n        deg[x]++;\n        deg[y]++;\n        a[x].push_back(y);\n        a[y].push_back(x);\n    }\n    dfs(1, 0);\n    for (int i = 0; i < m; i++) {\n        int x, y;\n        scanf(\"%d%d\", &x, &y);\n        b[x].push_back(y);\n        in[y]++;\n        int l = lca(x, y);\n        if (l == x) {\n            c[0]++;\n            c[n]--;\n            if (l == y) {\n                continue;\n            }\n            for (int i = 17; i >= 0; i--) {\n                if (d[f[y][i]] > d[x]) {\n                    y = f[y][i];\n                }\n            }\n            c[L[y]]--;\n            c[R[y]]++;\n        } else {\n            c[L[x]]++;\n            c[R[x]]--;\n        }\n    }\n\n    if (!ok()) {\n        for (int i = 1; i <= n; i++) {\n            printf(\"0\\n\");\n        }\n        return 0;\n    }\n\n    for (int i = 0; i < n; i++) {\n        c[i + 1] += c[i];\n    }\n    for (int i = 1; i <= n; i++) {\n        printf(\"%d\\n\", c[L[i]] == 0);\n    }\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[4],"class_list":["post-147","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-usaco"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/147","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/comments?post=147"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/147\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=147"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=147"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=147"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}