POJ - 3087 Shuffle'm Up解题报告（模拟）

题目大意： 就是给你两摞扑克牌，每摞有C张（100），洗牌操作就是完美的洗牌操作，一张插一张，然后就得到的牌再分成两摞，继续之前的操作，问你是否有可能洗出他所给出的目标顺序。1000组测试数据。  首先需要证明一个事情，就是，这两摞牌一直进行完美洗牌操作，进行若干次之后就会得到和原来一样的两摞牌。而且这个次数，只由牌数n确定。（在这里我默认的是所有牌都是不一样的）。 举例感觉一下： 5678 1234-->1526 3748-->3175 4286-->4321 8765这个疗程使两摞交换顺序并且两摞的牌都倒置，再继续一个疗程就变回原样了。这里发现，对于一个数的变化，对于数5，他的位置的变化是1-2-4-8-7-5-1。

那么，显然，显然，显然，对于一个第i次完美洗牌之后位于a[i]的数，一次完美洗牌之后，它的位置变化规律如下：

a[i+1]=( a[i]<=n/2 ? 2*a[i] : (a[i]-n/2)-1);

对于每摞有n张的两摞牌，变回与原来的样子所需要的完美洗牌次数为：我不会用n表示。

思路：

最简单的方法就是一直模拟，对于起始序列一直进行完美洗牌操作，直到再一次变为起始序列，每次操作之后，都检查是否出现目标序列。时间复杂度分析：1000组测试实例，每次洗牌操作需要100+判断需要200，洗牌操作最多可能进行多少次我不知道，设为s次。1000*300*s=3s*10e5。我赌一下，洗牌次数不会超过1000次。 

#include<iostream> #include<math.h> #include<string.h> #include<stdio.h> using namespace std; int s[210]={0}; int e[210]={0}; int n; int sum=0; bool same(int a[],int b[]) { int i=1; while(a[i]!=0) { if(a[i]!=b[i])return 0; i++; } return 1; } void ceshi(int a[]) { for(int i=1;i<=2*n;i++) { cout<<a[i]; } cout<<endl; } void dfs(int a[]) { //ceshi(a); if(same(a,e)==1) { return; } sum++; int next[210]={0}; for(int i=1;i<=n;i++) { next[2*i]=a[i]; } for(int i=n+1;i<=2*n;i++) { next[2*i-2*n-1]=a[i]; } //ceshi(next); if(same(next,s)==1) { sum=-1; return; } dfs(next); } int main() { int test; cin>>test; for(int k=1;k<=test;k++) { sum=0; cin>>n; getchar(); char l; for(int i=2*n;i>=n+1;i--) { scanf("%c",&l); s[i]=(int)(l-'A')+1; } getchar(); for(int i=n;i>=1;i--) { scanf("%c",&l); s[i]=(int)(l-'A')+1; } getchar(); for(int i=2*n;i>=1;i--) { scanf("%c",&l); e[i]=(int)(l-'A')+1; } getchar(); dfs(s); cout<<k<<" "<<sum<<endl; memset(s,0,sizeof(s)); memset(e,0,sizeof(e)); } }

注意，给你的S1，S2里面每种牌的个数有可能与目标序列里该种牌的个数不一样。

分类被分为广搜，本来以为会有什么更快的方法，但是去网上查了一下题解发现大家都是这个思路做成的模拟，也许是有什么大神级方法我没想道吧。