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

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| 久久精品国产第一区二区三区最新章节| 国产精品一区视频| 宅男在线国产精品| 一区二区三区欧美成人| 国产精品家教| 久久久精品tv| 蜜臀av在线播放一区二区三区| 欧美韩日亚洲| 制服诱惑一区二区| 亚洲欧美日韩国产成人| 激情懂色av一区av二区av| 欧美国产精品人人做人人爱| 欧美激情综合| 欧美中文字幕精品| 卡一卡二国产精品| 一区二区三区日韩| 午夜精品在线看| 亚洲日本欧美| 亚洲自拍偷拍网址| 亚洲日本欧美日韩高观看| 一区二区三区国产在线| 国产日韩欧美亚洲| 亚洲国产日韩欧美在线动漫| 国产精品v欧美精品v日韩 | 欧美激情二区三区| 欧美片第一页| 久久久综合网站| 欧美日韩一区二区三| 久久亚洲综合色| 国产精品久久久久久久久婷婷 | 国产一区清纯| 亚洲成色最大综合在线| 国产精品午夜国产小视频| 欧美激情第3页| 国产欧美一区二区白浆黑人| 91久久亚洲| 在线精品亚洲| 亚洲欧美在线x视频| 日韩亚洲不卡在线| 久久亚洲影音av资源网| 欧美在线观看网址综合| 欧美日韩三区| 亚洲东热激情| 1000部精品久久久久久久久| 亚洲永久免费观看| 亚洲一区二区三区在线看| 蘑菇福利视频一区播放| 久久综合伊人77777麻豆| 国产农村妇女精品一二区| 999在线观看精品免费不卡网站| 美日韩精品视频| 久久久精品久久久久| 欧美日韩hd| 欧美激情亚洲激情| 亚洲国产精品电影在线观看| 久久精品99国产精品酒店日本| 国产一区二区在线免费观看 | 国产综合在线看| 亚洲一区www| 亚洲一区三区视频在线观看| 欧美日韩视频免费播放| 欧美激情第六页| 亚洲高清一二三区| 美女视频一区免费观看| 美日韩在线观看| 伊人色综合久久天天| 久久久久免费观看| 女人香蕉久久**毛片精品| 在线精品视频一区二区| 免费成人高清| 亚洲激情在线观看| 在线视频你懂得一区二区三区| 亚洲女优在线| 午夜久久资源| 国产亚洲激情视频在线| 午夜精品视频网站| 久久五月天婷婷| 亚洲国产成人av| 欧美精品v国产精品v日韩精品| 午夜免费电影一区在线观看| 国产欧美视频一区二区| 久久夜色精品| 亚洲国产一二三| 亚洲综合999| 国产一区二区三区免费在线观看| 亚洲黄网站在线观看| 亚洲看片免费| 国产精品视频一区二区三区| 欧美一区2区视频在线观看| 玖玖在线精品| 中文亚洲视频在线| 国产日韩1区| 欧美国产精品劲爆| 亚洲资源在线观看| 欧美激情欧美狂野欧美精品| 亚洲一区日韩| 在线欧美电影| 国产精品久久久久久超碰| 久久国产66| 夜夜爽www精品| 久久久水蜜桃| 国产精品99久久久久久久女警 | 日韩亚洲欧美在线观看| 欧美在线视频播放| 亚洲精品三级| 国产欧美日韩视频| 蜜桃久久av一区| 午夜精品福利一区二区蜜股av| 一区二区三区欧美视频| 国产一区二区三区在线播放免费观看| 亚洲日本黄色| 久久久水蜜桃| 午夜精品亚洲| 一区二区三区欧美在线观看| 黄色一区二区三区四区| 国产精品青草久久久久福利99| 亚洲人精品午夜| 久久午夜av| 久久国产精品久久久| 一区二区三区精密机械公司| 在线欧美小视频| 国产欧美日韩麻豆91| 国产精品白丝av嫩草影院| 久久精品人人做人人综合| 亚洲一二区在线| 99国产精品国产精品久久 | 黄色日韩在线| 国产精品综合| 欧美四级在线观看| 美女图片一区二区| 久久免费视频网站| 欧美一区二区高清| 亚洲一区在线播放| 一区二区三区日韩在线观看| 亚洲韩日在线| 欧美激情精品久久久| 免费的成人av| 玖玖视频精品| 免费一级欧美在线大片| 快射av在线播放一区| 久久精品视频在线免费观看| 久久av在线看| 久久成人人人人精品欧| 久久国产手机看片| 久久精品在线| 久久久噜久噜久久综合| 久久久噜噜噜久噜久久| 久久天天躁狠狠躁夜夜爽蜜月| 欧美日韩中字| 欧美午夜精品理论片a级按摩| 亚洲三级视频| 一本久道久久综合中文字幕| 亚洲精品久久久蜜桃 | 久久精品日韩欧美| 久久国产精品亚洲va麻豆| 久久精品论坛| 免费观看亚洲视频大全| 久久综合色婷婷| 免费在线亚洲| 国产精品成人一区二区三区夜夜夜| 亚洲一区二区三区高清不卡| 亚洲一区二区av电影| 午夜精品影院| 久久久久久久久久久成人| 久热精品视频在线| 欧美日本亚洲| 国产伦精品一区二区三区视频孕妇 | 尤物yw午夜国产精品视频| 亚洲第一主播视频| 一本久久综合| 久久精品日韩| 亚洲国产欧美一区二区三区久久| 99国产成+人+综合+亚洲欧美| 国产精品久久久久久超碰| 国产精品s色| 在线成人中文字幕| 一区二区欧美在线| 久久人体大胆视频| 亚洲大胆人体在线| 亚洲一级黄色片| 久久综合久久综合久久综合| 欧美日韩小视频| 激情婷婷亚洲| 欧美一级免费视频| 亚洲国产一区二区三区在线播 | 久久久之久亚州精品露出| 亚洲激情视频| 欧美在线视频观看| 欧美久久久久久久| 一区三区视频| 香蕉国产精品偷在线观看不卡| 一本一本久久a久久精品综合麻豆| 狠狠色狠狠色综合日日tαg | 亚洲一区二区在线看| 欧美高清不卡| 一区二区三区在线看| 亚洲欧美日韩直播| 亚洲高清三级视频| 久久天天狠狠|