POJ3087 Shuffle’m Up(模拟)

题目链接

题意:洗扑克,两堆S1, S2 各有C个扑克。先从S2最下面拿一张放在新的一堆的最下面,再拿S1的最下面一张往上放,以此类推最后形成2*C个扑克组成的堆。上C个是新的S2,下C个是新的S1。问多少次能匹配上给定的顺序。

思路:set存储字符串,find方法判断是否有重复的。如果有重复的意味着构成一个循环节,如果还没匹配上就再也匹配不上了。(注意输入的字符串最左面是底部)

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
    //freopen("a.txt", "r", stdin);
    int N; cin >> N;
    for(int k = 1; k <= N; k++){
        int ans = 0, l;
        string s1, s2, s3;
        cin >> l >> s1 >> s2 >> s3;
        set<string> s;
        while(1){
            string s4;
            for(int i = 0; i < l; i++){
                s4 += s2[i];
                s4 += s1[i];
            }
            for(int i = 0; i < l; i++){
                s1[i] = s4[i];
                s2[i] = s4[i+l];
            }
            ans++;
            if(s4 == s3)    break;
            if(s.find(s4) == s.end())
                s.insert(s4);
            else{
                ans = -1;
                break;
            }
        }
        printf("%d %dn", k, ans);
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法