{"id":465,"date":"2023-04-01T12:50:03","date_gmt":"2023-04-01T04:50:03","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=465"},"modified":"2025-03-19T00:35:13","modified_gmt":"2025-03-18T16:35:13","slug":"acwing-4645-%e9%80%89%e6%95%b0%e5%bc%82%e6%88%96","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=465","title":{"rendered":"Acwing 4645. \u9009\u6570\u5f02\u6216"},"content":{"rendered":"

\"file\"\"file\"<\/p>\n

\u4e00\u9053\u6709\u70b9\u96be\u7684DP<\/p>\n

\u5206\u6790\u9898\u610f\u8bbe\u8ba1dp\u601d\u8def\uff1a<\/p>\n

\u6839\u636e\u5f02\u6216\u8fd0\u7b97\u7684\u6027\u8d28\uff0c\u79fb\u9879\u5f97a[j] = a[i] ^ x\uff0c\u4e0d\u59a8\u8bbej < i<\/p>\n

\u6211\u4eec\u5e0c\u671b\u679a\u4e3e\u6bcf\u4e00\u4e2aa[i]\uff0c\u5e76\u627e\u5230\u5176\u5de6\u8fb9\u6700\u8fd1\u7684a[j]\u4ee4 a[j] = a[i] ^ x\uff0c\u6b64\u65f6\u6211\u4eec\u79f0a[i], a[j]\u4e3a\u4e00\u4e2a\u5408\u6cd5\u6570\u5bf9\uff0cj\u4e3a\u8be5\u6570\u5bf9\u7684\u4e0b\u754c<\/p>\n

\u7528dp[i]\u8868\u793a\u533a\u95f41~i\u5185\u7684\u5408\u6cd5\u6570\u5bf9\u7684\u6700\u5927\u4e0b\u754c<\/strong>\uff0c\u5219\u5bf9\u4e8e\u4e00\u6b21\u8be2\u95eeL\uff0cR\u53ef\u4ee5\u5224\u5b9a\u5982\u679cdp[R] >= L\u5219\u8bf4\u660e\u5728\u8be5\u533a\u95f4\u4e2d\u5b58\u5728\u5408\u6cd5\u6570\u5bf9<\/p>\n

dp\u8f6c\u79fb\u516c\u5f0f<\/p>\n

dp[i] = max(dp[i - 1], last[a[i] ^ x])<\/code><\/pre>\n
\u5176\u4e2dlast\u662f\u54c8\u5e0c\u8868\uff0clast[i]\u4ee3\u8868i\u51fa\u73b0\u7684\u6700\u540e\u4f4d\u7f6e\uff0c\u6ca1\u6709\u51fa\u73b0\u8fc7\u5219\u4e3a0<\/p>\n
\u4e0a\u8ff0\u516c\u5f0f\u7684\u542b\u4e49\u662f\uff0cdp[i]\u7684\u8d21\u732e\u6765\u6e90\u6709\u4e24\u4e2a\uff0c\u4e00\u4e2a\u662f\u533a\u95f41~i – 1\uff0c\u4e00\u4e2a\u662fa[i] ^ x\uff0c\u4e5f\u5c31\u662f\u8bf4\uff0c\u53d6\u4ed6\u524d\u4e00\u4e2a\u72b6\u6001\u7684\u503c\u4e0ea[i] ^ x\uff0c\u5373\u4e0a\u9762\u7684a[j]\u6700\u540e\u51fa\u73b0\u7684\u4f4d\u7f6e\u7684\u6700\u5927\u503c<\/p>\n
#include <bits\/stdc++.h>\n\nusing namespace std;\n\nconst int N = 1e5 + 10;\nint a[N], dp[N];\n\n\/\/ dp[i] \u8868\u793a 1~i \u4e2d\u5408\u6cd5\u6570\u5bf9\u7684\u6700\u5927\u4e0b\u754c\n\nint main()\n{\n    int n, m, x;\n    cin >> n >> m >> x;\n\n    unordered_map<int, int> last;   \/\/ last[i] \u8868\u793ai\u51fa\u73b0\u7684\u6700\u540e\u4f4d\u7f6e\n    for (int i = 1; i <= n; i++)\n    {\n        cin >> a[i];\n        dp[i] = max(dp[i - 1], last[a[i] ^ x]);\n        last[a[i]] = i;\n    }\n\n    while (m--)\n    {\n        int l, r;\n        cin >> l >> r;\n        cout << (dp[r] >= l ? "yes" : "no")<< endl;\n    }\n    return 0;\n}\n<\/code><\/pre>\n
\u7b97\u6cd5\u590d\u6742\u5ea6O(m + n)<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u9053\u6709\u70b9\u96be\u7684DP \u5206\u6790\u9898\u610f\u8bbe\u8ba1dp\u601d\u8def\uff1a \u6839\u636e\u5f02\u6216\u8fd0\u7b97\u7684\u6027\u8d28\uff0c\u79fb\u9879\u5f97a[j] = […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,16,23],"tags":[],"class_list":["post-465","post","type-post","status-publish","format-standard","hentry","category-dp","category-16","category-23"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/465","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=465"}],"version-history":[{"count":2,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/465\/revisions"}],"predecessor-version":[{"id":843,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/465\/revisions\/843"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=465"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=465"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=465"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}