【POJ - 3087】Shuffle'm Up(模拟)

我会带着你远行 2021-11-26 17:30 194阅读 0赞

## [Shuffle'm Up][Shuffle_m Up] ##

直接写中文了

**Descriptions:**

给定两个长度为len的字符串s1和s2， 接着给出一个长度为len\*2的字符串s12。

将字符串s1和s2通过一定的变换变成s12，找到变换次数

变换规则如下：

假设s1=12345,s2=67890

变换后的序列 s=6172839405

如果s和s12完全相等那么输出变换次数

如果不完全相等，s的前半部分作为s1，后半部分作为s2，重复上述过程。

**Input**

第一行给出T(1≤T≤1000)，代表有T组数据，每组数据首先给出len(1≤len≤100)，接着给出两个长度为len的字符串s1 s2 然后给出长度为len\*2的字符串s12。

**Output**

首先输出处理数据组的编号（编号从1开始）

再输出变换次数并换行。

注意两个数字之间有空格。

对于变换次数，如果无需变换直接得到s12，那么输出0，如果无论怎么变换都不会得到s12，那么输出 -1。

**Sample Input**

>     2
>     4
>     AHAH
>     HAHA
>     HHAAAAHH
>     3
>     CDE
>     CDE
>     EEDDCC

**Sample Output**

>     1 2
>     2 -1

题目链接：  
[https://vjudge.net/problem/POJ-3087][Shuffle_m Up]

没什么说的，大模拟就行

AC代码:

#include <iostream>
    #include <cstdio>
    #include <fstream>
    #include <algorithm>
    #include <cmath>
    #include <deque>
    #include <vector>
    #include <queue>
    #include <string>
    #include <cstring>
    #include <map>
    #include <stack>
    #include <set>
    #include <sstream>
    #define mod 1000000007
    #define eps 1e-6
    #define ll long long
    #define INF 0x3f3f3f3f
    #define ME0(x) memset(x,0,sizeof(x))
    using namespace std;
    int T,len,total;
    char s1[105],s2[105],s3[210],s[210];
    map<string,int>str;
    void solve()
    {
        int step=0;
        while(1)
        {
            int pos=0;
            for(int i=0; i<len; i++)//模拟实现s
            {
                s[pos++]=s2[i];
                s[pos++]=s1[i];
            }
            s[pos]='\0';
            step++;
            if(!strcmp(s,s3))//s与s3比较，相等则返回0
            {
                cout<<total<<" "<<step<<endl;
                break;
            }
            if(str[s]>1&&strcmp(s,s3))//s与s3比较，不相等且，s出现的次数大于1
            {
                cout<<total<<" "<<-1<<endl;
                break;
            }
            if(!str.count(s))//判断s是否存在，不存在，则初始化为0
                str[s]=0;
            str[s]++;//没出现一次加一次
            for(int i=0; i<len; i++)//模拟实现s1，s2
                s1[i]=s[i];
            s1[len]='/0';
            for(int i=0,j=len; j<len*2; i++,j++)
                s2[i]=s[j];
                s2[len]='\0';
        }
    }
    int main()
    {
        total=0;
        cin>>T;
        while(T--)
        {
            str.clear();//清空数据
            total++;
            cin>>len>>s1>>s2>>s3;
            solve();
        }
    }

转载于:https://www.cnblogs.com/sky-stars/p/11114581.html

[Shuffle_m Up]: https://vjudge.net/problem/POJ-3087