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

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>
            一区二区三区成人| 久久国产精品久久w女人spa| 欧美成人精品不卡视频在线观看 | 欧美国产精品劲爆| 欧美sm视频| av成人免费| 亚洲欧美日韩精品久久亚洲区| 国产精品久久精品日日| 欧美一区二区三区日韩视频| 久久人人九九| 一区二区高清在线观看| 亚洲综合色噜噜狠狠| 伊人久久婷婷色综合98网| 亚洲国产精品久久久久秋霞蜜臀 | 久久久久久伊人| 日韩午夜黄色| 羞羞色国产精品| 最新国产精品拍自在线播放| 中文久久精品| 在线日韩一区二区| 在线亚洲免费| 91久久精品国产91性色| 亚洲尤物在线视频观看| 亚洲国产小视频在线观看| 一区二区三区四区五区精品视频| 国产一区二区丝袜高跟鞋图片| 亚洲电影在线播放| 国产亚洲一二三区| 日韩视频免费大全中文字幕| 国语自产精品视频在线看一大j8 | 亚洲日韩欧美视频| 亚洲自拍电影| 一区二区三区不卡视频在线观看 | 欧美性做爰猛烈叫床潮| 免费在线观看成人av| 国产精品极品美女粉嫩高清在线| 欧美大香线蕉线伊人久久国产精品| 欧美日韩一区三区| 亚洲国产国产亚洲一二三| 国产欧美日韩亚洲| 国产精品99久久久久久久女警| 最新亚洲视频| 久久久蜜桃一区二区人| 欧美在线观看视频一区二区三区 | 欧美日韩精品高清| 欧美激情第五页| 国产一本一道久久香蕉| 亚洲欧美激情视频| 亚洲综合视频一区| 欧美日韩综合视频| 亚洲人成网站999久久久综合| 在线电影国产精品| 久久久久久免费| 久久伊人一区二区| 国产在线观看精品一区二区三区| 亚洲在线观看免费视频| 亚洲制服丝袜在线| 国产精品国产a级| 一区二区三区精品在线| 亚洲手机在线| 久久免费视频在线观看| 国产日韩在线看| 欧美在线观看网址综合| 久久精品一区二区三区不卡| 国产一区二区三区久久久久久久久| 亚洲女同在线| 久久久91精品国产| 激情婷婷欧美| 亚洲人成网站精品片在线观看| 亚洲全黄一级网站| 欧美日韩喷水| 亚洲无吗在线| 久久精品人人爽| 一区二区亚洲精品国产| 美女久久一区| 99国产欧美久久久精品| 午夜亚洲性色视频| 亚洲影音先锋| 久久亚洲精品伦理| 亚洲人成7777| 国产精品久久久久毛片大屁完整版| 亚洲性av在线| 美女脱光内衣内裤视频久久网站| 亚洲国产天堂久久综合| 欧美日韩国产不卡| 亚洲欧美日本另类| 欧美高清在线一区| 亚洲永久免费视频| 伊人久久婷婷色综合98网| 欧美精品一区二区视频| 亚洲一区影音先锋| 欧美激情自拍| 亚洲免费在线| 亚洲国产欧美国产综合一区 | 久久视频国产精品免费视频在线| 亚洲片在线观看| 欧美在线黄色| 日韩视频免费观看| 国产一区二区三区在线播放免费观看| 另类激情亚洲| 亚洲欧美日韩区| 亚洲激情小视频| 久久久国产一区二区| 99这里只有久久精品视频| 国产亚洲va综合人人澡精品| 欧美极品欧美精品欧美视频| 午夜精品一区二区三区四区| 91久久一区二区| 猫咪成人在线观看| 午夜在线电影亚洲一区| 日韩视频在线一区二区三区| 国产综合激情| 国产精品一区二区三区观看| 欧美国产视频在线观看| 久久久999精品免费| 亚洲免费网址| 在线亚洲欧美| 亚洲欧洲一区二区在线播放| 久久精品99久久香蕉国产色戒| 在线视频精品一| 最新国产拍偷乱拍精品| 在线精品视频一区二区| 国产亚洲精品综合一区91| 国产精品久久福利| 欧美三级特黄| 欧美日韩www| 欧美黄污视频| 欧美大片一区二区| 欧美大片18| 欧美成人激情在线| 免费欧美高清视频| 久久五月婷婷丁香社区| 久久精品国产免费| 欧美激情精品久久久久久大尺度| 久久久久久久波多野高潮日日| 亚洲欧美日韩在线观看a三区| 一本久久精品一区二区| 日韩一级大片在线| 日韩午夜激情| 亚洲一区国产视频| 亚洲欧美一区二区三区在线| 亚洲在线观看免费视频| 亚洲午夜av电影| 国内精品久久久久久| 国产区在线观看成人精品| 国产日韩欧美一区二区三区四区| 国产欧美在线视频| 好吊日精品视频| 在线精品观看| 99香蕉国产精品偷在线观看| 一本色道久久88亚洲综合88| 亚洲天堂成人在线观看| 午夜精品久久久99热福利| 久久国产高清| 欧美成人视屏| 日韩午夜在线观看视频| 亚洲视频日本| 久久激情久久| 欧美精品久久久久久久久老牛影院 | 欧美a级大片| 欧美日韩无遮挡| 国产欧美日本一区二区三区| 韩日精品在线| 日韩一区二区精品在线观看| 亚洲一区美女视频在线观看免费| 欧美在线观看一区| 亚洲第一区色| 亚洲一二三区在线| 久久理论片午夜琪琪电影网| 欧美人牲a欧美精品| 国产精品人人做人人爽人人添| 国内一区二区三区在线视频| 亚洲精品一区二区三区婷婷月| 亚洲欧美国产精品专区久久| 久久影院午夜论| 在线综合欧美| 久久一区二区三区四区| 国产精品久在线观看| 136国产福利精品导航| 亚洲伊人伊色伊影伊综合网| 久久综合九色综合欧美就去吻 | 99精品国产一区二区青青牛奶| 先锋影音久久久| 欧美激情中文字幕一区二区| 国产一区二区三区不卡在线观看| 亚洲理论电影网| 久久久福利视频| 日韩亚洲欧美综合| 另类成人小视频在线| 国产日韩精品一区二区三区 | 国产一区日韩一区| 亚洲桃花岛网站| 亚洲第一免费播放区| 欧美在现视频| 国产精品毛片| 9久re热视频在线精品| 亚洲第一中文字幕| 久久精品亚洲乱码伦伦中文| 国产精品女人毛片| 亚洲永久免费观看|