亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

A Great Alchemist

系統 1801 0

Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Problem
Carol is a great alchemist.

In her world, each metal has a name of 2N (N is an integer) letters long, which consists of uppercase alphabets.

Carol can create metal S3 from S1 and S2 alchemical when she can make the name of S3 by taking N letters each from S1 and S2 then rearranging them properly.

You are given 3 names of the metal S1, S2, S3. Determine wether Carol can create S3 from S1 and S2 or not.

Input
The input will be given in the following format from the Standard Input.

S1
S2
S3
On the first line, you will be given the name of the first metal material S1.
On the second line, you will be given the name of the second metal material S2.
On the third line, you will be given the name of the metal S3, which Carol wants to create.
Each character in the S1, S2, and S3 will be an uppercase English alphabet letter.
Each string S1, S2 and S3 has same number of letters and the number is always even.
It is guaranteed that 2≦|S1|≦100000
Output
If Carol can create S3 from S1 and S2, output YES, if not, output NO in one line. Make sure to insert a line break at the end of the output.

Input Example 1
AABCCD
ABEDDA
EDDAAA
Output Example 1
YES
You can make EDDAAA by picking AAD from the first metal, and AED from the second metal.

Input Example 2
AAAAAB
CCCCCB
AAABCB
Output Example 2
NO
To make AAABCB, you have to take at least four letters from the first material. So this can't be created alchemical.

用回溯法TLE。看了同學的代碼,在執行回溯前執行一些檢查就能過了。哎。

      
         1
      
       #include <iostream>


      
         2
      
       #include <
      
        string
      
      >


      
         3
      
       #include <vector>


      
         4
      
      
        using
      
      
        namespace
      
      
         std;


      
      
         5
      
      
         6
      
      
        bool
      
       backtrack(
      
        string
      
       &S3, 
      
        int
      
       charsFromS1, 
      
        int
      
       charsFromS2, 
      
        int
      
      
         current, 


      
      
         7
      
               vector<
      
        int
      
      > &charsInS1, vector<
      
        int
      
      > &
      
        charsInS2) {


      
      
         8
      
      
        if
      
       (current >= S3.length()) 
      
        return
      
      
        true
      
      
        ;


      
      
         9
      
      
        char
      
       index = S3[current] - 
      
        '
      
      
        A
      
      
        '
      
      
        ;


      
      
        10
      
      
        if
      
       (charsInS1[index] > 
      
        0
      
       && charsFromS1 < S3.length() / 
      
        2
      
      
        ) {


      
      
        11
      
               charsInS1[index]--
      
        ;


      
      
        12
      
      
        if
      
       (backtrack(S3, charsFromS1 + 
      
        1
      
      , charsFromS2, current + 
      
        1
      
      , charsInS1, charsInS2)) 
      
        return
      
      
        true
      
      
        ;


      
      
        13
      
               charsInS1[index]++
      
        ;


      
      
        14
      
      
            }


      
      
        15
      
      
        if
      
       (charsInS2[index] > 
      
        0
      
       && charsFromS2 < S3.length() / 
      
        2
      
      
        ) {


      
      
        16
      
               charsInS2[index]--
      
        ;


      
      
        17
      
      
        if
      
       (backtrack(S3, charsFromS1, charsFromS2 + 
      
        1
      
      , current + 
      
        1
      
      , charsInS1, charsInS2)) 
      
        return
      
      
        true
      
      
        ;


      
      
        18
      
               charsInS2[index]++
      
        ;


      
      
        19
      
      
            }


      
      
        20
      
      
        return
      
      
        false
      
      
        ;


      
      
        21
      
      
        }


      
      
        22
      
      
        23
      
      
        int
      
       main(
      
        int
      
       argc, 
      
        char
      
      **
      
         argv) {


      
      
        24
      
      
        string
      
      
         S1, S2, S3;


      
      
        25
      
           cin >> S1 >> S2 >>
      
         S3;


      
      
        26
      
           vector<
      
        int
      
      > charsInS1(
      
        26
      
      , 
      
        0
      
      ), charsInS2(
      
        26
      
      , 
      
        0
      
      ), charsInS3(
      
        26
      
      , 
      
        0
      
      
        );


      
      
        27
      
      
        28
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < S1.length(); ++
      
        i) {


      
      
        29
      
               charsInS1[S1[i] - 
      
        '
      
      
        A
      
      
        '
      
      ]++
      
        ;


      
      
        30
      
               charsInS2[S2[i] - 
      
        '
      
      
        A
      
      
        '
      
      ]++
      
        ;


      
      
        31
      
               charsInS3[S3[i] - 
      
        '
      
      
        A
      
      
        '
      
      ]++
      
        ;


      
      
        32
      
      
            }


      
      
        33
      
      
        34
      
      
        int
      
       common13 = 
      
        0
      
      , common23 = 
      
        0
      
      
        ;


      
      
        35
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < 
      
        26
      
      ; ++
      
        i) {


      
      
        36
      
      
        if
      
       (charsInS3[i] > charsInS1[i] +
      
         charsInS2[i]) {


      
      
        37
      
                   cout << 
      
        "
      
      
        NO
      
      
        "
      
       <<
      
         endl;


      
      
        38
      
      
        return
      
      
        0
      
      
        ;


      
      
        39
      
      
                }


      
      
        40
      
               common13 +=
      
         min(charsInS3[i], charsInS1[i]);


      
      
        41
      
               common23 +=
      
         min(charsInS3[i], charsInS2[i]);


      
      
        42
      
      
            }


      
      
        43
      
      
        44
      
      
        if
      
       (common13 < S3.length() / 
      
        2
      
       || common23 < S3.length() / 
      
        2
      
      
        ) {


      
      
        45
      
               cout << 
      
        "
      
      
        NO
      
      
        "
      
       <<
      
         endl;


      
      
        46
      
           } 
      
        else
      
      
         {


      
      
        47
      
      
        bool
      
       ans = backtrack(S3, 
      
        0
      
      , 
      
        0
      
      , 
      
        0
      
      
        , charsInS1, charsInS2);


      
      
        48
      
               cout << (ans ? 
      
        "
      
      
        YES
      
      
        "
      
       : 
      
        "
      
      
        NO
      
      
        "
      
      ) <<
      
         endl;


      
      
        49
      
      
            }


      
      
        50
      
      
        return
      
      
        0
      
      
        ;


      
      
        51
      
       }
    

?

A Great Alchemist


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 免费视频爱爱太爽在线观看 | 九色精品视频在线观看 | 日韩一级大毛片欧美一级 | 久久精品一区二区三区不卡 | 日韩成人在线网站 | 爆操白虎逼 | 五月色婷婷琪琪综合伊人 | 日本中文字幕在线观看 | 99久热在线精品视频播放6 | 91精选视频 | 色偷偷要色偷偷网站视频在线 | 97se亚洲综合自在线尤物 | 日本最新免费二区 | 逆天至尊免费看229集 | 亚洲综合区小说区激情区噜噜 | 男人看的网址 | 日韩字幕一中文在线综合 | 奇米影视亚洲春色77777 | 精品国产你懂的在线观看 | 亚洲国产精品第一区二区三区 | 国产精品视频九九九 | 伊人精品国产 | 欧美做爰xxxⅹ在线视频hd | 亚洲精品色一区二区三区 | 特级aav毛片日本免费视频 | 亚洲欧洲日韩国产一区二区三区 | 妖精视频在线观看网站 | 亚洲精品免费日日日夜夜夜夜 | 久久中文字幕在线 | 国产区精品福利在线观看精品 | 久久综合五月天 | 亚洲欧美日韩国产精品 | 91精品国产免费久久久久久 | 高清亚洲综合色成在线播放放 | 麻豆视频一区二区 | 国产亚洲精品看片在线观看 | 婷婷四房色播 | www.欧美.com| 久久免费激情视频 | 国产精品久久久久aaaa | 中文字幕.com|