[POI2009]Baj \u6700\u77ed\u56de\u6587\u8def<\/p>\n
Time Limit:10000MS Memory Limit:165536K
Total Submit:10 Accepted:1
Case Time Limit:3000MS<\/p>\n
Description <\/strong><\/p>\n N\u4e2a\u70b9\u7528M\u6761\u6709\u5411\u8fb9\u8fde\u63a5\uff0c\u6bcf\u6761\u8fb9\u6807\u6709\u4e00\u4e2a\u5c0f\u5199\u5b57\u6bcd\u3002 <\/p>\n \u5bf9\u4e8e\u4e00\u4e2a\u957f\u5ea6\u4e3aD\u7684\u9876\u70b9\u5e8f\u5217\uff0c\u56de\u7b54\u6bcf\u5bf9\u76f8\u90bb\u9876\u70b9Si\u5230Si+1\u7684\u6700\u77ed\u56de\u6587\u8def\u5f84\u3002 <\/p>\n \u5982\u679c\u6ca1\u6709\uff0c\u8f93\u51fa-1\u3002 <\/p>\n \u5982\u679c\u6709\uff0c\u8f93\u51fa\u6700\u77ed\u957f\u5ea6\u4ee5\u53ca\u8fd9\u4e2a\u5b57\u7b26\u4e32\u3002 <\/p>\n Input <\/strong><\/p>\n \u7b2c\u4e00\u884c\u6b63\u6574\u6570N\u548cM ( 2 \u2264 N \u2264 400 , 1 \u2264 M \u2264 60,000 ) Output <\/strong><\/p>\n \u5bf9\u4e8eD-1\u5bf9\u76f8\u90bb\u70b9\uff0c\u6309\u8981\u6c42\u8f93\u51fa\u4e00\u884c\u3002 \u5982\u679c\u6709\u5408\u6cd5\uff0c\u8f93\u51fa\u6700\u77ed\u957f\u5ea6\u4ee5\u53ca\u8fd9\u4e2a\u5b57\u7b26\u4e32\u3002\u7a7a\u683c\u9694\u5f00\u3002 <\/p>\n Sample Input <\/strong><\/p>\n 6 7<\/p>\n 1 2 a<\/p>\n 1 3 x<\/p>\n 1 4 b<\/p>\n 2 6 l<\/p>\n 3 5 y<\/p>\n 4 5 z<\/p>\n 6 5 a<\/p>\n 3<\/p>\n 1 5 3<\/p>\n Sample Output <\/strong><\/p>\n 3 ala<\/p>\n -1<\/p>\n Source [POI2009]Baj \u6700\u77ed\u56de\u6587\u8def Time Limit:10000MS Memory Limit:165536KTotal Submit:10 Accepted:1 Case Time Limit:3000MS Description N\u4e2a\u70b9\u7528M\u6761\u6709\u5411\u8fb9\u8fde\u63a5\uff0c\u6bcf\u6761\u8fb9\u6807\u6709\u4e00\u4e2a\u5c0f\u5199\u5b57\u6bcd\u3002 \u5bf9\u4e8e\u4e00\u4e2a\u957f\u5ea6\u4e3aD\u7684\u9876\u70b9\u5e8f\u5217\uff0c\u56de\u7b54\u6bcf\u5bf9\u76f8\u90bb\u9876\u70b9Si\u5230Si+1\u7684\u6700\u77ed\u56de\u6587\u8def\u5f84\u3002 \u5982\u679c\u6ca1\u6709\uff0c\u8f93\u51fa-1\u3002 \u5982\u679c\u6709\uff0c\u8f93\u51fa\u6700\u77ed\u957f\u5ea6\u4ee5\u53ca\u8fd9\u4e2a\u5b57\u7b26\u4e32\u3002 Input \u7b2c\u4e00\u884c\u6b63\u6574\u6570N\u548cM ( 2 \u2264 N \u2264 400 , 1 \u2264 M \u2264 60,000 ) \u63a5\u4e0b\u6765M\u884c\u63cf\u8ff0\u8fb9\u7684\u8d77\u70b9\uff0c\u7ec8\u70b9\uff0c\u5b57\u6bcd\u3002 \u63a5\u4e0b\u6765D\u8868\u793a\u8be2\u95ee\u5e8f\u5217\u957f\u5ea6 ( 2 \u2264 D \u2264 100 ) \u518d\u63a5\u4e0b\u6765D\u4e2a1\u5230N\u7684\u6574\u6570 Output \u5bf9\u4e8eD-1\u5bf9\u76f8\u90bb\u70b9\uff0c\u6309\u8981\u6c42\u8f93\u51fa\u4e00\u884c\u3002 \u5982\u679c\u6ca1\u5408\u6cd5\u65b9\u6848\uff0c\u8f93\u51fa-1\u3002 \u5982\u679c\u6709\u5408\u6cd5\uff0c\u8f93\u51fa\u6700\u77ed\u957f\u5ea6\u4ee5\u53ca\u8fd9\u4e2a\u5b57\u7b26\u4e32\u3002\u7a7a\u683c\u9694\u5f00\u3002 Sample Input 6 7 1 2 a 1 3 x […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/348"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=348"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/348\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=348"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u63a5\u4e0b\u6765M\u884c\u63cf\u8ff0\u8fb9\u7684\u8d77\u70b9\uff0c\u7ec8\u70b9\uff0c\u5b57\u6bcd\u3002
\u63a5\u4e0b\u6765D\u8868\u793a\u8be2\u95ee\u5e8f\u5217\u957f\u5ea6 ( 2 \u2264 D \u2264 100 )
\u518d\u63a5\u4e0b\u6765D\u4e2a1\u5230N\u7684\u6574\u6570 <\/p>\n
\u5982\u679c\u6ca1\u5408\u6cd5\u65b9\u6848\uff0c\u8f93\u51fa-1\u3002 <\/p>\n
\u9996\u5148\u4e00\u5f00\u59cb\u6211\u7684\u60f3\u6cd5\u662f\u5bf9\u4e8e
(a,b)\u5982\u679ca->c\u7684\u8fb9\u548cb->c\u4e0a\u7684\u8fb9\u7684\u5b57\u6bcd\u4e00\u6837\u7684\u8bdd\u5c31\u53ef\u4ee5\u8f6c\u79fb\u3002\u3002\u7136\u540e\u72b6\u6001\u5c31\u662f(a,b)\u3002\u3002
\u8fd9\u6837\u72b6\u6001\u6570\u6709N^2\u3002\u3002\u6bcf\u6b21\u8f6c\u79fb\u662f\u5ea6\u6570\u7684\u5e73\u65b9\u7ea7\u522b\u7684\u3002\u3002\u663e\u7136\u4f1aTLE\u56e7\u3002\u3002\u3002
\u7136\u540e\u6362\u79cd\u601d\u8def\uff1a
\u8fd9\u4e2a\u66f4\u65b0\u8bf4\u767d\u4e86\u5c31\u662fa\u8d70\u4e00\u6b65\uff0cb\u987a\u7740\u540c\u6837\u7684\u8fb9\u8d70\u4e00\u6b65\u3002
\u90a3\u4e48\u6709\u4e24\u79cd\u53ef\u80fd\u7684\u60c5\u51b5\u8f6e\u5230a\u8d70\uff0c\u8f6e\u5230b\u8d70\u3002\u3002
\u5982\u679c\u662fa\u8d70\uff0c\u90a3\u4e48a\u968f\u4fbf\u8d70\u4e00\u6b65\u5c31\u884c\u4e86\u3002\u3002
\u5982\u679c\u662fb\u8d70\uff0cb\u8981\u8ddfa\u8d70\u5230\u90a3\u4e2a\u4e00\u6837\u3002\u3002
\u6362\u8a00\u4e4b\u72b6\u6001\u5c31\u662f (a,b,now,pre)a\u548cb\u610f\u4e49\u5982\u4e0a\uff0cnow\u8868\u793a\u662fa\u8d70\u8fd8\u662fb\u8d70\uff0cpre\u8868\u793a\u4e0a\u4e00\u4e2a\u662f\u54ea\u4e2a\uff08a\u8d70\u5230\u8bdd\u5c31\u5ffd\u7565\uff09\u3002\u3002
\u90a3\u4e48\u5b9e\u9645\u4e0a\u5c31\u4e00\u5171\u6709N*N*\uff0826+1\uff09\u79cd\u72b6\u6001\u3002\u3002\u540c\u65f6\u66f4\u65b0\u4e5f\u53d8\u6210O\uff08M\uff09\u7ea7\u522b\u4e86\u3002\u3002
A\u4e86\u3002\u3002\u4ee3\u7801\u5982\u4e0b\u3002\u3002\u3002
http:\/\/www.ideone.com\/EpXy9
<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"