{"id":617,"date":"2025-05-05T01:27:41","date_gmt":"2025-05-04T17:27:41","guid":{"rendered":"http:\/\/47.121.202.229\/?p=617"},"modified":"2025-05-05T01:27:42","modified_gmt":"2025-05-04T17:27:42","slug":"2025-5-4-%e5%ba%b7%e5%a4%8d%e8%ae%ad%e7%bb%83","status":"publish","type":"post","link":"http:\/\/47.121.202.229\/?p=617","title":{"rendered":"2025.5.4 \u5eb7\u590d\u8bad\u7ec3"},"content":{"rendered":"\n

p1024<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

p1902<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll=long long;\nint get() {\n\tint x = 0, f = 1;\n\tchar c = getchar();\n\twhile (!isdigit(c)) {\n\t\tif (c == '-') {\n\t\t\tf = -1;\n\t\t}\n\t\tc = getchar();\n\n\t}\n\twhile (isdigit(c)) {\n\t\tx = x * 10 + c - '0';\n\t\tc = getchar();\n\t}\n\treturn x * f;\n}\n\nconst int MaxN = 1005;\nconst int inf = 0x3f3f3f3f;\n\nconst int dx[5] = {0, 1, 0, -1, 0};\nconst int dy[5] = {0, 0, 1, 0, -1};\nint p[MaxN][MaxN], vis[MaxN][MaxN];\nint n, m;\nint l = inf, r = -inf, mid, ans, f;\nbool bfs(int x, int y, int maxn) {\n\tqueue<pair<int, int>> q;\n\tq.push({x, y});\n\tvis[x][y] = 1;\n\twhile (q.size()) {\n\t\tint xx = q.front().first;\n\t\tint yy = q.front().second;\n\t\tq.pop();\n\t\tfor (int i = 1; i <= 4; i++) {\n\t\t\tint nx = xx + dx[i];\n\t\t\tint ny = yy + dy[i];\n\t\t\tif (nx < 1 || nx > n || yy < 1 || yy > m || vis[nx][ny] || p[nx][ny] > maxn) {\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tif (nx == n) {\n\t\t\t\treturn true;\n\t\t\t} else {\n\t\t\t\tvis[nx][ny] = 1;\n\t\t\t\tq.push({nx, ny});\n\t\t\t}\n\n\t\t}\n\t}\n\treturn false;\n}\n\nint main() {\n\tn = get(), m = get();\n\tfor (int i = 1; i <= n; i++) {\n\t\tfor (int j = 1; j <= m; j++) {\n\t\t\tp[i][j] = get();\n\t\t\tr = max(r, p[i][j]);\n\t\t\tl = min(l, p[i][j]);\n\t\t}\n\t}\n\twhile (l <= r) {\n\t\tmid = (l + r) >> 1;\n\t\tf = 0;\n\t\tmemset(vis, 0, sizeof(vis));\n\t\tif (bfs(1, 1, mid)) {\n\t\t\tr = mid - 1;\n\t\t\tans = mid;\n\t\t} else {\n\t\t\tl = mid + 1;\n\t\t}\n\t}\n\tprintf(\"%d\", ans);\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
P1314<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll=long long;\nll n, m, s;\nll y, ans;\nll w[200010], v[200010];\nll l[200010], r[200010];\nll qzh1[200010], qzh2[200010];\nbool check(ll wq) {\n\ty = 0;\n\tmemset(qzh1, 0, sizeof(qzh1));  \n\tmemset(qzh2, 0, sizeof(qzh2));\n\t\n\tfor (int i = 1; i <= n; i++) {\n\t\tif (w[i] > wq)  \n\t\t\tqzh1[i] = qzh1[i - 1] + 1, qzh2[i] = qzh2[i - 1] + v[i]; \n\t\telse\n\t\t\tqzh1[i] = qzh1[i - 1], qzh2[i] = qzh2[i - 1]; \n\t}\n\tfor (int i = 1; i <= m; i++) {\n\t\tint rrrr = r[i];\n\t\tint llll = l[i];\n\t\ty += (qzh1[rrrr] - qzh1[llll - 1]) * (qzh2[rrrr] - qzh2[llll - 1]); \n\t}\n\tif (y > s)\n\t\treturn 1;  \n\telse\n\t\treturn 0;\n}\nint main() {\n\tcin >> n >> m >> s;\n\tfor (int i = 1; i <= n; i++)\n\t\tcin >> w[i] >> v[i];\n\tfor (int i = 1; i <= m; i++)\n\t\tcin >> l[i] >> r[i];\n\tint lll = 1;\n\tint rrr = 2000010;  \n\tans = s;\n\twhile (lll <= rrr) { \n\t\tint mid = lll + (rrr - lll) \/ 2;\n\t\tif (check(mid))\n\t\t\tlll = mid + 1;\n\t\telse\n\t\t\trrr = mid - 1;\n\t\t\tans = min(ans, llabs(s - y));\n\t}\n\tcout << ans;\n}<\/code><\/pre>\n\n\n\n
p4343<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\nint l, k;\nll arr[100005];\nint judge(ll n) {\n    ll sum = 0;\n    int sk = 0;\n    for (int i = 1; i <= l; i++) {\n        sum += arr[i];\n        if (sum >= n) {\n            sk++;\n            sum = 0;\n        } else if (sum < 0) {\n            sum = 0;\n        }\n    }\n    if (sk < k) return 2;\n    else if (sk > k) return 3;\n    else return 1;\n}\nint main() {\n    cin >> l >> k;\n    for (int i = 1; i <= l; i++) cin >> arr[i];\n    \n    ll ansm = -1, ansx = -1;\n    \n    \/\/ \u5bfb\u627e\u6700\u5c0f\u503c\n    ll left = 1, right = 1e18;\n    while (left <= right) {\n        ll mid = (left + right) \/ 2;\n        int res = judge(mid);\n        if (res == 1) {\n            ansm = mid;\n            right = mid - 1;\n        } else if (res == 2) { \/\/ sk <k\uff0cmid\u592a\u5927\n            right = mid - 1;\n        } else { \/\/ res ==3\uff0cmid\u592a\u5c0f\n            left = mid + 1;\n        }\n    }\n    \n    \/\/ \u5bfb\u627e\u6700\u5927\u503c\n    left = 1, right = 1e18;\n    while (left <= right) {\n        ll mid = (left + right) \/ 2;\n        int res = judge(mid);\n        if (res == 1) {\n            ansx = mid;\n            left = mid + 1;\n        } else if (res == 2) { \/\/ sk <k\uff0cmid\u592a\u5927\n            right = mid - 1;\n        } else { \/\/ res ==3\uff0cmid\u592a\u5c0f\n            left = mid + 1;\n        }\n    }\n    \n    if (ansm == -1 || ansx == -1 || ansm > ansx) {\n        cout << -1 << endl;\n    } else {\n        cout << ansm << ' ' << ansx << endl;\n    }\n    \n    return 0;\n}\n\n<\/code><\/pre>\n\n\n\n
p1010<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nvoid divide(int x)\n{\n    bool flag = false; \/\/...\u5224\u65ad\u662f\u5426\u662f\u7b2c\u4e00\u4e2a\uff0c\u5982\u679c\u662f\u7684\u8bdd\u5c31\u4e0d\u8f93\u51fa\u52a0\u53f7\n    while (x != 0)\n    {\n        int t = int(log2(x));\n        \/*\n        log2(x)\u8fd9\u4e2a\u51fd\u6570\u6c42\u4ee52\u4e3a\u5e95x\u7684\u5bf9\u6570\uff0c\u4f8b\u5982log2(8)\u8fd4\u56de3\uff0c\u56e0\u4e3a2^3=8\n        \u800c\u8fd9\u91cc\u628a\u8fd4\u56de\u503c\u5f3a\u5236\u8f6c\u6362\u4e3aint\u662f\u4e3a\u4e86\u627e\u5230\u79bbx\u6700\u8fd1\u53c8\u5c0f\u4e8ex\u7684\u80fd\u8868\u793a\u4e3a2^k\u7684\u6570\n        \u4f8b\u5982int(log2(137))\u5c31\u80fd\u8fd4\u56de7\uff0c\u800c2^7=128\uff0c\u6070\u4e3a\u79bb137\u6700\u8fd1\u7684\u80fd\u8868\u793a\u4e3a2^k\u7684\u6570\n        *\/\n        if (flag) cout << \"+\"; \/\/\u5f00\u5934\u4e0d\u8f93\u51fa\u52a0\u53f7\n        if (t == 1) cout << \"2\"; \/\/\u5982\u679c\u8fd9\u4e00\u9879\u662f1\uff0c\u8f93\u51fa2\uff0c\u4e0d\u9012\u5f52\n        else if (t == 0) cout << \"2(0)\"; \/\/\u5982\u679c\u8fd9\u4e00\u9879\u662f0\uff0c\u8f93\u51fa2(0)\uff0c\u4e0d\u9012\u5f52\n        else\n        {\n            cout << \"2(\";\n            divide(t); \/\/\u9012\u5f52\u4e00\u5c42\uff0c\u628a\u62ec\u53f7\u91cc\u7684\u6570\u5206\u89e3\u8f93\u51fa\n            cout << \")\";\n        }\n        x -= pow(2,t); \/\/\u7ee7\u7eed\u5904\u7406\u4e0b\u4e00\u9879\n        flag = true;\n    }\n}\n\nint main() {\n    int n;\n    cin >> n;\n    divide(n);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
p1208<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\nint n, m;\nstruct Compare {\n\tbool operator()(const pair<int, int> &a, const pair<int, int> &b) {\n\t\treturn a.first > b.first; \/\/ \u5c0f\u6839\u5806\u903b\u8f91\uff08\u7b2c\u4e00\u4e2a\u5143\u7d20\u5347\u5e8f\uff09\n\t}\n};\npriority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;\n\nint main() {\n\n\n\tcin >> n >> m;\n\tint temp1, temp2;\n\tfor (int i = 1; i <= m; i++) {\n\t\tcin >> temp1 >> temp2;\n\t\tpq.push({temp1, temp2});\n\t}\n\tint sum = 0;\n\twhile (n > 0) {\n\t\tint money = pq.top().first;\n\t\tint qut = pq.top().second;\n\t\tif (qut >= n) {\n\t\t\tsum += n * money;\n\t\t\tbreak;\n\t\t} else {\n\t\t\tsum += qut * money;\n\t\t\tn -= qut;\n\t\t\tpq.pop();\n\t\t}\n\t}\n\tcout << sum;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
p4995<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n;\nll ans = 0;\nint arr[305];\nint syb[305];\n\nint main() {\n\tcin >> n;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> arr[i];\n\t}\n\tmemset(syb, 0, sizeof(syb));\n\tint cur = 0;\n\tfor (int i = 1; i <= n; i++) {\n\t\tint max_diff = -1, sid = -1;\n\t\tfor (int j = 1; j <= n; j++) {\n\t\t\tif (syb[j] == 0) {\n\t\t\t\tint diff = abs(arr[j] - cur);\n\t\t\t\tif (diff > max_diff) {\n\t\t\t\t\tmax_diff = diff;\n\t\t\t\t\tsid = j;\n\t\t\t\t} else if (diff == max_diff && arr[j] > arr[sid]) {\n\t\t\t\t\tsid = j;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tsyb[sid] = 1;\n\t\tans += (ll)max_diff * max_diff;\n\t\tcur = arr[sid];\n\t}\n\tcout << ans;\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
p1199<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\n\nint a[510][510];\nint main()\n{\n    int n;\n    scanf(\"%d\",&n);\n    for(int i=1;i<n;i++)\n        for(int j=i+1;j<=n;j++)\n        {\n            scanf(\"%d\",&a[i][j]);\n            a[j][i]=a[i][j];\n        }\n    int ans=0;\n    for(int i=1;i<=n;i++)\n    {\n        sort(a[i]+1,a[i]+1+n);\n        ans=ans>a[i][n-1]?ans:a[i][n-1];\/\/\u9009\u51fa\u6392\u540d\u7b2c\u4e8c\u4e2d\u6700\u5927\u7684\u90a3\u4e2a\n    }\n    printf(\"1\\n%d\\n\",ans);\/\/\u4e00\u5b9a\u6709\u89e3\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
p2672<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nconst int N = 1e5 + 5;\npair<int, int> arr[N];\npriority_queue<int> pq; \nint suffix[N]; \n\nint main() {\n\tint n;\n\tcin >> n;\n\n\tfor (int i = 1; i <= n; ++i)\n\t\tcin >> arr[i].first;\n\tfor (int i = 1; i <= n; ++i)\n\t\tcin >> arr[i].second;\n\n\tsort(arr + 1, arr + n + 1);\n\n\tsuffix[n + 1] = 0;\n\tfor (int i = n; i >= 1; --i) {\n\t\tsuffix[i] = max(suffix[i + 1], 2 * arr[i].first + arr[i].second);\n\t}\n\n\tint select_id = 0, max_gain = 0;\n\tfor (int i = 1; i <= n; ++i) {\n\t\tif (2 * arr[i].first + arr[i].second > max_gain) {\n\t\t\tmax_gain = 2 * arr[i].first + arr[i].second;\n\t\t\tselect_id = i;\n\t\t}\n\t}\n\n\tll sum = max_gain;\n\tint cur_max_s = arr[select_id].first;\n\tcout << sum << endl;\n\n\tfor (int i = 1; i < select_id; ++i) {\n\t\tpq.push(arr[i].second);\n\t}\n\n\tint ptr = select_id; \n\n\t\n\tfor (int k = 2; k <= n; ++k) {\n\t\tint right_gain = 0;\n\t\tif (ptr < n) {\n\t\t\tright_gain = suffix[ptr + 1] - 2 * cur_max_s;\n\t\t}\n\n\t\tint left_gain = (pq.empty() ? -1 : pq.top());\n\n\t\tif (left_gain >= right_gain) {\n\t\t\tsum += left_gain;\n\t\t\tpq.pop();\n\t\t} else {\n\t\t\tsum += right_gain;\n\t\t\t\n\t\t\tint new_s = 0, new_id = 0;\n\t\t\tfor (int i = ptr + 1; i <= n; ++i) {\n\t\t\t\tint val = 2 * arr[i].first + arr[i].second - 2 * cur_max_s;\n\t\t\t\tif (val > new_s) {\n\t\t\t\t\tnew_s = val;\n\t\t\t\t\tnew_id = i;\n\t\t\t\t}\n\t\t\t}\n\t\t\tcur_max_s = arr[new_id].first;\n\t\t\t\n\t\t\tfor (int i = ptr + 1; i < new_id; ++i) {\n\t\t\t\tpq.push(arr[i].second);\n\t\t\t}\n\t\t\tptr = new_id;\n\t\t}\n\n\t\tcout << sum << endl;\n\t}\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
p1024 p1902 P1314 p4343 p1010 p1208 p4995 p1199 p2672<\/p>\n","protected":false},"author":1,"featured_media":634,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[36,19,26],"tags":[],"class_list":["post-617","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-2025-5","category-data_learning","category-26"],"_links":{"self":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts\/617","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=617"}],"version-history":[{"count":3,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts\/617\/revisions"}],"predecessor-version":[{"id":635,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts\/617\/revisions\/635"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/media\/634"}],"wp:attachment":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=617"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=617"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=617"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}