首页
登录 | 注册

poj 3087 字符串+set(洗牌)

题意:给定长度都为C两个字符串,S1,S2,和一个要求的结果字符串SS。先把S2的最下面一张牌放在最下面,然后S1,S2交错的叠放,得到S(洗牌操作)。

如果此时得到SS,则输出次数。否则再把S最下面的C个字符当做S1,把剩下的当做S2,再次重复上面的过程。如果不能得到目标字符串,则输出-1。

思路:模拟。

一开始只以为回到初始串则输出-1,实际上有可能会的变换过程中的任意一个串,那么循环了就应该输出-1。所以应该用一个判重的数据结构,set可以选择。

另外读入的时候一开始用的getchar,怎么着都WA,后来改成scanf才A(可能每一行后面有多余的空格)

#include <cstdio>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
#define clr(s,t) memset(s,t,sizeof(s))
#define N 505
int T,n,c;
char s[N],t[N],base[N],tmp[N];
set<string> flag;
void inverse(char* x,int len){
    int i,j;
    for(i = 0,j = len-1;i<j;i++,j--){
        char ch = x[i];
        x[i] = x[j];
        x[j] = ch;
    }
}
int main(){
    scanf("%d",&T);
    for(c = 1;c<=T;c++){
        int i,res = 0;
        flag.clear();
        scanf("%d\n",&n);
        scanf("%s %s %s",s+1,t+1,base+1);
        inverse(s+1,n);
        inverse(t+1,n);
        inverse(base+1,2*n);
        strcat(t+1, s+1);
        strcpy(s+1,t+1);
        tmp[2*n+1] = '\0';
        while(strcmp(t+1, base+1)){//找到目标串
            string ttt(t+1);
            flag.insert(ttt);
            for(i = 1;i<=2*n;i++){//这个公式纸上推一下即可
                if(i&1)
                    tmp[i] = t[i/2+n+1];
                else
                    tmp[i] = t[i/2];
            }
            ttt = tmp+1;
            if(flag.count(ttt))//判重
                break;
            res++;
            strcpy(t+1, tmp+1);
        }
        if(!strcmp(t+1, base+1))
            printf("%d %d\n",c,res);
        else
            printf("%d %d\n",c,-1);
    }
    return 0;
}




2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号