{"id":290,"date":"2018-06-01T09:54:07","date_gmt":"2018-06-01T09:54:07","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=290"},"modified":"2018-06-05T10:26:16","modified_gmt":"2018-06-05T10:26:16","slug":"2018-%e8%ae%a1%e8%92%9c%e4%b9%8b%e9%81%93-%e5%88%9d%e8%b5%9b-%e7%ac%ac%e5%85%ad%e5%9c%ba","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=290","title":{"rendered":"2018 \u8ba1\u849c\u4e4b\u9053 \u521d\u8d5b \u7b2c\u516d\u573a"},"content":{"rendered":"

A:\u8d1d\u58f3\u627e\u623f<\/h2>\n

\u9898\u89e3\uff1a\u6253\u8868\uff0c\u9884\u5904\u74061e5\u7684\u8868\uff0c\u7136\u540e\u6839\u636e\u8868\u8fdb\u884c\u67e5\u8be2\u3002
\n\u9898\u76ee\u8bf4\u4e86\u6709\u5e8f\uff0c\u4e0d\u77e5\u9053\u4f1a\u4e0d\u4f1a\u6709\u964d\u5e8f\uff0c\u603b\u4e4b\u5199\u4e86\u4e5f\u8fc7\u4e86<\/p>\n

#include <iostream>\n#include <algorithm>\n#include <array>\n#include <limits>\n#include <cmath>\n#include <map>\n#include <iomanip>\n\nusing namespace std;\nusing ll = long long;\nusing db = double;\nmap<ll, ll> house;\n\nint main() {\n    ios::sync_with_stdio(false);\n    house[1] = 1;\n    ll prev = 1;\n    for (int i = 2; i <= 1e5 + 3; ++i) {\n        ll cur = prev + i + 1;\n        house[cur] = i;\n        prev = cur;\n    }\n    int n;\n    cin >> n;\n    while (n--) {\n        int num;\n        cin >> num;\n        prev = -1;\n        bool dir = false;\n        bool ok = true;\n        ll dis = 0;\n        if (num == 1) {\n            int cur;\n            cin >> cur;\n            ll pos = house[cur];\n            if (!pos) {\n                cout << \"no\" << endl;\n            } else {\n                cout << \"yes\" << endl;\n            }\n        } else {\n            while (num--) {\n                int cur;\n                cin >> cur;\n                if (prev == -1) {\n                    ll pos = house[cur];\n                    if (!pos) {\n                        ok = false;\n                        prev = 0;\n                        continue;\n                    } else {\n                        ok = true;\n                    }\n                    prev = pos;\n                    continue;\n                } else {\n                    if (!ok)continue;\n                    auto pos = house[cur];\n                    if(!pos)\n                    {\n                        ok = false;\n                        continue;\n                    }\n                    if(!dir)\n                    {\n                        dir = true;\n                        dis = prev - pos;\n                        if(abs(dis)>1)\n                        {\n                            ok = false;\n                            continue;\n                        }\n                        prev = pos;\n                        continue;\n                    }\n                    if(prev - pos == dis)\n                    {\n                        prev = pos;\n                        continue;\n                    }\n                    else {\n                        ok = false;\n                    }\n                }\n\n      }\n        if (ok) {\n            cout << \"yes\" << endl;\n        } else {\n            cout << \"no\" << endl;\n        }\n    }\n}\n}\n<\/code><\/pre>\n
B \u8d1d\u58f3\u627e\u623f\u79fb\u5c71\uff08\u7b80\u5355\uff09<\/h2>\n
\u9898\u89e3:\u56de\u6eaf\u3002\u7531\u4e8e\u9898\u76ee\u8303\u56f4\u5f88\u5c0f\u53ef\u4ee5\u5bb9\u5fcd\u590d\u6742\u5ea6\u76f8\u5f53\u9ad8\u7684\u7b97\u6cd5\u3002\u56e0\u6b64\u968f\u4fbf\u641e\u4e00\u4e2a\u56de\u6eaf\u5c31\u80fd\u8fc7<\/p>\n
#include <iostream>\n#include <algorithm>\n#include <array>\n#include <limits>\n#include <cmath>\n#include <map>\n#include <iomanip>\n#include <queue>\n#include <functional>\n\nusing namespace std;\nusing ll = long long;\nusing db = double;\n\nstruct Mountain {\n    int start, end, height;\n\n    Mountain() {}\n\n    Mountain(int s, int e, int h) : start(s), end(e), height(h) {}\n\n    bool operator<(const Mountain v) const {\n        if (height != v.height)\n            return height > v.height;\n        else\n            return end - start < v.end - v.start;\n    }\n};\narray<int, 10> road{};\nint n, k;\nint cnt = 0x3f3f3f3f;\n\nvoid dfs(int _cnt)\n{\n    vector<Mountain> q;\n    int status = 0;\n    int spos = 0;\n    for (int i = 1; i <= n + 1; ++i) {\n        if (status == 1) {\n            if (road[i] < road[i - 1]) {\n                status = 0;\n                q.push_back(Mountain(spos, i - 1, min(road[spos] - road[spos - 1], road[i - 1] - road[i])));\n            } else if (road[i] > road[i - 1]) {\n                spos = i;\n            }\n        } else {\n            if (road[i] > road[i - 1]) {\n                status = 1;\n                spos = i;\n            }\n        }\n    }\n    if (q.size() > k) {\n        for(auto el:q)\n        {\n            auto top = el;\n            int s = top.start;\n            int e = top.end;\n            for (int i = s; i <= e; ++i) {\n                --road[i];\n            }\n            dfs(_cnt+1);\n            for (int i = s; i <= e; ++i) {\n                ++road[i];\n            }\n        }\n\n    } else {\n        cnt = min(_cnt,cnt);\n    }\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n    int T;\n    cin >> T;\n    while (T--) {\n        cin >> n >> k;\n        for (int i = 1; i <= n; ++i) {\n            cin >> road[i];\n        }\n        road[n + 1] = road[0] = 0;\n        cnt = 0x3f3f3f3f;\n        dfs(0);\n        cout << cnt << endl;\n    }\n}\n<\/code><\/pre>\n
C \u8d1d\u58f3\u627e\u623f\u79fb\u5c71\uff08\u4e2d\u7b49\uff09<\/h2>\n
\u9898\u89e3:\u679a\u4e3e\u6240\u6709\u7684\u5c71\u5cf0\u5c71\u8c37\uff0c\u4e00\u8d77\u6d88\u53bb\u5c31\u884c<\/p>\n
#include <iostream>\n#include <algorithm>\n#include <vector>\nusing namespace std;\nusing ll = long long;\nll n, k, t;\nll a;\nvector<ll> high;\n\nint main() {\n    cin >> t;\n    for (ll q = 1; q <= t; q++) {\n        cin >> n >> k;\n        ll last = 0, ans = 0;\n        high.clear();\n        bool which = true;\n        high.push_back(0);\n        for (ll i = 1; i <= n; i++) {\n            cin >> a;\n            if (which) {\n                if (a < last) {\n                    high.push_back(last);\n                    which = false;\n                }\n            } else {\n                if (a > last) {\n                    high.push_back(last);\n                    which = true;\n                }\n            }\n            last = a;\n        }\n        if (which) {\n            high.push_back(last);\n            high.push_back(0);\n        } else\n            high.push_back(0);\n        auto numofsf = static_cast<ll>(high.size() \/ 2);\n        for (ll i = 1; i <= numofsf - k; i++) {\n            ll willdel = 1;\n            for (ll j = 1; j <= high.size() \/ 2; j++) {\n                if (high[j * 2 - 1] - (max(high[j * 2 - 2], high[j * 2])) <\n                    high[willdel] - max(high[willdel - 1], high[willdel + 1]))\n                    willdel = j * 2 - 1;\n            }\n            if (high[willdel + 1] > high[willdel - 1]) {\n                ans += high[willdel] - high[willdel + 1];\n                high.erase(high.begin() + willdel);\n                high.erase(high.begin() + willdel);\n            } else {\n                ans += high[willdel] - high[willdel - 1];\n                high.erase(high.begin() + willdel - 1);\n                high.erase(high.begin() + willdel - 1);\n            }\n        }\n        cout << ans << endl;\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
A:\u8d1d\u58f3\u627e\u623f \u9898\u89e3\uff1a\u6253\u8868\uff0c\u9884\u5904\u74061e5\u7684\u8868\uff0c\u7136\u540e\u6839\u636e\u8868\u8fdb\u884c\u67e5\u8be2\u3002 \u9898\u76ee\u8bf4\u4e86\u6709\u5e8f\uff0c\u4e0d\u77e5\u9053\u4f1a\u4e0d\u4f1a\u6709\u964d\u5e8f\uff0c\u603b\u4e4b\u5199\u4e86\u4e5f […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[22],"tags":[24],"class_list":["post-290","post","type-post","status-publish","format-standard","hentry","category-22","tag-cpp"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-4G","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/290","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=290"}],"version-history":[{"count":5,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/290\/revisions"}],"predecessor-version":[{"id":295,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/290\/revisions\/295"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}