【模拟】POJ 3087

直达–>POJ 3087 Shuffle’m Up

题意：一开始没怎么看明白，注意现是从S2里拿牌放在最底下，再放S1，这样交叉放（我一开始以为是S1和S2随意哪个先放，分别模拟取最小），然后在从中间截一半，下半部给组成新的S1，上半部组成新的S2。然后再交叉洗牌，重复，问达到给出的S12最小的洗牌次数。

思路：题意懂了直接模拟就行，无法到达的情况就是某一次洗牌出来的S12和之前出现过的S12重合了，也就是形成了循环，此时无法达到给出的S12的情况那就是不可能了。判重没想到什么特别巧妙的方法就用了map。

另外这道题的数据似乎超了点，开到500+比较好。

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#include <map>

using namespace std;

const int maxn = 5000+5;

char s1[maxn];

char s2[maxn];

char S12[maxn*10];

char ss[maxn*10];

int len;

bool check(char a[],char b[]){

    if(strlen(a)!=strlen(b)) return false;

    for(int i=0;i<strlen(a);i++){

        if(a[i]!=b[i])

            return false;

    }

    return true;

}

int solve(char S1[],char S2[]){

    int ans = 0;

    int lenc = 0;

    map<string,int>M;

    while(1){

        ans++;

        int cnt=0;

        memset(ss,'\0',sizeof(ss));

        for(int i=0;i<len;i++){

            ss[cnt++] = S2[i];

            ss[cnt++] = S1[i];

        }

        //printf("CNT = %d,LEN = %d\n",cnt,strlen(ss));

        ss[cnt] = '\0';

        //printf("%s\n",ss);

        if(check(ss,S12)) return ans;

        string a = ss;

        if(!M[a])

            M[a]++;

        else return -1;

        for(int i=0;i<len;i++){

            S1[i] = ss[i];

            S2[i] = ss[len+i];  //模拟题WA只告诉了我们一件事 仔细读题

        }

        S1[len] = '\0';

        S2[len] = '\0';

        //printf("%s\n",S1);

        //printf("%s\n",S2);

    }

    return -1;

}

void init(){

    memset(s1,'\0',sizeof(s1));

    memset(s2,'\0',sizeof(s2));

    memset(S12,'\0',sizeof(S12));

    memset(ss,'\0',sizeof(ss));

}

int main()

{

    int N;

    int m=0;

    scanf("%d",&N);

    while(N--){

        init();

        scanf("%d",&len);

        getchar();

        gets(s1);

       //printf("%s\n",S1);

        gets(s2);

        //printf("%s\n",S2);

        gets(S12);

        //printf("%s\n",S12);

        //solve();

        printf("%d %d\n",++m,solve(s1,s2));

    }

    return 0;

}