{"id":78,"date":"2023-03-16T15:49:56","date_gmt":"2023-03-16T07:49:56","guid":{"rendered":"https:\/\/solost.cn\/?p=78"},"modified":"2023-03-16T15:49:56","modified_gmt":"2023-03-16T07:49:56","slug":"168","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=78","title":{"rendered":"Acwing – 1497. \u6811\u7684\u904d\u5386"},"content":{"rendered":"

\"image(1).png\"<\/p>\n

\u9898\u76ee\u94fe\u63a5<\/h2>\n

\u9898\u76ee\u94fe\u63a5<\/a><\/p>\n

solution<\/h2>\n

\"E24B2DA983D0779AC64D62EBD55B3948.png\"<\/p>\n

\u7531\u4e8e\u7ed9\u51fa\u7684\u662f\u540e\u5e8f\u904d\u5386\u4e0e\u4e2d\u5e8f\u904d\u5386\uff0c\u540e\u7eed\u904d\u5386\u7684\u904d\u5386\u987a\u5e8f\u662f\u5de6\u53f3\u6839\uff0c\u4e2d\u5e8f\u904d\u5386\u7684\u987a\u5e8f\u662f\u6839\u5de6\u53f3\uff0c\u6240\u4ee5\u6211\u4eec\u5148\u7528\u540e\u5e8f\u904d\u5386\u786e\u5b9a\u6839\u8282\u70b9\uff0c\u7136\u540e\u518d\u5728\u4e2d\u5e8f\u904d\u5386\u91cc\u9762\u627e\u5230\u8be5\u8282\u70b9\uff0c\u7136\u540e\u8be5\u8282\u70b9\u5de6\u8fb9\u5c31\u662f\u5de6\u5b50\u6811\uff0c\u53f3\u8fb9\u5c31\u662f\u53f3\u5b50\u6811\uff0c\u5de6\u5b50\u6811\u7684\u6570\u91cf\u5c31\u662fk - bl + 1<\/code>,\u90a3\u4e48\u5bf9\u5e94\u5230\u540e\u5e8f\u904d\u5386\u91cc\u9762\u5c31\u662fal - (k - bl + 1) == al - k + bl - 1<\/code>,\u7136\u540e\u518d\u5904\u7406\u53f3\u5b50\u6811\uff0c\u5c31\u662f\u540e\u5e8fal - k + bl<\/code>\u5230ar - 1<\/code>\uff0c\u4e2d\u5e8fk + 1<\/code>\u5230br<\/code>\uff0c\u4e0d\u65addfs\u5373\u53ef<\/p>\n

\u4e0d\u7528DFS\u7248\u672c<\/h3>\n
#include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <iostream>\n#include <map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <unordered_map>\n#include <vector>\n\nusing namespace std;\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\ntypedef long long ll;\ntypedef pair<int, int> PII;\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2e5 + 10;\n\nint a[N], b[N], p[N];\nvector<int> level[N];\n\nvoid build(int al, int ar, int bl, int br, int d)\n{\n    if (al > ar)\n        return;\n    int root = a[ar];\n    int k = p[root];\n    level[d].push_back(root);\n    build(al, al + k - bl - 1, bl, k - 1, d + 1);\n    build(al + k - bl, ar - 1, k + 1, br, d + 1);\n}\n\nvoid solve()\n{\n    int n;\n    cin >> n;\n    for (int i = 1; i <= n; i++)\n        cin >> a[i];\n    for (int i = 1; i <= n; i++) {\n        cin >> b[i];\n        p[b[i]] = i;\n    }\n    build(1, n, 1, n, 1);\n    for (int i = 1; i <= n; i++) {\n        for (auto x : level[i]) {\n            cout << x << " ";\n        }\n    }\n}\nint main()\n{\n    \/\/ IOS;\n    int t = 1;\n    \/\/ cin >> t;\n    while (t--) {\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n
DFS\u7248\u672c<\/h3>\n
#include<map>\n#include<set>\n#include<stack>\n#include<queue>\n#include<cmath>\n#include<vector>\n#include<bitset>\n#include<cstdio>\n#include<cstring>\n#include<fstream>\n#include<cstdlib>\n#include<iostream>\n#include<algorithm>\n#include<unordered_map>\n\nusing namespace std;\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\ntypedef long long ll;\ntypedef pair<int,int> PII;\ntypedef unsigned long long ull;\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2e5 + 10;\n\nint n, a[N], b[N], p[N], l[N], r[N];\nvector<int> level[N];\n\nint build(int al, int ar, int bl, int br, int d){\n    if(al > ar) return 0;\n    int root = a[ar];\n    int k = p[root];\n    \/\/ level[d].push_back(root);\n    l[root] = build(al, al + k - bl - 1, bl, k - 1, d + 1);\n    r[root] = build(al + k - bl, ar - 1, k + 1, br, d + 1);\n    return root;\n}\n\nvoid bfs(){\n    queue<int> q;\n    q.push(a[n]);\n    while(q.size()){\n        auto t = q.front();\n        q.pop();\n        cout << t << " ";\n        if(l[t]) q.push(l[t]);\n        if(r[t]) q.push(r[t]);\n    }\n}\n\nvoid solve(){\n    cin >> n;\n    for (int i = 1; i <= n; i++) cin >> a[i];\n    for (int i = 1; i <= n; i++) {\n        cin >> b[i];\n        p[b[i]] = i;\n    }\n    build(1, n, 1, n, 1);\n    bfs();\n}\nint main(){\n    \/\/ IOS;\n    int t = 1;\n    \/\/ cin >> t;\n    while(t--){\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u94fe\u63a5 \u9898\u76ee\u94fe\u63a5 solution \u7531\u4e8e\u7ed9\u51fa\u7684\u662f\u540e\u5e8f\u904d\u5386\u4e0e\u4e2d\u5e8f\u904d\u5386\uff0c\u540e\u7eed\u904d\u5386\u7684\u904d\u5386\u987a\u5e8f\u662f\u5de6\u53f3\u6839\uff0c\u4e2d\u5e8f\u904d\u5386\u7684\u987a\u5e8f\u662f\u6839\u5de6\u53f3\uff0c\u6240\u4ee5\u6211\u4eec\u5148\u7528\u540e\u5e8f\u904d\u5386\u786e\u5b9a\u6839\u8282\u70b9\uff0c\u7136\u540e\u518d\u5728\u4e2d\u5e8f\u904d\u5386\u91cc\u9762\u627e\u5230\u8be5\u8282\u70b9\uff0c\u7136\u540e\u8be5\u8282\u70b9\u5de6\u8fb9\u5c31\u662f\u5de6\u5b50\u6811\uff0c\u53f3\u8fb9\u5c31\u662f\u53f3\u5b50\u6811\uff0c\u5de6\u5b50\u6811\u7684\u6570\u91cf\u5c31\u662fk - bl + 1,\u90a3\u4e48\u5bf9\u5e94\u5230\u540e\u5e8f\u904d\u5386\u91cc\u9762\u5c31\u662fal - (k - bl + 1) == al - k + bl - 1,\u7136\u540e\u518d\u5904\u7406\u53f3\u5b50\u6811\uff0c\u5c31\u662f\u540e\u5e8fal - k + bl\u5230ar - 1\uff0c\u4e2d\u5e8fk + 1\u5230br\uff0c\u4e0d\u65addfs\u5373\u53ef \u4e0d\u7528DFS\u7248\u672c #include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[72,3],"tags":[25,24,34,35],"class_list":["post-78","post","type-post","status-publish","format-standard","hentry","category-acm","category-solution","tag-bfs","tag-dfs","tag-34","tag-35"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/78","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=78"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/78\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=78"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=78"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=78"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}