Shuffle’m Up
题目传送门
Shuffle’m Up
题目大意
给你两个长度为len的字符串分别为s1，s2，和一个长度为2*len的字符串s 现在将s1和s2像洗牌那样重叠在一起，先是s2第一个，再是s1第一个… 若组合成的s’为s，则输出此时的次数，否则将s’前一半拆分为s1，后一半为s2 不可能出现s’等于s的情况则输出-1
思路
直接模拟即可，不能相等的情况为s’重复出现的时候
AC Code
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
using namespace std
;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
const int N
=2e5 +9;
int len
, cnt
;
char s
[N
], s1
[N
], s2
[N
], ss
[N
];
void solve(){
cin
>>len
;
cin
>>s1
>>s2
>>ss
;
map
<string
, int> mp
;
int flag
=0, ans
=0;
while(1){
ans
++;
int lens
=0;
for(int i
=0; i
<len
; i
++){
s
[lens
++]=s2
[i
];
s
[lens
++]=s1
[i
];
}
s
[lens
]='\0';
if(!strcmp(ss
,s
)) {flag
=1; break;}
if(mp
.find(s
)!=mp
.end()) break;
for(int i
=0; i
<len
; i
++){
s1
[i
]=s
[i
];
s2
[i
]=s
[i
+len
];
}
mp
[s
]++;
}
if(flag
) cout
<<++cnt
<<" "<<ans
<<endl
;
else cout
<<++cnt
<<" -1"<<endl
;
return ;
}
signed main(){
ios
::sync_with_stdio(0);
cin
.tie(0), cout
.tie(0);
#ifdef TDS_ACM_LOCAL
freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
int T
;
cin
>>T
;
while(T
--) solve();
return 0;
}
