{"id":41,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-08-04\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-04","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-04\/","title":{"rendered":"2020-08-04"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=1404&pid=5<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

\u8bbeX\u662f\u6709N\u4e2a\u4e0d\u76f8\u540c\u6574\u6570\u7684\u96c6\u5408\u3002\u628aX\u4e2d\u6bcf\u4e2a\u6570\u7528\u4e24\u6b21\uff0c\u6392\u6210\u4e00\u4e2a\u957f\u5ea6\u4e3a2N\u7684\u6570\u5217S\uff0c\u8981\u6c42S\u4e2d\u4efb\u610f\u4e00\u4e2a\u6570i\u4e0e\u53e6\u4e00\u4e2a\u4e0e\u5b83\u76f8\u540c\u7684i\u4e4b\u95f4\u6b63\u597d\u95f4\u9694i\u4e2a\u6570\u5b57\u3002<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

\u7b2c1\u884c\u4e00\u4e2a\u6574\u6570N(I\u2264N\u22648)\uff1b
\u7b2c2\u884c\u6709N\u4e2a\u6574\u6570\uff08\u6bcf\u4e2a\u6570\u4e0d\u76f8\u540c\uff0c\u5e76\u4e14\u57280\u523016\u4e4b\u95f4\uff09\uff0c\u8868\u793a\u96c6\u5408\u4e2d\u7684\u6570\u3002<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

\u8f93\u51fa\u4e00\u4e2a\u6ee1\u8db3\u4e0a\u9762\u8981\u6c42\u7684\u957f\u5ea6\u4e3a2N\u7684\u6570\u5217\uff1b\u82e5\u6709\u591a\u4e2a\u89e3\uff0c\u8f93\u51fa\u5b57\u5178\u5e8f\u6700\u5c0f\u7684\uff1b\u82e5\u6ca1\u6709\u89e3\uff0c\u8f93\u51fa-1\u3002<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
5\n0 1 2 3 4 \n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
0 0 2 3 4 2 1 3 1 4 \n<\/code><\/pre>\n
DFS\u641c\u7d22\u6bcf\u4e00\u79cd\u60c5\u51b5\u5373\u53ef\u3002<\/p>\n
#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nint<\/span> vis[<\/span>100<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> data[<\/span>100<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> n;<\/span>\nint<\/span> a[<\/span>100<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> dfs<\/span>(<\/span>int<\/span> k)<\/span>\n{<\/span>\n    if<\/span>(<\/span>k==<\/span>2<\/span>*<\/span>n+<\/span>1<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>2<\/span>*<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            cout<<<\/span>data[<\/span>i]<\/span><<<\/span>' '<\/span>;<\/span>\n        }<\/span>\n        cout<<<\/span>endl;<\/span>\n        exit<\/span>(<\/span>0<\/span>)<\/span>;<\/span>\n    }<\/span>\n    if<\/span>(<\/span>data[<\/span>k]<\/span>==<\/span>-<\/span>1<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> l=<\/span>0<\/span>;<\/span>l<<\/span>n;<\/span>l++<\/span>)<\/span>\n        {<\/span>\n            int<\/span> i=<\/span>a[<\/span>l]<\/span>;<\/span>\n            if<\/span>(<\/span>k+<\/span>i+<\/span>1<\/span><=<\/span>2<\/span>*<\/span>n&&<\/span>!<\/span>vis[<\/span>i]<\/span>&&<\/span>data[<\/span>k]<\/span>==<\/span>-<\/span>1<\/span>&&<\/span>data[<\/span>k+<\/span>i+<\/span>1<\/span>]<\/span>==<\/span>-<\/span>1<\/span>)<\/span>\n            {<\/span>\n                data[<\/span>k]<\/span>=<\/span>data[<\/span>k+<\/span>i+<\/span>1<\/span>]<\/span>=<\/span>i;<\/span>\n                vis[<\/span>i]<\/span>=<\/span>1<\/span>;<\/span>\n                dfs<\/span>(<\/span>k+<\/span>1<\/span>)<\/span>;<\/span>\n                vis[<\/span>i]<\/span>=<\/span>0<\/span>;<\/span>\n                data[<\/span>k]<\/span>=<\/span>data[<\/span>k+<\/span>i+<\/span>1<\/span>]<\/span>=<\/span>-<\/span>1<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n    else<\/span>\n        dfs<\/span>(<\/span>k+<\/span>1<\/span>)<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    std::<\/span>ios::<\/span>sync_with_stdio<\/span>(<\/span>false<\/span>)<\/span>;<\/span>\n    std::<\/span>cin.<\/span>tie<\/span>(<\/span>0<\/span>)<\/span>;<\/span>\n    memset<\/span>(<\/span>data,<\/span>-<\/span>1<\/span>,<\/span>sizeof<\/span>(<\/span>data)<\/span>)<\/span>;<\/span>\n    cin>><\/span>n;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>n;<\/span>i++<\/span>)<\/span>\n        cin>><\/span>a[<\/span>i]<\/span>;<\/span>\n    sort<\/span>(<\/span>a,<\/span>a+<\/span>n)<\/span>;<\/span>\n    dfs<\/span>(<\/span>1<\/span>)<\/span>;<\/span>\n    cout<<<\/span>-<\/span>1<\/span><<<\/span>endl;<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-41","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/41","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=41"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/41\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=41"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=41"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=41"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}