{"id":4,"date":"2019-02-20T22:32:16","date_gmt":"2019-02-20T14:32:16","guid":{"rendered":"https:\/\/blog.kaaass.net\/acm\/?p=4"},"modified":"2019-02-22T16:22:01","modified_gmt":"2019-02-22T08:22:01","slug":"jlu-winter","status":"publish","type":"post","link":"https:\/\/blog.kaaass.net\/acm\/2019\/02\/jlu-winter\/","title":{"rendered":"JLU\u5bd2\u5047\u6a21\u62df\u8d5b\u89e3\u9898\u601d\u8def\u7b14\u8bb0"},"content":{"rendered":"

\u5bd2\u5047\u9893\u5e9f\u4e86\u5f88\u4e45\uff0c\u679c\u7136\u83dc\u7684\u62a0\u811a\u3002\u867d\u7136\u6ca1\u6709\u6574\u573a\u6253\u4e0b\u6765\uff0c\u4f46\u662f\u4f9d\u65e7\u6539\u53d8\u4e0d\u4e86\u6211\u83dc\u7684\u4e8b\u5b9e\u3002\u59d1\u4e14\u8bb0\u4e00\u4e0b\u3002<\/p>\n

<\/p>\n

A – \u5199\u6587\u6848\uff08CodeForces 165B\uff09<\/h1>\n

\u601d\u8def\u5f88\u7b80\u5355\uff0c\u5148\u786e\u5b9a\u8fb9\u754c\u7136\u540e\u518d\u641c\u7d22\u3002<\/p>\n

S = v + \\left\\lfloor \\frac{v}{k} \\right\\rfloor + \\left\\lfloor \\frac{v}{k^{2}} \\right\\rfloor + ... + \\left\\lfloor \\frac{v}{k^{p}} \\right\\rfloor<\/span><\/p>\n

\u5176\u4e2d\uff0cp\u6ee1\u8db3\\left\\lfloor \\frac{v}{k^{p+1}} \\right\\rfloor = 0<\/span>\u3002\u7b80\u5355\u653e\u7f29\u53d6\u4e00\u4e2a\u4e0b\u754c\uff1a<\/p>\n

n \\leq S < v \\cdot \\left( 1 + \\frac{1}{k} + ... + \\frac{1}{k^{p}} \\right) < \\frac{v-\\frac{v}{k^{p}}}{1-\\frac{1}{k}}<\/span><\/p>\n

v > (1+\\frac{1}{k}) \\cdot n -1<\/span><\/p>\n

\u4e2d\u9014\u8bb0\u9519\u4e86\u7b49\u6bd4\u6c42\u548c\uff0c\u5361\u4e86\u4e00\u54c8\u3002<\/p>\n

#include <iostream>\r\n\r\n#define LL long long\r\nusing namespace std;\r\n\r\nLL calc_limit(LL k, LL n) {\r\n    return n - n \/ k - 1;\r\n}\r\n\r\nLL calc(LL v, LL k) {\r\n    LL t = 1, acc = 0;\r\n    while (v \/ t > 0) {\r\n        acc += v \/ t;\r\n        t *= k;\r\n    }\r\n    return acc;\r\n}\r\n\r\nint main() {\r\n    LL n, k, i;\r\n    cin >> n >> k;\r\n    i = calc_limit(k, n);\r\n    while (calc(i, k) < n) i++;\r\n    cout << i << endl;\r\n    return 0;\r\n}<\/pre>\n
B – \u6446\u77f3\u5b50\uff08HDU 4248\uff09<\/h1>\n
\u7eaf\u7528\u6392\u5217\u597d\u50cf\u5f88\u590d\u6742\uff0c\u6211\u8c14\u8c14\u3002\u611f\u89c9\u662fdp\uff0c\u77ed\u65f6\u95f4\u6ca1\u5199\u51fa\u8f6c\u79fb\u65b9\u7a0b\uff0c\u8df3\u4e86\u3002\u4e4b\u540e\u60f3\u4e86\u4e00\u4e0b\uff0c\u591a\u7ec4\u6570\u636e\u611f\u89c9dp\u53ef\u80fd\u60ac\uff1f\u8303\u56f4\u5012\u662f\u8fd8\u597d\uff0c\u4e22\u4e2a\u72b6\u8f6c\u3002<\/p>\n
dp\\left[ i, j \\right] = dp\\left[ i-1, j - k \\right] \\cdot \\left( {k \\atop j} \\right)<\/span><\/p>\n
i\u662f\u52a0\u5165\u7684\u7ec4\uff0cj\u662f\u5e8f\u5217\u957f\u5ea6\uff0ck\u4e3a\u7ec4i\u52a0\u5165\u7684\u6570\u76ee\u3002\u4ee5\u540e\u5199\uff08\u5495\uff09<\/p>\n
C – \u7b97\u6570\u5b57\uff08POJ 2739\uff09<\/h1>\n
\u5199\u4e86\u4e00\u8f88\u5b50\u7684\u5f31\u667a\u9898\u3002\u7ebf\u6027\u7b5b+\u679a\u4e3e\u5e8f\u5217\u5c3e\u3002\u7ed3\u679c\u9996\u5148\u662f\u65e0\u9650RE\u3002\u4ee5\u4e3a\u662f\u6570\u7ec4\u4e0b\u6807\u8d8a\u754c\uff0c\u751a\u81f3\u6570\u7ec4\u6ca1\u521d\u59cb\u5316\u3001_for\u5b8f\u90fd\u6000\u7591\u4e86\uff0c\u7ed3\u679c\u5176\u5b9e\u662f\u6709\u4e2a\u53d8\u91cf\u6ca1\u521d\u59cb\u5316\u3002\u7136\u800c\u8fd8\u6709\u95ee\u9898\uff0c\u5c31\u662f\u67e5\u627e\u5e8f\u5217\u5c3e\u7684\u51fd\u6570\uff0c\u6539\u7684\u65f6\u5019\u6f0f\u4e86\u6539\u6700\u540e\u7684return\u3002<\/p>\n
int near(int n) {\r\n    for (int i=1; i < ind; i++) {\r\n        if (prime[i]>=n)\r\n            return i;\r\n    }\r\n    return 1;\r\n}<\/pre>\n
\u5e94\u8be5\u8fd4\u56de\u6700\u540e\u4e00\u4e2a\u7d20\u6570\u7684\u4e0b\u6807\u3002\u5f88\u597d\u7684\u6559\u8bad\u3002<\/p>\n
D – \u590d\u5236\u73a9\u5177\uff08CodeForces 922A\uff09<\/h1>\n
\u8fd9\u4e2ax – (y – 1)\u5224\u65ad\u4e0b\u5c31\u884c\uff0c\u7ed3\u679c\u6c99\u96d5\u7684\u4ee5\u4e3a!(x >= 0 && y >= 1)\u7684\u6761\u4ef6\u53ef\u4ee5\u5305\u62ecy == 1 && x != 0\u4e86\u3002\u5f53\u65f6\u4ee5\u4e3a\u662f\u6570\u636e\u8303\u56f4\u7684\u95ee\u9898\uff0c\u6240\u4ee5\u5199\u5927\u6570\u7c7b\u53bb\u4e86\u3002\u7136\u540e\u5c31\u6ca1\u65f6\u95f4\u4e86\uff0c\u771f\u662f\u6c99\u96d5\u3002<\/p>\n
E – \u86d9\u8df3\uff08CodeForces 1077A\uff09<\/h1>\n
\u7b7e\u5230\u9898<\/p>\n
#include<iostream>\r\n\r\nusing namespace std;\r\n\r\nint main() {\r\n    long long a, b, k, offset, kase;\r\n    cin >> kase;\r\n    while (kase--) {\r\n        cin >> a >> b >> k;\r\n        offset = a - b;\r\n        cout << offset * (k \/ 2) + (k % 2 ? a: 0) << endl;\r\n    }\r\n    return 0;\r\n}<\/pre>\n
F – \u5730\u94c1\uff08POJ 2502\uff09<\/h1>\n
\u5199\u5b8c\u7ed3\u70b9\u8bfb\u5165\u548c\u8ddd\u79bb\u8ba1\u7b97\u5c31\u53ea\u5269\u534a\u5c0f\u65f6\u4e86\uff0c\u6253\u6270\u4e86\u3002\u4e4b\u540e\u8865\uff08\u5495\uff09<\/p>\n
G – \u534a\u7d20\u6570\uff08CodeForces 26A\uff09<\/h1>\n
\u7ebf\u6027\u7b5b+\u56e0\u6570\u8ba1\u6570\uff0c>2\u7684\u53ef\u4ee5\u76f4\u63a5\u653e\u8fc7\u3002<\/p>\n
int main() {\r\n    int n, num = 0, pri;\r\n    cin >> n;\r\n    seive(n);\r\n    memset(mark, 0, sizeof(mark));\r\n    for (int i = 1; i < total; i++) {\r\n        pri = primes[i];\r\n        if (n \/ pri < 1) break;\r\n        for (int i = 4; i <= n; i++) {\r\n            if (mark[i] > 2) continue;\r\n            mark[i] += i % pri == 0;\r\n        }\r\n    }\r\n    for (int i = 4; i <= n; i++) {\r\n        if (mark[i] == 2) {\r\n            num++;\r\n        }\r\n    }\r\n    cout << num << endl;\r\n    return 0;\r\n}<\/pre>\n
H – \u9aa8\u724c\u6446\u653e(POJ 2506)<\/h1>\n
\u5f53\u65f6\u8df3\u4e86\uff0c\u540e\u6094\u4e86\u3002\u5176\u5b9e\u7c7b\u4f3c\u6590\u6ce2\u90a3\u5951\uff0c\u5c31\u662f\u4e00\u4e2a\u9012\u63a8\u3002F(n)=F(n-1)+2*F(n-2)\u3002<\/p>\n
I – \u51e0\u70b9\u4e86\uff08HDU 6077\uff09<\/h1>\n
\u8fd9\u4e2a\u8df3\u4e86\uff0c\u66f4\u540e\u6094\u4e86\u3002\u5176\u5b9e\u627e\u4e00\u4e24\u4e2a\u7279\u5f81\u70b9\u5c31\u884c\u3002\u5f53\u65f6\u89c9\u5f97\u627e\u8d77\u6765\u6162\u5c31\u8fc7\u4e86\u3002<\/p>\n
J – \u5339\u914d\u5b57\uff08HDU 2222\uff09<\/h1>\n
\u8df3\u4e86\u4e24\u4e2a\u7b80\u5355\u7684\u7136\u540e\u9009\u4e86J\uff0c\u771f\u7684\u6c99\u96d5\u3002\u5f53\u65f6\u60f320\u5206\u949f\uff0c\u5c31\u5199\u4e2akmp\u640f\u4e00\u640f\u5427\u3002\u679c\u7136\u4e8b\u60c5\u6ca1\u90a3\u4e48\u7b80\u5355\uff0cTLE\u4e86\uff0c\u7136\u540e\u6bd4\u8d5bTLE\u4e86\u3002<\/p>\n
\u53cd\u601d<\/h1>\n
\u9898\u505a\u7684\u4e0d\u591f\uff0c\u89e3\u51b3\u95ee\u9898\u5b8c\u5168\u6ca1\u6761\u7406\u3002\u51fa\u4e86\u9519\u51e0\u4e4e\u662f\u624b\u5fd9\u811a\u4e71\u7684\u3002\u65f6\u95f4\u5206\u914d\u4e0d\u5408\u7406\u3002<\/p>","protected":false},"excerpt":{"rendered":"
\u5bd2\u5047\u9893\u5e9f\u4e86\u5f88\u4e45\uff0c\u679c\u7136\u83dc\u7684\u62a0\u811a\u3002\u867d\u7136\u6ca1\u6709\u6574\u573a\u6253\u4e0b\u6765\uff0c\u4f46\u662f\u4f9d\u65e7\u6539\u53d8\u4e0d\u4e86\u6211\u83dc\u7684\u4e8b\u5b9e\u3002\u59d1\u4e14\u8bb0\u4e00\u4e0b\u3002<\/p>","protected":false},"author":1,"featured_media":5,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-4","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-2","entry"],"_links":{"self":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/posts\/4","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/comments?post=4"}],"version-history":[{"count":0,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/posts\/4\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/media\/5"}],"wp:attachment":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/media?parent=4"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/categories?post=4"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/tags?post=4"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}