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

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中字母的對應(yīng)關(guān)系,看哪種對應(yīng)需要刪除的字母最少,這一最少值即是答案。
窮舉對應(yīng)關(guān)系,就是生成全排列。
我生成全排列的方式是回溯。

之后看其他人的代碼,發(fā)現(xiàn)一個由給定排列求出其下一個排列的函數(shù),于是學(xué)習(xí)一下,自己實現(xiàn)如下:

// 生成下一字典序排列
// 假設(shè)a中元素互不相同
// 若已經(jīng)是最后一個字典序排列,則返回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 函數(shù),功能一樣。


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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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热软件| 亚洲视频一区在线| 亚洲一区二区高清| 亚洲电影观看| 亚洲欧美色一区| 国产伦精品一区二区三区视频黑人| 一区二区毛片| 一区二区三区产品免费精品久久75| 欧美成人精品在线| 亚洲欧洲一区二区在线播放| 亚洲国产精品电影| 欧美精彩视频一区二区三区| 亚洲日本欧美| 99精品欧美一区二区三区| 欧美美女bb生活片| 亚洲网站在线播放| 在线亚洲精品福利网址导航| 欧美日韩中文字幕综合视频 | 亚洲一区二区三区精品在线| 久久免费高清| 久久激情婷婷| 亚洲人成在线观看一区二区| 亚洲丁香婷深爱综合| 亚欧成人在线| 国产精品扒开腿爽爽爽视频| 欧美风情在线观看| 欧美日本精品| 国产自产v一区二区三区c| 久久久亚洲高清| 久久这里有精品15一区二区三区 | 亚洲欧美日韩视频一区| 国产视频自拍一区| 亚洲国产精品第一区二区三区| 欧美精品 国产精品| 午夜精品亚洲| 蜜臀av性久久久久蜜臀aⅴ| 亚洲神马久久| 久久精品国产免费| 亚洲视频第一页| 久久精品综合| 亚洲视频在线观看视频| 久久国产福利| 亚洲高清免费视频| 日韩一区二区精品葵司在线| 欧美国产欧美亚洲国产日韩mv天天看完整| 国产精品99久久久久久白浆小说| 欧美一级淫片播放口| 最新日韩在线视频| 午夜精品理论片| 亚洲日本成人| 久久精品99无色码中文字幕| 99这里只有精品| 久久精品国产清高在天天线| 亚洲中字在线| 欧美激情久久久久| 久久久综合香蕉尹人综合网| 欧美日韩专区| 亚洲经典视频在线观看| 国产综合久久久久影院| 中文欧美在线视频| 99视频一区二区三区| 久久网站热最新地址| 久久国产精品99国产| 欧美日韩午夜剧场| 亚洲第一网站免费视频| 黄色日韩在线| 99热精品在线| 99国产欧美久久久精品| 亚洲自拍三区| 亚洲综合精品四区| 欧美午夜一区二区| 亚洲精品久久在线| 亚洲美女av黄| 欧美大片91| 欧美韩国日本一区| 亚洲成人中文| 久久一区二区三区超碰国产精品| 久久久人成影片一区二区三区观看| 国产精品国产三级国产普通话99| 亚洲黄色在线观看| 午夜视频一区在线观看| 亚洲视频欧美在线| 欧美性一二三区| 一本久久综合| 亚洲欧美激情一区二区| 欧美亚洲成人免费| 一区二区欧美国产| 欧美一级久久久| 国产精品一区免费观看| 欧美中文在线观看| 久久一区中文字幕| 黄网动漫久久久| 一区二区日韩伦理片| 亚洲一区二区欧美| 国产亚洲欧美一区在线观看| 亚洲欧美日韩第一区| 久久99在线观看| 激情综合五月天| 久久综合影音| 亚洲看片免费| 久久本道综合色狠狠五月| 国产亚洲精品自拍| 美日韩免费视频| 日韩亚洲一区在线播放| 午夜久久黄色| 永久91嫩草亚洲精品人人| 欧美精品一区二区三| 亚洲第一成人在线| 亚洲欧美日韩国产综合在线| 国产啪精品视频| 久久美女艺术照精彩视频福利播放| 欧美成人资源网| 亚洲欧美日韩精品在线| 国一区二区在线观看| 蜜臀av性久久久久蜜臀aⅴ四虎| 免费人成精品欧美精品| 一区二区三区日韩精品| 欧美色精品天天在线观看视频| 亚洲女同同性videoxma| 欧美激情第二页| 午夜精品久久久久久久久久久久久 | 亚洲第一在线| 亚洲欧美视频一区二区三区| 国产亚洲精品久久久久动| 欧美激情欧美激情在线五月| 亚洲综合成人婷婷小说| 欧美电影免费观看高清| 性欧美暴力猛交另类hd| 最新亚洲视频| 狠狠狠色丁香婷婷综合激情| 欧美日韩一级黄| 久久综合999| 香港久久久电影| 一区二区三区 在线观看视频| 久久综合999| 午夜影院日韩| 亚洲视频一区| 亚洲精品久久久久中文字幕欢迎你 | 亚洲一区二区精品在线观看| 在线日韩日本国产亚洲| 欧美日韩爆操| 欧美在线免费看| 亚洲图片你懂的| 国产日韩欧美二区| 欧美三区免费完整视频在线观看| 免费视频一区二区三区在线观看| 亚洲欧美在线观看| 亚洲调教视频在线观看| 亚洲人成小说网站色在线| 免费观看成人鲁鲁鲁鲁鲁视频 | 久久精品亚洲乱码伦伦中文 | 在线视频你懂得一区二区三区| 亚洲电影网站| 在线播放视频一区| 一区二区三区在线视频免费观看| 久久久精品一品道一区| 亚洲乱码国产乱码精品精天堂| 欧美激情亚洲自拍| 欧美成年人视频| 欧美激情1区2区| 亚洲电影在线播放| 91久久精品国产| 亚洲美女在线一区| 欧美韩日高清| 亚洲精品字幕| 在线亚洲欧美| 亚洲欧洲av一区二区| 欧美一区二视频| 久久精品99久久香蕉国产色戒| 久久国产精品72免费观看| 久久久久国色av免费观看性色| 一区二区三区四区蜜桃| 亚洲线精品一区二区三区八戒| 亚洲尤物在线| 亚洲区在线播放| 亚洲国产欧美久久| 亚洲一区二区三区午夜| 亚洲一区二区三区精品动漫| 亚洲综合三区| 久久一区二区三区四区| 亚洲美女视频| 欧美一区二区三区在线观看| 久久久夜夜夜| 美女国产精品| 国产欧美一区二区三区在线看蜜臀| 国内欧美视频一区二区| 亚洲国产一二三| 久久精品一区二区三区四区| 欧美成人免费在线观看| 99热精品在线观看| 久久精品91久久香蕉加勒比| 国产精品扒开腿做爽爽爽视频 | 欧美专区亚洲专区| 欧美大胆a视频| 国产精品综合| 99综合电影在线视频| 麻豆国产精品va在线观看不卡| 亚洲美女毛片| 久久一区二区三区av| 国产一区二区电影在线观看|