博客

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
// #define TDS_ACM_LOCAL
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;
}