• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            coreBugZJ

            此 blog 已棄。

            生成全排列的非回溯方法(TopCoder SRM 591 DIV 2)

            問題來自 TopCoder SRM 591 DIV 2 的第二題:

            Problem Statement
               
            Let X and Y be two strings of equal length, consisting of uppercase English letters only. The two strings are called convertible if there is a permutation P of the English alphabet with the following property: if each character c in the string X is replaced by the character P(c), we obtain the string Y. (In other words, X and Y are convertible iff the following holds: whenever two letters of X are equal, the corresponding two letters of Y must be equal, and vice versa.)  For example, consider the string "ABCA". We can choose to replace each 'A' by a 'F', each 'B' by a 'B', and each 'C' by a 'G', obtaining the string "FBGF". Thus the strings "ABCA" and "FBGF" are convertible. The strings "ABCA" and "EFGH" are not convertible, because the two 'A's in the first string must correspond to the same letter in the second string. The strings "ABCA" and "EEEE" are not convertible, because different letters in the first string must correspond to different letters in the second string.  You are given two strings A and B of the same length. These strings only contain English letters from 'A' to 'I', inclusive. (That is, only the first 9 letters of the alphabet are used.)  You want to change A and B into two strings that are convertible. The only allowed change is to choose some indices (possibly none) and to remove the characters at those indices from each of the strings. (I.e., the removed characters must be at the same positions in both strings. For example, it is not allowed to only remove character 0 of A and character 3 of B.) For example, if A="ABAC", B="AHHA" and the chosen indices are 0 and 2, then the resulting strings will be "BC" and "HA". Our goal is to choose as few indices as possible, given that after the erasing we want to obtain two convertible strings. Compute and return the smallest possible number of chosen indices.
            Definition
               
            Class:
            ConvertibleStrings
            Method:
            leastRemovals
            Parameters:
            string, string
            Returns:
            int
            Method signature:
            int leastRemovals(string A, string B)
            (be sure your method is public)
               

            Constraints
            -
            A will contain between 1 and 50 characters, inclusive.
            -
            A and B will be of the same length.
            -
            A will contain characters from 'A' to 'I' only.
            -
            B will contain characters from 'A' to 'I' only.

            我的思路是窮舉A中字母與B中字母的對應關系,看哪種對應需要刪除的字母最少,這一最少值即是答案。
            窮舉對應關系,就是生成全排列。
            我生成全排列的方式是回溯。

            之后看其他人的代碼,發現一個由給定排列求出其下一個排列的函數,于是學習一下,自己實現如下:

            // 生成下一字典序排列
            // 假設a中元素互不相同
            // 若已經是最后一個字典序排列,則返回0,否則返回1
            int next_permutation( int a[], int n ) {
                    
            int i, j;
                    
            for ( i = n-1; (0 < i) && (a[i-1> a[i]); --i ) {
                    }
                    
            if ( 0 >= i ) {
                            
            return 0;
                    }
                    
            for ( j = n-1; j >= i; --j ) {
                            
            if ( a[ j ] > a[ i-1 ] ) {
                                    
            int tmp = a[ i-1 ];
                                    a[ i
            -1 ] = a[ j ];
                                    a[ j ] 
            = tmp;
                                    j 
            = n - 1;
                                    
            while ( i < j ) {
                                            tmp 
            = a[ i ];
                                            a[ i ] 
            = a[ j ];
                                            a[ j ] 
            = tmp;
                                            
            ++i; --j;
                                    }
                                    
            break;
                            }
                    }
                    
            return 1;
            }

            還有人使用的是C++的 <algorithm> 中 next_permutation 函數,功能一樣。


            posted on 2013-09-28 17:03 coreBugZJ 閱讀(910) 評論(0)  編輯 收藏 引用 所屬分類: ACM 、Algorithm

            国产成人无码精品久久久性色| 久久久久女教师免费一区| 91精品国产91久久久久久| 91久久精品电影| 色婷婷狠狠久久综合五月| 婷婷五月深深久久精品| 青青热久久综合网伊人| 四虎国产精品免费久久| 97久久国产综合精品女不卡| AV无码久久久久不卡网站下载| 久久有码中文字幕| 成人久久精品一区二区三区| 久久天天躁夜夜躁狠狠躁2022| 国产激情久久久久影院老熟女| 午夜精品久久久久久99热| 久久综合丁香激情久久| 亚洲欧美伊人久久综合一区二区| 久久er国产精品免费观看2| 亚洲中文字幕无码久久2017| 国产福利电影一区二区三区久久老子无码午夜伦不 | 亚洲精品乱码久久久久久中文字幕| 久久久久久午夜成人影院| 久久伊人五月天论坛| 精品久久一区二区三区| 伊人久久大香线蕉综合5g| 久久精品一区二区三区中文字幕| 亚洲综合熟女久久久30p| 亚洲成av人片不卡无码久久| 亚洲伊人久久大香线蕉苏妲己| 欧美一区二区三区久久综 | 综合久久一区二区三区| 国产精品成人无码久久久久久 | AA级片免费看视频久久| 九九精品99久久久香蕉| 色欲综合久久中文字幕网| 久久天天躁狠狠躁夜夜avapp| 久久人人爽人人澡人人高潮AV| 国产91久久综合| 久久成人18免费网站| 香蕉99久久国产综合精品宅男自 | 免费一级欧美大片久久网|