BruteForce,纯模拟吧,无解时会回到初始态。
不过这题好像有数学方法的,
而且任何情况都会回到初始态,
这个应该有证明。
还记得有一道题是求回到初始态的步数。。
总之是用BF秒过了。。
更多深入以后研究。

PKU3087
1
/**//*
2
Task: pku3087
3
Author: DMKaplony
4
Date: 04/03/2010 11:16:17 China Standard Time
5
State:
6
6511528 DMKaplony 3087 Accepted 180K 0MS C++ 1729B 2010-03-04 11:32:06
7
Memo: BruteForce--Forxcc0322
8
*/
9
10
#include <iostream>
11
12
#define MAXL 3000
13
14
using namespace std;
15
16
char a[MAXL], b[MAXL], aa[MAXL], bb[MAXL], g[MAXL];
17
int n;
18
19
bool NoAnswer()
{
20
int i;
21
for (i=1; i<n+1; i++)
{
22
if (a[i] != aa[i] || b[i] != bb[i])
23
return false;
24
}
25
return true;
26
}
27
int Check()
{
28
if (NoAnswer())
{
29
return -1;
30
}
31
for (int i=1; i<n+1; i++)
{
32
if (a[i] != g[i] || b[i] != g[n + i])
33
return 0;
34
}
35
return 1;
36
}
37
38
void Alter()
{
39
char tmp[MAXL];
40
int i;
41
for (i=1; i<n+1; i++)
{
42
tmp[(i << 1) - 1] = b[i];
43
tmp[i << 1] = a[i];
44
}
45
for (i=1; i<n+1; i++)
{
46
a[i] = tmp[i];
47
b[i] = tmp[n + i];
48
}
49
}
50
int main()
{
51
int cases;
52
scanf("%d", &cases);
53
for (int o=1; o<cases+1; o++)
{
54
scanf("%d", &n);
55
int i;
56
for (i=1; i<n+1; i++)
{
57
scanf(" %c", &a[i]);
58
}
59
for (i=1; i<n+1; i++)
{
60
scanf(" %c", &b[i]);
61
}
62
//
63
for (i=1; i<(n << 1)+1; i++)
{
64
scanf(" %c", &g[i]);
65
}
66
//
67
memcpy(aa, a, sizeof(a));
68
memcpy(bb, b, sizeof(b));
69
int ret;
70
int counter = 1;
71
Alter();
72
while (1)
{
73
ret = Check();
74
if (ret)
75
break;
76
Alter();
77
counter++;
78
}
79
if (ret == -1)
80
printf("%d %d\n", o, ret);
81
else
82
printf("%d %d\n", o, counter);
83
}
84
return 0;
85
}
86