poj3087 Shuffle'm Up ——水题

April 19, 2013
POJ

题目链接：http://poj.org/problem?id=3087 题目大意：　　给定长度都为Ｃ两个字符串，Ｓ１，Ｓ2，和一个要求的结果字符串ＳＳ。先把Ｓ２的最下面一张牌放在最下面，然后Ｓ１，Ｓ２交错的叠放，得到Ｓ，再把Ｓ最下面的Ｃ个字符赋值给Ｓ１，把剩下的赋值给Ｓ２，再次重复上面的过程。最后求出要得到ＳＳ，需要几步这样的过程。题目思路：　　开始以为是用ＳＴＬ的栈，后来才发现根本用不到，直接用字符串模拟就可以了。为了学习一下ＳＴＬ，用的是ｓｔｒｉｎｇ类。只要比较当前得到的字符串和要得到的字符串是不是相等就可以了。如果永远也得不到要得到的字符串，那么就一定存在Ｓ１和Ｓ２和原来的Ｓ１和Ｓ２都对应相等，其实这道题目的难点就在这里。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int main(void){
#ifndef ONLINE_JUDGE
  freopen("3087.in", "r", stdin);
#endif
  int n, i, c, j; scanf("%d", &n);
  string s1, s2, s, S1, S2, S;
  for (i = 1; i <= n; ++i){
    printf("%d ", i);
    cin >> c >> s1 >> s2 >> S; int cnt = 0;
    S1 = s1; S2 = s2;
    string::iterator it; bool flag = false;
    s = "";
    while (1){
      for (j = 0; j < c; ++j){
        s += s2[j]; s+= s1[j];
      } s1 = s2 = ""; cnt++;
      if (!s.compare(S)) {flag = true; printf("%d\n", cnt);break;}
      for (j = 0; j < c; ++j){
        s1+=s[j]; 
      }
      for (j = c; j < s.length(); ++j){ s2+= s[j];}
      s = "";
      if (!s1.compare(S1) && !s2.compare(S2)) break;
    }
    if (!flag) printf("-1\n");
  }

  return 0;
}

看了人家的代码，http://blog.sina.com.cn/s/blog_6a0e04380100olz1.html，用到了ｓｅｔ，正好这道题目不难，正好学习一下ｓｅｔ类，所以也照着学了一下。但是有一个地方的思路有一点儿差别，就是，它判别是不是永远也得不到ＳＳ的时候用的是Ｓ是不是出现过，其实本质上和我的是一样的。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int main(void){
#ifndef ONLINE_JUDGE
  freopen("3087.in", "r", stdin);
#endif
  int n, i, j, index, cnt, c; scanf("%d", &n);
  string s1, s2, s3, s;
  set<string> myset;
  for (i = 1; i <= n; ++i){
    printf("%d ", i); cin >> c >> s1 >> s2 >> s3;
    s = s3; myset.clear(); cnt = index = 0;
    while (1){
      index = 0;
      for (j = 0; j < c; ++j){
        s[index++] = s2[j]; s[index++] = s1[j];
      } cnt++;
      if (s == s3){ printf("%d\n", cnt);break;}
      if (myset.count(s) == 1){printf("-1\n"); break;}
      else{
        s1.assign(s, 0, c); s2.assign(s, c, c);
        myset.insert(s);
      }
    }
  }

  return 0;
}

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

Read more