poj3087:http://poj.org/problem?id=3087
题意:题意简化之后的就是:给你两个长度均为c的字符串s1,s2,然后给你一个2*c的串ss,现在每次从s2,中取一个,然后再从s1,取出一个(都是从左往右),组成新的串,如果新的的串和ss相同,则说明s1,s2可以通过若干次洗牌,组成ss。现在就是来求这个步数,若存在,则输出,否则输出-1.
题解:直接模拟。但是要注意一个问题。就是strcmp(s1,s2)s1,s2后面要加‘\0’,我就是没有注意这个问题结果贡献了4wa。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
char s1[],s2[],aim[],temp[];
int c;
int main(){
int t;
scanf("%d",&t);
for(int cas=;cas<=t;cas++){
map<string,int>Q;
scanf("%d",&c);
scanf("%s",s1);
scanf("%s",s2);
scanf("%s",aim);
int counts=;
Q[aim]=;bool flag=true;
while(true){
for(int i=;i<=*c-;i+=)
temp[i]=s2[i/];
for(int i=;i<=*c-;i+=)
temp[i]=s1[i/];
counts++;
temp[*c]='\0';
if(strcmp(temp,aim)==)break;
if(Q[temp]){
flag=false;
break;
}
Q[temp]=;
for(int i=;i<c;i++)
s1[i]=temp[i];
for(int j=c;j<=*c-;j++)
s2[j-c]=temp[j];
}
if(flag)printf("%d %d\n",cas,counts);
else printf("%d -1\n",cas);
}
}