{"id":21,"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-09-08-%e4%ba%8c%e5%88%86%e6%9c%80%e5%b0%8f%e7%94%9f%e6%88%90%e6%a0%91\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-08-%e4%ba%8c%e5%88%86%e6%9c%80%e5%b0%8f%e7%94%9f%e6%88%90%e6%a0%91","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-08-%e4%ba%8c%e5%88%86%e6%9c%80%e5%b0%8f%e7%94%9f%e6%88%90%e6%a0%91\/","title":{"rendered":"2020-09-08 \u4e8c\u5206+\u6700\u5c0f\u751f\u6210\u6811"},"content":{"rendered":"

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

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

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

Coco is a beautiful ACMer girl living in a very beautiful mountain. There are many trees and flowers on the mountain, and there are many animals and birds also. Coco like the mountain so much that she now name some letter sequences as Mountain Subsequences.<\/p>\n

A Mountain Subsequence is defined as following:<\/p>\n

    \n
  1. \n

    If the length of the subsequence is n, there should be a max value letter, and the subsequence should like this, a1 < \u2026< ai < ai+1 < Amax > aj > aj+1 > \u2026 > an<\/p>\n<\/li>\n

  2. \n

    It should have at least 3 elements, and in the left of the max value letter there should have at least one element, the same as in the right.<\/p>\n<\/li>\n

  3. \n

    The value of the letter is the ASCII value.<\/p>\n<\/li>\n<\/ol>\n

    Given a letter sequence, Coco wants to know how many Mountain Subsequences exist.<\/p>\n

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

    Input contains multiple test cases.<\/p>\n

    For each case there is a number n (1<= n <= 100000) which means the length of the letter sequence in the first line, and the next line contains the letter sequence.<\/p>\n

    Please note that the letter sequence only contain lowercase letters.<\/p>\n

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

    For each case please output the number of the mountain subsequences module 2012.<\/p>\n

    <\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
    4\nabca\n<\/code><\/pre>\n
    <\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
    4\n<\/code><\/pre>\n
    <\/a>\u63d0\u793a<\/h5>\n
    The 4 mountain subsequences are:<\/p>\n
    aba, aca, bca, abca<\/p>\n
    \u7528\u6807\u8bb0\u6570\u7ec4\u7684\u65b9\u6cd5\u6765\u964d\u4f4e\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n
    AC\u4ee3\u7801<\/p>\n
    #include<\/span> <\/span><\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\ntypedef<\/span> unsigned<\/span> long<\/span> long<\/span> ull;<\/span>\nchar<\/span> a[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\null dp2[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\null dp1[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nll w[<\/span>200<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    ll n;<\/span>\n    while<\/span>(<\/span>scanf<\/span>(<\/span>\"%lld%s\"<\/span>,<\/span>&<\/span>n,<\/span>a+<\/span>1<\/span>)<\/span>!=<\/span>EOF<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>30<\/span>;<\/span>i++<\/span>)<\/span>\n            w[<\/span>i]<\/span>=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>register<\/span> ll i=<\/span>n;<\/span> i>=<\/span>1<\/span>;<\/span> i--<\/span>)<\/span>\n        {<\/span>\n            dp2[<\/span>i]<\/span>=<\/span>0<\/span>;<\/span>\n            for<\/span>(<\/span>char<\/span> j=<\/span>'a'<\/span>;<\/span> j<<\/span>a[<\/span>i]<\/span>;<\/span> j++<\/span>)<\/span>\n            {<\/span>\n                dp2[<\/span>i]<\/span>+<\/span>=<\/span>w[<\/span>j-<\/span>'a'<\/span>]<\/span>;<\/span>\n                dp2[<\/span>i]<\/span>%<\/span>=<\/span>2012<\/span>;<\/span>\n            }<\/span>\n            w[<\/span>a[<\/span>i]<\/span>-<\/span>'a'<\/span>]<\/span>+<\/span>=<\/span>dp2[<\/span>i]<\/span>+<\/span>1<\/span>;<\/span>\n            w[<\/span>a[<\/span>i]<\/span>-<\/span>'a'<\/span>]<\/span>%<\/span>=<\/span>2012<\/span>;<\/span>\n        }<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>30<\/span>;<\/span>i++<\/span>)<\/span>\n            w[<\/span>i]<\/span>=<\/span>0<\/span>;<\/span>\n        register<\/span> long<\/span> long<\/span> ans=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>register<\/span> ll i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            dp1[<\/span>i]<\/span>=<\/span>0<\/span>;<\/span>\n            for<\/span>(<\/span>ll j=<\/span>'a'<\/span>;<\/span> j<<\/span>a[<\/span>i]<\/span>;<\/span> j++<\/span>)<\/span>\n            {<\/span>\n                dp1[<\/span>i]<\/span>+<\/span>=<\/span>w[<\/span>j-<\/span>'a'<\/span>]<\/span>;<\/span>\n                dp1[<\/span>i]<\/span>%<\/span>=<\/span>2012<\/span>;<\/span>\n            }<\/span>\n            w[<\/span>a[<\/span>i]<\/span>-<\/span>'a'<\/span>]<\/span>+<\/span>=<\/span>dp1[<\/span>i]<\/span>+<\/span>1<\/span>;<\/span>\n            w[<\/span>a[<\/span>i]<\/span>-<\/span>'a'<\/span>]<\/span>%<\/span>=<\/span>2012<\/span>;<\/span>\n        }<\/span>\n        for<\/span>(<\/span>register<\/span> ll i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n            ans+<\/span>=<\/span>(<\/span>dp1[<\/span>i]<\/span>*<\/span>dp2[<\/span>i]<\/span>)<\/span>%<\/span>2012<\/span>,<\/span>ans%<\/span>=<\/span>2012<\/span>;<\/span>\n        printf<\/span>(<\/span>\"%lldn\"<\/span>,<\/span>ans)<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
    \u65f6\u95f4\u8d85\u9650<\/p>\n
    #pragma<\/span> GCC optimize(2)<\/span>\n#include<\/span> <\/span><\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\ntypedef<\/span> unsigned<\/span> long<\/span> long<\/span> ull;<\/span>\nchar<\/span> a[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\null dp1[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\null dp2[<\/span>100500<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    ll n;<\/span>\n    while<\/span>(<\/span>scanf<\/span>(<\/span>\"%lld%s\"<\/span>,<\/span>&<\/span>n,<\/span>a+<\/span>1<\/span>)<\/span>!=<\/span>EOF<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<=<\/span>n+<\/span>50<\/span>;<\/span>i++<\/span>)<\/span>\n            dp1[<\/span>i]<\/span>=<\/span>dp2[<\/span>i]<\/span>=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            for<\/span>(<\/span>ll j=<\/span>1<\/span>;<\/span> j<<\/span>i;<\/span> j++<\/span>)<\/span>\n                if<\/span>(<\/span>a[<\/span>j]<\/span><<\/span>a[<\/span>i]<\/span>)<\/span>\n                    dp1[<\/span>i]<\/span>=<\/span>dp1[<\/span>i]<\/span>+<\/span>dp1[<\/span>j]<\/span>+<\/span>1<\/span>;<\/span>\n        }<\/span>\n        for<\/span>(<\/span>ll i=<\/span>n;<\/span> i>=<\/span>1<\/span>;<\/span> i--<\/span>)<\/span>\n        {<\/span>\n            for<\/span>(<\/span>ll j=<\/span>n;<\/span> j><\/span>i;<\/span> j--<\/span>)<\/span>\n                if<\/span>(<\/span>a[<\/span>i]<\/span>><\/span>a[<\/span>j]<\/span>)<\/span>\n                    dp2[<\/span>i]<\/span>=<\/span>dp2[<\/span>i]<\/span>+<\/span>dp2[<\/span>j]<\/span>+<\/span>1<\/span>;<\/span>\n        }<\/span>\n        long<\/span> long<\/span> ans=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n        {<\/span>\n            if<\/span>(<\/span>dp1[<\/span>i]<\/span>>=<\/span>1<\/span>&&<\/span>dp2[<\/span>i]<\/span>>=<\/span>1<\/span>)<\/span>\n                ans+<\/span>=<\/span>dp1[<\/span>i]<\/span>%<\/span>2012<\/span>*<\/span>dp2[<\/span>i]<\/span>%<\/span>2012<\/span>;<\/span>\n            ans%<\/span>=<\/span>2012<\/span>;<\/span>\n        }<\/span>\n        cout<<<\/span>ans<<<\/span>endl;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
    <\/a>\u9898\u76ee\u63cf\u8ff0<\/h6>\n
    In China, there are two companies offering the Internet service for the people from all cities: China Telecom and China Unicom. They both are planning to build cables between cities. Obviously, the government wants to connect all the cities in minimum costs. So the minister of finance Mr. B wants to choose some of the cable plans from the two companies and calculate the minimum cost needed to connect all the cities. Mr. B knows that N-1 cables should be built in order to connect all N cities of China. For some honorable reason, Mr. B should choose K cables from the China Telecom and the rest N-1-K cables from the China Unicom. Your job is to help Mr. B determine which cables should be built and the minimum cost to build them. You may assume that the solution always exists.<\/p>\n
    <\/a>\u8f93\u5165<\/h6>\n
    Each test case starts with a line containing the number of cities N (1 <= N <= 50,000), number of cable plans M (N-1 <= M <= 100,000) and the number of required cables from China Telecom K (0 <= K <= N-1). This is followed by M lines, each containing four integers a, b, c, x (0 <= a, b <= N-1, a != b, 1 <= c <= 100, x in {0,1} indicating the pair of cities this cable will connect, the cost to build this cable and the company this cable plan belongs to. x=0 denotes that the cable plan belongs to China Telecom and x=1 denotes that the cable plan is from China Unicom.<\/p>\n
    <\/a>\u8f93\u51fa<\/h6>\n
    For each test case, display the case number and the minimum cost of the cable building.<\/p>\n
    <\/a>\u6837\u4f8b\u8f93\u5165<\/h6>\n
    2 2 1\n0 1 1 1\n0 1 2 0\n2 2 0\n0 1 1 1\n0 1 2 0\n<\/code><\/pre>\n
    <\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n
    Case 1: 2\nCase 2: 1\n<\/code><\/pre>\n
    <\/a>\u63d0\u793a<\/h6>\n
    In the first case, there are two cable plans between the only two cities, one from China Telecom and one from China Unicom. Mr. B needs to choose the one from China Telecom to satisfy the problem requirement even the cost is higher.
     In the second case, Mr. B must choose the cable from China Unicom, which leads the answer to 1.
     \u4e8c\u5206+\u6700\u5c0f\u751f\u6210\u6811<\/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>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\nint<\/span> n,<\/span>m,<\/span>k,<\/span>sum1;<\/span>\nint<\/span> fa[<\/span>500500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> x,<\/span>y,<\/span>z,<\/span>t;<\/span>\n}<\/span>;<\/span>\nnode a[<\/span>500500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nbool<\/span> cmp<\/span>(<\/span>node a,<\/span>node b)<\/span>\n{<\/span>\n    if<\/span>(<\/span>a.<\/span>z!=<\/span>b.<\/span>z)<\/span>\n        return<\/span> a.<\/span>z<<\/span>b.<\/span>z;<\/span>\n    else<\/span>\n        return<\/span> a.<\/span>t<<\/span>b.<\/span>t;<\/span>\n}<\/span>\nint<\/span> findfa<\/span>(<\/span>int<\/span> x)<\/span>\n{<\/span>\n    if<\/span>(<\/span>x==<\/span>fa[<\/span>x]<\/span>)<\/span>\n        return<\/span> x;<\/span>\n    else<\/span>\n        return<\/span> fa[<\/span>x]<\/span>=<\/span>findfa<\/span>(<\/span>fa[<\/span>x]<\/span>)<\/span>;<\/span>\n}<\/span>\nint<\/span> add<\/span>(<\/span>int<\/span> x,<\/span>int<\/span> y)<\/span>\n{<\/span>\n    int<\/span> fx=<\/span>findfa<\/span>(<\/span>x)<\/span>;<\/span>\n    int<\/span> fy=<\/span>findfa<\/span>(<\/span>y)<\/span>;<\/span>\n    if<\/span>(<\/span>fx!=<\/span>fy)<\/span>\n    {<\/span>\n        fa[<\/span>fx]<\/span>=<\/span>fy;<\/span>\n        return<\/span> 1<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\nint<\/span> pd<\/span>(<\/span>int<\/span> x)<\/span>\n{<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>.<\/span>t==<\/span>0<\/span>)<\/span>\n            a[<\/span>i]<\/span>.<\/span>z=<\/span>a[<\/span>i]<\/span>.<\/span>z+<\/span>x;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        fa[<\/span>i]<\/span>=<\/span>i;<\/span>\n    sort<\/span>(<\/span>a+<\/span>1<\/span>,<\/span>a+<\/span>m+<\/span>1<\/span>,<\/span>cmp)<\/span>;<\/span>\n    int<\/span> sum=<\/span>0<\/span>,<\/span>cnt=<\/span>n-<\/span>1<\/span>;<\/span>\n    sum1=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>add<\/span>(<\/span>a[<\/span>i]<\/span>.<\/span>x,<\/span>a[<\/span>i]<\/span>.<\/span>y)<\/span>)<\/span>\n        {<\/span>\n            sum++<\/span>;<\/span>\n            cnt-<\/span>=<\/span>a[<\/span>i]<\/span>.<\/span>t;<\/span>\n            sum1+<\/span>=<\/span>a[<\/span>i]<\/span>.<\/span>z;<\/span>\n        }<\/span>\n        if<\/span>(<\/span>sum==<\/span>n-<\/span>1<\/span>)<\/span>\n            break<\/span>;<\/span>\n    }<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>.<\/span>t==<\/span>0<\/span>)<\/span>\n        {<\/span>\n            a[<\/span>i]<\/span>.<\/span>z=<\/span>a[<\/span>i]<\/span>.<\/span>z-<\/span>x;<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> cnt>=<\/span>k;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> summ=<\/span>0<\/span>;<\/span>\n    while<\/span>(<\/span>scanf<\/span>(<\/span>\"%d%d%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m,<\/span>&<\/span>k)<\/span>!=<\/span>EOF<\/span>)<\/span>\n    {<\/span>\n        int<\/span> ans=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            scanf<\/span>(<\/span>\"%d%d%d%d\"<\/span>,<\/span>&<\/span>a[<\/span>i]<\/span>.<\/span>x,<\/span>&<\/span>a[<\/span>i]<\/span>.<\/span>y,<\/span>&<\/span>a[<\/span>i]<\/span>.<\/span>z,<\/span>&<\/span>a[<\/span>i]<\/span>.<\/span>t)<\/span>;<\/span>\n        }<\/span>\n        int<\/span> l=<\/span>-<\/span>100<\/span>,<\/span>r=<\/span>100<\/span>;<\/span>\n        while<\/span>(<\/span>l<<\/span>r)<\/span>\n        {<\/span>\n            int<\/span> mid=<\/span>(<\/span>l+<\/span>r-<\/span>1<\/span>)<\/span>\/<\/span>2<\/span>;<\/span>\n            if<\/span>(<\/span>pd<\/span>(<\/span>mid)<\/span>)<\/span>\n            {<\/span>\n                l=<\/span>mid+<\/span>1<\/span>;<\/span>\n                ans=<\/span>sum1-<\/span>k*<\/span>mid;<\/span>\n            }<\/span>\n            else<\/span>\n            {<\/span>\n                r=<\/span>mid;<\/span>\n            }<\/span>\n        }<\/span>\n        printf<\/span>(<\/span>\"Case %d: %dn\"<\/span>,<\/span>++<\/span>summ,<\/span>ans)<\/span>;<\/span>\n    }<\/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-21","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\/21","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=21"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/21\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=21"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=21"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=21"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
    http:\/\/icpc.upc.edu.cn\/problem.php?cid=2570&pid=8<\/a><\/p>\n