洗牌(DAY 100)

1：题目

给定两叠纸牌 S1 和 S2，每叠恰好有 C 张牌。

每张牌的尺寸大小都完全相同，但是颜色可能不同。

下面介绍洗牌规则。

不妨设 S1 中纸牌从上到下编号依次为 a1,a2,…,aC，S2 中纸牌从上到下编号依次为 b1,b2,…,bC。

洗牌就是将这两叠牌交错堆叠在一起，形成一个拥有 2C 张牌的新牌堆 S12。

新牌堆中的牌由上至下依次为 a1,b1,a2,b2,…,aC,bC。

可参考下图：

3087_1.png

然后，将牌堆从中间一分为二，下半部分是新的 S1，上半部分是新的 S2。

这样就可以继续进行洗牌操作获得新的 S12 了。

给定 S1 和 S2，请问至少需要进行多少轮洗牌操作方可获得指定牌堆 S12。

输入格式
第一行包含一个整数 T，表示共有 T 组测试数据。

每组数据第一行包含一个整数 C。

第二行包含一个长度为 C 的由大写字母构成的字符串，其中第 i 个字母表示初始 S1 中由底向上第 i 张牌的颜色。

第三行包含一个长度为 C 的由大写字母构成的字符串，其中第 i 个字母表示初始 S2 中由底向上第 i 张牌的颜色。

第四行包含一个长度为 2C 的由大写字母构成的字符串，其中第 i 个字母表示目标 S12 中由底向上第 i 张牌的颜色。

输出格式
共 T 行，每行输出一组数据的结果，首先输出组别编号 i（从 1 开始），然后输出所需要的最少洗牌次数。如果无法通过洗牌获得目标牌堆，则输出 −1。

数据范围
1≤T≤1000,
1≤C≤100。
卡牌最多有 8 种颜色，用大写字母 A∼H 表示，所以输入字符串中不会出现其他大写字母。

输入样例：
2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC
输出样例：
1 2
2 -1

2：代码实现

```#include<bits/stdc++.h>
using namespace std;

int main(){
    
    auto suff = [](string a, string b){
    
        string ret;
        for(int i = 0; i < (int)a.size(); i++) ret += b[i], ret += a[i];
        return ret;
    };

    int tt; cin >> tt;
    for(int _ = 1; _ <= tt; _++){
    
        int n; cin >> n;
        string s1, s2, s3;
        cin >> s1 >> s2 >> s3;
        int ans = 1;
        set<string> mp;
        for(string t = suff(s1, s2); ; t = suff(t.substr(0, n), t.substr(n, n)), ans++){
    
            if(mp.find(t) != mp.end()) {
    ans = -1; break;}
            else if(t == s3) break;
            else mp.insert(t);
        }
        cout << _ << ' ' << ans << endl;
    }

    return 0;
}