{"id":24,"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-21\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-21","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-21\/","title":{"rendered":"2020-08-21"},"content":{"rendered":"

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

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

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

\u7ecf\u8fc7\u6570\u5929\u7684\u8270\u82e6\u8dcb\u6d89\uff0cRainy7 \u7ec8\u4e8e\u8fdb\u5165\u4e86\u9b54\u6cd5\u738b\u56fd\u3002\u7531\u4e8e Rainy7 \u662f\u5927\u9b54\u6cd5\u5e08\uff0c\u6240\u4ee5\u5979\u53d7\u5230\u4e86\u56fd\u738b 3edc2wsx1qaz \u7684\u70ed\u60c5\u6b3e\u5f85\u3002<\/p>\n

Rainy7 \u4eab\u7528\u5b8c\u56fd\u5bb4\u540e\uff0c\u56fd\u738b\u5411\u5979\u9053\u51fa\u4e86\u9b54\u6cd5\u738b\u56fd\u7684\u56f0\u96be\uff1a\u738b\u56fd\u6b63\u906d\u53d7\u7740\u9b54\u517d\u7684\u88ad\u51fb\u3002\u738b\u56fd\u4e2d\u7684\u6240\u6709\u4eba\u90fd\u65e0\u6cd5\u51fb\u8d25\u9b54\u517d\uff0c\u6240\u4ee5\u56fd\u738b\u6073\u8bf7\u5927\u9b54\u6cd5\u5e08 Rainy7 \u5e2e\u52a9\u738b\u56fd\u4e0e\u9b54\u517d\u6218\u6597\u3002<\/p>\n

Rainy7 \u723d\u5feb\u5730\u7b54\u5e94\u4e86\u3002\u56fd\u738b\u6b23\u559c\u82e5\u72c2\uff0c\u5e76\u7acb\u5373\u9080\u8bf7 Rainy7 \u5230\u9b54\u6cd5\u4e16\u754c\u6700\u5927\u7684\u9b54\u6cd5\u9635\u4e2d\u6c72\u53d6\u9b54\u6cd5\uff0c\u4ee5\u505a\u597d\u6218\u6597\u51c6\u5907\u3002<\/p>\n

\u8fd9\u4e2a\u9b54\u6cd5\u9635\u662f\u4e00\u4e2an\u884cm\u5217\u7684\u77e9\u9635\uff0c\u77e9\u9635\u4e2d\u6bcf\u4e2a\u683c\u5b50\u90fd\u6709\u4e00\u4e2a\u975e\u8d1f\u6574\u6570\u7684\u9b54\u6cd5\u503c\uff0c\u7b2ci\u884c\u7b2cj\u5217\u7684\u683c\u5b50\u7684\u9b54\u6cd5\u503c\u4e3aaij\u3002<\/p>\n

Rainy7 \u8981\u4ece\u7b2c1\u884c\u7b2c1\u5217\u7684\u683c\u5b50\u8d70\u5230\u7b2cn\u884c\u7b2cm\u5217\u7684\u683c\u5b50\u3002\u5982\u679c Rainy7 \u5f53\u524d\u5728\u7b2ci\u884c\u7b2cj\u5217\u7684\u683c\u5b50\u4e0a\uff0c\u5219\u5979\u4e0b\u4e00\u6b65\u53ef\u4ee5\u8d70\u5230\u7b2ci+1\u884c\u7b2cj\u5217\u7684\u683c\u5b50\u6216\u7b2c i\u884c\u7b2cj+1\u5217\u7684\u683c\u5b50\u4e0a\uff08\u5982\u679c\u90a3\u4e2a\u683c\u5b50\u5b58\u5728\u7684\u8bdd\uff09\uff0c\u76f4\u5230\u5979\u8d70\u5230\u7b2cn\u884c\u7b2cm\u5217\u7684\u683c\u5b50\u4e3a\u6b62\u3002<\/p>\n

Rainy7 \u53ea\u80fd\u6309\u8fd9\u6837\u7684\u65b9\u5f0f\u8d70\u4e00\u6b21\u3002\u8d70\u5b8c\u540e\uff0cRainy7 \u6c72\u53d6\u5230\u7684\u9b54\u6cd5\u503c\u662f\u5979\u8d70\u8fc7\u7684\u6240\u6709\u683c\u5b50\u7684\u9b54\u6cd5\u503c\u7684\u4e0e\u548c\uff0c\u5373\u628a\u5979\u8d70\u8fc7\u7684\u6240\u6709\u683c\u5b50\u7684\u9b54\u6cd5\u503c\u5168\u90e8\u6309\u4f4d\u4e0e\u8d77\u6765\u7684\u7ed3\u679c\u3002<\/p>\n

Rainy7 \u60f3\u77e5\u9053\u5979\u6700\u591a\u80fd\u6c72\u53d6\u5230\u591a\u5c11\u9b54\u6cd5\u503c\u3002Rainy7 \u53ea\u7528\u4e86114514-1919810s\u5c31\u7b97\u51fa\u4e86\u7b54\u6848\uff0c\u5728\u5979\u5f00\u59cb\u6c72\u53d6\u9b54\u6cd5\u4e4b\u524d\uff0c\u5979\u4e5f\u60f3\u8ba9\u4f60\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u3002<\/p>\n

\u9877\u523b\u95f4\uff0c\u9b54\u6cd5\u6c72\u53d6\u5b8c\u6bd5\u4e86\uff0cRainy7 \u4fbf\u575a\u5b9a\u5730\u5411\u6218\u573a\u8d70\u53bb\u2026\u2026<\/p>\n

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

\u7b2c\u4e00\u884c\u4e24\u4e2a\u6574\u6570n,m\uff0c\u5206\u522b\u8868\u793a\u9b54\u6cd5\u9635\u7684\u884c\u6570\u548c\u5217\u6570\u3002
\u63a5\u4e0b\u6765n\u884c\uff0c\u6bcf\u884c\u5305\u542bm\u4e2a\u6574\u6570\uff0c\u5176\u4e2d\u7b2ci\u7684\u7b2cj\u4e2a\u6570\u8868\u793aaij\u3002<\/p>\n

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

\u8f93\u51fa\u4e00\u884c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a Rainy7 \u80fd\u6c72\u53d6\u5230\u7684\u9b54\u6cd5\u503c\u7684\u6700\u5927\u503c\u3002<\/p>\n

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

\u3010\u6837\u4f8b1\u3011
3 4
3 7 7 7
6 3 8 4
1 3 3 7
\u3010\u6837\u4f8b2\u3011
10 10
2047 2047 1535 2043 863 1983 2046 2015 2047 2047
1903 1535 1982 2015 2047 1531 1791 2015 2025 2045
767 927 2023 2039 2015 1918 2042 2039 935 2047
2022 2045 1499 991 2046 2047 2047 959 1023 2047
2038 1999 2046 1919 1519 2015 1007 2047 2047 1023
2047 991 1983 2047 1919 1655 1791 2013 1535 2047
2047 2047 1974 1535 2047 2031 1847 1535 2047 2045
1023 1023 2047 2047 1919 2011 1983 1791 1979 2023
2047 2047 2047 2045 1503 511 1023 2004 2039 2047
895 1525 2031 1911 2039 1967 1852 1023 1983 2047<\/p>\n

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

\u3010\u6837\u4f8b1\u3011
3
\u3010\u6837\u4f8b2\u3011
1284<\/p>\n

<\/a>\u63d0\u793a<\/h5>\n

\u6837\u4f8b1\u89e3\u91ca\uff1a
\u6211\u4eec\u7528(i,j)\u8868\u793a\u9b54\u6cd5\u9635\u7b2ci\u884c\u7b2cj\u5217\u7684\u683c\u5b50\u3002<\/p>\n

Rainy7 \u8d70\u8fc7\u7684\u8def\u5f84\u4e3a\uff1a(1,1)->(1,2)->(2,2)->(3,2)->(3,3)->(3,4)\uff0c\u6c72\u53d6\u5230\u7684\u9b54\u6cd5\u503c\u4e3a 3 and 7 and 3 and 4 and 3 and 7 = 3\u3002<\/p>\n

\u6837\u4f8b2\u89e3\u91ca:
Rainy7 \u8d70\u8fc7\u7684\u4e00\u79cd\u6700\u4f73\u8def\u5f84\u4e3a\uff1a
(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(2.5)->(3,5)->(4,5)->(5,5)->(6,5)->(7,5)->(7,6)->(7,7)->(7,8)->(7,9)->(7,10)->(8,10)->(9,10)->(10.10)\u3002<\/p>\n

\u5bf9\u4e8e\u5168\u90e8\u6570\u636e\uff0c1\u2264n,m\u22642\u00d7103,0\u2264aij\u2264231-1\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> a[<\/span>2500<\/span>]<\/span>[<\/span>2500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> n,<\/span>m;<\/span>\nint<\/span> dp[<\/span>2500<\/span>]<\/span>[<\/span>2500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> max1=<\/span>0<\/span>;<\/span>\nint<\/span> cnt=<\/span>0<\/span>;<\/span>\nint<\/span> p[<\/span>2005<\/span>]<\/span>[<\/span>2005<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> vis[<\/span>2005<\/span>]<\/span>[<\/span>2005<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\ninline<\/span> int<\/span> dfs<\/span>(<\/span>)<\/span>\n{<\/span>\n    if<\/span>(<\/span>vis[<\/span>1<\/span>]<\/span>[<\/span>1<\/span>]<\/span>)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    cnt++<\/span>;<\/span>\n    p[<\/span>1<\/span>]<\/span>[<\/span>1<\/span>]<\/span>=<\/span>cnt;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>m;<\/span>j++<\/span>)<\/span>\n        {<\/span>\n            if<\/span>(<\/span>vis[<\/span>i]<\/span>[<\/span>j]<\/span>)<\/span>\n                continue<\/span>;<\/span>\n            if<\/span>(<\/span>i><\/span>1<\/span>&&<\/span>!<\/span>vis[<\/span>i-<\/span>1<\/span>]<\/span>[<\/span>j]<\/span>&&<\/span>p[<\/span>i-<\/span>1<\/span>]<\/span>[<\/span>j]<\/span>==<\/span>cnt)<\/span>\n                p[<\/span>i]<\/span>[<\/span>j]<\/span>=<\/span>cnt;<\/span>\n            if<\/span>(<\/span>j><\/span>1<\/span>&&<\/span>!<\/span>vis[<\/span>i]<\/span>[<\/span>j-<\/span>1<\/span>]<\/span>&&<\/span>p[<\/span>i]<\/span>[<\/span>j-<\/span>1<\/span>]<\/span>==<\/span>cnt)<\/span>\n                p[<\/span>i]<\/span>[<\/span>j]<\/span>=<\/span>cnt;<\/span>\n        }<\/span>\n    }<\/span>\n    if<\/span>(<\/span>p[<\/span>n]<\/span>[<\/span>m]<\/span>==<\/span>cnt)<\/span>\n        return<\/span> 1<\/span>;<\/span>\n    else<\/span>\n        return<\/span> 0<\/span>;<\/span>\n}<\/span>\nint<\/span> last[<\/span>2005<\/span>]<\/span>[<\/span>2005<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> l[<\/span>100<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m)<\/span>;<\/span>\n    for<\/span>(<\/span>register<\/span> int<\/span> i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>register<\/span> int<\/span> j=<\/span>1<\/span>;<\/span> j<=<\/span>m;<\/span> j++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>a[<\/span>i]<\/span>[<\/span>j]<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    for<\/span>(<\/span>int<\/span> k=<\/span>31<\/span>;<\/span>k>=<\/span>0<\/span>;<\/span>k--<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>!<\/span>(<\/span>(<\/span>a[<\/span>1<\/span>]<\/span>[<\/span>1<\/span>]<\/span>>><\/span>k)<\/span>&<\/span>1<\/span>)<\/span>)<\/span>\n            continue<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>m;<\/span>j++<\/span>)<\/span>\n            {<\/span>\n                vis[<\/span>i]<\/span>[<\/span>j]<\/span>=<\/span>last[<\/span>i]<\/span>[<\/span>j]<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>m;<\/span>j++<\/span>)<\/span>\n            {<\/span>\n                if<\/span>(<\/span>!<\/span>(<\/span>(<\/span>a[<\/span>i]<\/span>[<\/span>j]<\/span>>><\/span>k)<\/span>&<\/span>1<\/span>)<\/span>)<\/span>\n                    vis[<\/span>i]<\/span>[<\/span>j]<\/span>=<\/span>1<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        if<\/span>(<\/span>dfs<\/span>(<\/span>)<\/span>)<\/span>\n        {<\/span>\n            l[<\/span>k]<\/span>=<\/span>1<\/span>;<\/span>\n            for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n            {<\/span>\n                for<\/span>(<\/span>int<\/span> j=<\/span>1<\/span>;<\/span>j<=<\/span>m;<\/span>j++<\/span>)<\/span>\n                {<\/span>\n                    last[<\/span>i]<\/span>[<\/span>j]<\/span>=<\/span>vis[<\/span>i]<\/span>[<\/span>j]<\/span>;<\/span>\n                }<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n    int<\/span> sum=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>30<\/span>;<\/span>i>=<\/span>0<\/span>;<\/span>i--<\/span>)<\/span>\n    {<\/span>\n        sum+<\/span>=<\/span>l[<\/span>i]<\/span>*<\/span>(<\/span>1<\/span><<<\/span>i)<\/span>;<\/span>\n    }<\/span>\n    cout<<<\/span>sum<<<\/span>endl;<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\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-24","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\/24","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=24"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/24\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=24"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=24"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=24"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}