青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(927) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲图片在区色| 国产日韩亚洲| 亚洲国产精品视频| 牛夜精品久久久久久久99黑人| 欧美怡红院视频一区二区三区| 国产亚洲精品资源在线26u| 久久综合成人精品亚洲另类欧美| 久久久久一区二区三区| 99国产精品久久| 一区二区三区久久| 国产偷自视频区视频一区二区| 久久在线免费观看视频| 男女av一区三区二区色多| 妖精视频成人观看www| 亚洲午夜未删减在线观看| 国产亚洲精品久久久久婷婷瑜伽| 欧美国产精品| 国产精品久久二区| 免费欧美在线| 国产精品久久久久久久久久免费看| 久久久久久久久蜜桃| 欧美风情在线观看| 久久精精品视频| 欧美激情第二页| 久久精品在线免费观看| 欧美国产日韩xxxxx| 久久riav二区三区| 欧美激情一区二区三区在线| 久久av资源网站| 欧美日韩成人| 麻豆成人在线播放| 国产精品手机视频| 亚洲精品精选| 狠久久av成人天堂| 夜久久久久久| 日韩视频一区二区三区| 久久精品国产精品 | 国产伦精品一区二区三区高清版 | 欧美成人激情视频| 国产精品综合久久久| 91久久精品www人人做人人爽| 国产亚洲精品v| 一本综合久久| 日韩午夜视频在线观看| 久久久久在线观看| 久久亚洲精品一区二区| 国产精品亚洲人在线观看| 亚洲日本电影在线| 亚洲欧洲精品一区二区三区波多野1战4 | 亚洲欧美视频在线观看| 欧美大香线蕉线伊人久久国产精品| 久久国产一二区| 国产欧美日韩视频在线观看| 一区二区三区四区五区视频| 91久久精品美女高潮| 久久亚洲精品一区二区| 久久久女女女女999久久| 国产精品亚洲综合色区韩国| 在线午夜精品| 亚洲欧美日韩综合| 欧美四级在线观看| 亚洲午夜一二三区视频| 亚洲欧美资源在线| 国产美女精品视频免费观看| 香蕉久久精品日日躁夜夜躁| 欧美在线视频一区二区三区| 国产欧美日韩麻豆91| 久久爱另类一区二区小说| 久久亚洲一区二区| 亚洲高清久久| 欧美激情亚洲综合一区| 亚洲毛片播放| 亚洲欧美日韩精品久久久久| 国产日韩在线一区| 六月婷婷一区| 日韩一级精品| 欧美一级在线亚洲天堂| 国产一区二区精品久久91| 久久久久久久性| 亚洲精品麻豆| 亚洲午夜女主播在线直播| 国产精品日日摸夜夜摸av| 欧美亚洲综合在线| 欧美高清在线| 亚洲欧美国产三级| 狠狠色伊人亚洲综合成人| 欧美国产精品劲爆| 亚洲一区二区三区三| 久久免费视频这里只有精品| 亚洲电影免费观看高清| 欧美日韩精品不卡| 久久av红桃一区二区小说| 最新国产の精品合集bt伙计| 亚洲欧美日韩一区二区在线 | 亚洲人成77777在线观看网| 亚洲少妇最新在线视频| 国产色婷婷国产综合在线理论片a| 久久久久国产成人精品亚洲午夜| 亚洲电影av在线| 欧美中文字幕在线| 日韩亚洲欧美成人| 国产亚洲视频在线观看| 欧美屁股在线| 久久免费视频网| 亚洲午夜精品久久久久久app| 老色批av在线精品| 午夜精品婷婷| 亚洲美女91| 韩日精品中文字幕| 国产精品成人观看视频免费| 久久亚洲美女| 亚洲尤物视频网| 日韩视频国产视频| 欧美成人黑人xx视频免费观看| 午夜视频一区在线观看| 日韩一区二区精品在线观看| 国自产拍偷拍福利精品免费一| 欧美精品导航| 久久久一本精品99久久精品66| 亚洲高清不卡| 国产女主播一区二区| 欧美α欧美αv大片| 欧美一级理论片| 亚洲精品中文字幕女同| 欧美国产精品v| 美女精品视频一区| 欧美一区二区三区男人的天堂| 亚洲色图自拍| 亚洲制服av| 亚洲一区二区三区免费观看| 亚洲精选成人| 亚洲高清123| 91久久久久久久久| 亚洲成人在线| 亚洲激情成人网| 亚洲国产日韩一级| 亚洲第一二三四五区| 一色屋精品视频在线观看网站| 黄色国产精品| 亚洲七七久久综合桃花剧情介绍| 欧美中文在线字幕| 午夜国产精品视频| 羞羞色国产精品| 欧美一级一区| 久久精品国产第一区二区三区| 亚洲欧美一区二区三区极速播放| 亚洲少妇中出一区| 性做久久久久久久免费看| 欧美在线www| 久久精品国产久精国产一老狼| 亚洲综合首页| 欧美在线一二三| 久久五月天婷婷| 欧美激情视频给我| 久久免费视频网| 久久婷婷久久一区二区三区| 老司机午夜精品视频在线观看| 麻豆精品传媒视频| 免费观看在线综合色| 亚洲黄色影院| 中国女人久久久| 午夜一级久久| 亚洲最新视频在线| 中日韩午夜理伦电影免费| 亚洲影视综合| 久久精品论坛| 亚洲国产va精品久久久不卡综合| 亚洲高清视频一区二区| 99精品国产高清一区二区| 日韩视频国产视频| 欧美中文字幕久久| 狂野欧美一区| 国产精品av久久久久久麻豆网| 国产精品欧美经典| 亚洲国产高清自拍| 亚洲欧美在线另类| 欧美激情中文字幕一区二区 | 在线观看欧美亚洲| 夜夜狂射影院欧美极品| 欧美一区二区日韩一区二区| 欧美国产免费| 亚洲欧美日韩高清| 欧美在线免费观看| 欧美日韩视频第一区| 国产资源精品在线观看| 一区二区三区欧美| 亚洲影院色在线观看免费| 亚洲自拍三区| 欧美韩日亚洲| 性欧美大战久久久久久久免费观看| 久久久91精品国产一区二区精品| 欧美凹凸一区二区三区视频| 国产精品羞羞答答xxdd| 日韩午夜精品视频| 蜜桃av一区二区| 新片速递亚洲合集欧美合集| 欧美日韩亚洲一区二区| 亚洲欧洲一区二区三区| 久久亚洲国产精品一区二区| 亚洲免费伊人电影在线观看av|