poj3087 Shuffle'm Up —

poj3087 Shuffle'm Up ——水题

题目大意：

　　给定长度都为Ｃ两个字符串，Ｓ１，Ｓ2，和一个要求的结果字符串ＳＳ。先把Ｓ２的最下面一张牌放在最下面，然后Ｓ１，Ｓ２交错的叠放，得到Ｓ，再把Ｓ最下面的Ｃ个字符赋值给Ｓ１，把剩下的赋值给Ｓ２，再次重复上面的过程。最后求出要得到ＳＳ，需要几步这样的过程。

题目思路：

　　开始以为是用ＳＴＬ的栈，后来才发现根本用不到，直接用字符串模拟就可以了。为了学习一下ＳＴＬ，用的是ｓｔｒｉｎｇ类。只要比较当前得到的字符串和要得到的字符串是不是相等就可以了。如果永远也得不到要得到的字符串，那么就一定存在Ｓ１和Ｓ２和原来的Ｓ１和Ｓ２都对应相等，其实这道题目的难点就在这里。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <stack>
10 #include <queue>
11 #include <cmath>
12 #include <algorithm>
13 #define lson l, m, rt<<1
14 #define rson m+1, r, rt<<1|1
15 using namespace std;
16 typedef long long int LL;
17 const int MAXN =  0x3f3f3f3f;
18 const int  MIN =  -0x3f3f3f3f;
19 const double eps = 1e-9;
20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
21   {1,1},{1,-1},{-1,-1}};
22 
23 int main(void){
24 #ifndef ONLINE_JUDGE
25   freopen("3087.in", "r", stdin);
26 #endif
27   int n, i, c, j; scanf("%d", &n);
28   string s1, s2, s, S1, S2, S;
29   for (i = 1; i <= n; ++i){
30     printf("%d ", i);
31     cin >> c >> s1 >> s2 >> S; int cnt = 0;
32     S1 = s1; S2 = s2;
33     string::iterator it; bool flag = false;
34     s = "";
35     while (1){
36       for (j = 0; j < c; ++j){
37         s += s2[j]; s+= s1[j];
38       } s1 = s2 = ""; cnt++;
39       if (!s.compare(S)) {flag = true; printf("%d\n", cnt);break;}
40       for (j = 0; j < c; ++j){
41         s1+=s[j]; 
42       }
43       for (j = c; j < s.length(); ++j){ s2+= s[j];}
44       s = "";
45       if (!s1.compare(S1) && !s2.compare(S2)) break;
46     }
47     if (!flag) printf("-1\n");
48   }
49 
50   return 0;
51 }

看了人家的代码，http://blog.sina.com.cn/s/blog_6a0e04380100olz1.html，用到了ｓｅｔ，正好这道题目不难，正好学习一下ｓｅｔ类，所以也照着学了一下。

但是有一个地方的思路有一点儿差别，就是，它判别是不是永远也得不到ＳＳ的时候用的是Ｓ是不是出现过，其实本质上和我的是一样的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <stack>
10 #include <queue>
11 #include <cmath>
12 #include <algorithm>
13 #define lson l, m, rt<<1
14 #define rson m+1, r, rt<<1|1
15 using namespace std;
16 typedef long long int LL;
17 const int MAXN =  0x3f3f3f3f;
18 const int  MIN =  -0x3f3f3f3f;
19 const double eps = 1e-9;
20 const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
21   {1,1},{1,-1},{-1,-1}};
22 
23 int main(void){
24 #ifndef ONLINE_JUDGE
25   freopen("3087.in", "r", stdin);
26 #endif
27   int n, i, j, index, cnt, c; scanf("%d", &n);
28   string s1, s2, s3, s;
29   set<string> myset;
30   for (i = 1; i <= n; ++i){
31     printf("%d ", i); cin >> c >> s1 >> s2 >> s3;
32     s = s3; myset.clear(); cnt = index = 0;
33     while (1){
34       index = 0;
35       for (j = 0; j < c; ++j){
36         s[index++] = s2[j]; s[index++] = s1[j];
37       } cnt++;
38       if (s == s3){ printf("%d\n", cnt);break;}
39       if (myset.count(s) == 1){printf("-1\n"); break;}
40       else{
41         s1.assign(s, 0, c); s2.assign(s, c, c);
42         myset.insert(s);
43       }
44     }
45   }
46 
47   return 0;
48 }

写代码的过程中还是出现了一些低级的错误，看来代码的准确度还是不行啊～