[GD_SGOI 三角阵]找规律、字符串变换

【题目】

提交文件：tri.pas/.cpp

输入文件：tri.in

输出文件：tri.out

 

　　把3个相同的小三角形按如下方式连接起来就形成了一个一级三角阵。

　　我们把位于顶端的小三角形标记为T，位于左端的小三角形标记为L，位于右端的小三角形标记为R。

　　把3个一级三角阵按同样的方式连接起来就形成了一个二级三角阵。

　　我们为顶端的三角阵的标记添加前缀T，为左端的三角阵的标记添加前缀L，为右端的三角阵的标记添加前缀R。

把3个二级三角阵按同样的方式连接起来就形成了一个三级三角阵。

同样地为顶端的三角阵的标记添加前缀T，为左端的三角阵的标记添加前缀L，为右端的三角阵的标记添加前缀R。

依次类推，可以构建一个N级三角阵。

如果两个小三角形有公共点，则认为这两个小三角形相邻，可以一步到达。

你的任务是求从一个小三角形走到另一个小三角形至少需要多少步。

 

输入格式：

第一行是三角阵的等级Ｎ（Ｎ≤30）。

第二行和第三行都是一个长度为N的字符串，由大写字母“L”、“R”、“T”组成，表示两个小三角形的标号。

 

输出格式：

输出一个数，表示从一个小三角形走到另一个小三角形所需的最少步数。

 

输入样例：

3

TRL

RLR

 

输出样例：

5

 

样例解释：

从“TRL”出发，途经“TRR”、“RTT”、“RTL”、“RLT”，最后到达“RLR”，一共需要5步。

【算法分析】
首先我们围观它走一步的话，那个字符串会有什么变化。
第一种可能："abc"->"abk" 然后这个这个c和k是可以任意的。
第二种可能："xyzabbbbbbb…bbbbb"->"xyzbaaaaaaa…aaaaa"，当然，这个a和b不能相同。
于是可以很直接地得到一个走到本三角顶点的算法。
那就是从高位到低位，一位一位地处理，具体自己YY吧，不难。
并且容易发现他是最优的。（怎么发现？看图。。。）
然后对于A串和B串，我们先把相同的前缀删掉。
对于剩下的东西而言。有两种可能。
剩下的设长度为n。
1、从我所属于的这个(n-1)级三角形直接走到对象的那个(n-1)级三角形。
2、从我所属于的这个(n-1)级三角形绕路另一个(n-1)级三角形，再跑到对象的那个(n-1)三角形。
于是分开两种情况，min一下即可。
【CODE】
#include #include #include typedef __int64 lld;
const int N=55;
int n;
char str1[N],str2[N],s1[N],s2[N];

lld solve(char *ss1,char *ss2){
memcpy(s1,ss1,sizeof(s1));
memcpy(s2,ss2,sizeof(s2));
int i,j,k;
lld ans=0;
for (i=1;i<=n;i++)
if (s1[i]!=s2[i]){
for (j=n;j>i;j–)
if (s2[i]!=s1[j]){
ans+=(lld)(1)<<(n-j);
s1[j]=s2[i];
}
ans++;
for (j=n;j>i;j–) s1[j]=s1[i];
s1[i]=s2[i];
}
return ans;
}

void work(){
if (strcmp(str1+1,str2+1)==0) puts("0");
else{
lld ans=solve(str1,str2);
char str[N];
memcpy(str,str2,sizeof(str));
int i=1,j;
while (str1[i]==str2[i]) i++;
if (str1[i]==’T’){
if (str2[i]==’L’) str[i]=’R’;
if (str2[i]==’R’) str[i]=’L’;
}
if (str1[i]==’L’){
if (str2[i]==’T’) str[i]=’R’;
if (str2[i]==’R’) str[i]=’T’;
}
if (str1[i]==’R’){
if (str2[i]==’L’) str[i]=’T’;
if (str2[i]==’T’) str[i]=’L’;
}
for (j=i+1;j<=n;j++) str[j]=str1[i];
lld now=solve(str1,str)+solve(str,str2);
if (now printf("%I64dn",ans);
}
}

int main(){
freopen("tri.in","r",stdin);
freopen("tri.out","w",stdout);
scanf("%d%s%s",&n,str1+1,str2+1);
work();
return 0;
}