[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;
}

加入对话

4条评论

留下评论

您的电子邮箱地址不会被公开。