题意
你需要模拟一个洗牌过程,每一次把左右两个牌堆交叉叠放在一起,然后把整个叠放好的大牌堆再分成上下两半作为左右牌堆。现在给出你初始的左右牌堆,和一个要达到的目标大牌堆,问你至少要经过多少次洗牌,才能使左右牌堆直接叠放在一起等于大牌堆。
思路
这个题的数据还是比较小的,不妨尝试模拟洗牌过程,然后设定一个洗牌次数上界,只要在上界规定之内的次数没有洗出符合要求的牌堆,就视为无解。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; char s1[101]; char s2[101]; char ns1[101]; char ns2[101]; char st[202]; bool check(int n){ for (int i = 1; i <= n; i++) { if (s1[i] != st[i] || st[n+i] != s2[i]) { return false; } } return true; } void myshuffle(int n){ int llb = 1,rlb = 1,lub = n,rub = n; for (int i = 1; i <= n; i++) { if (i % 2) { ns1[i] = s2[rlb]; ns2[n+1-i] = s1[lub]; rlb++,lub--; }else{ ns1[i] = s1[llb]; ns2[n+1-i] = s2[rub]; llb++,rub--; } } memcpy(s1, ns1, sizeof(ns1)); memcpy(s2, ns2, sizeof(ns2)); } int main(){ int caseCnt = 0; scanf(" %d",&caseCnt); for (int d = 1; d <= caseCnt; d++) { int n; scanf(" %d",&n); for (int i = 1; i <= n; i++) { scanf(" %c",&s1[i]); } for (int i = 1; i <= n; i++) { scanf(" %c",&s2[i]); } for (int i = 1; i <= n*2; i++) { scanf(" %c",&st[i]); } const int BOUND = 10000; bool flag = false; for (int i = 0; i <= BOUND; i++) { if (check(n)) { printf("%d %d\n",d,i); flag = true; break; } myshuffle(n); } if (!flag) { printf("%d -1\n",d); } } return 0; } |
September 11, 2015
[…] POJ 3087 Shuffle’m Up […]