code500这道题其实并不难，只是由于自己太错误的执着，导致花了不少时间。
题目描述如下：
女神Alice找回了钱钱，女神非常开心，然后就去洗澡了 这时Mallory已经逃走了！ plusplus7希望抓住Mallory，于是决定开挖掘机去追他。 刚刚坐上挖掘机，结果发现启动挖掘机需要把一些插头按照一定的顺序连接起来... 插头有两面，每个插头的两端都有颜色 如： 绿色和黑色插头 “G:B” 当插头的两个面颜色相同，才能被接在一起 如： 对接成功 “G:B = B:V” 对接失败 “G:B * C:G” 插座也有两面，一面有颜色，一面无颜色以"X"表示 如： 左插座 “X:B” 右插座 “C:X” 插座只有两个，且不可移动 如： “X:B * C:G = G:E * B:C * E:X” 对挖掘机的siri输入指令，“3 3 1” “X:B = B:C = C:G = G:E = E:X” 那么，问题来了... 218.2.197.248:7777
第一眼看到题目的时候，确实是被那个指令给搞懵了，但是稍微恢复了下神智之后，到nc上去试，试了半天总算猜对了指令的含义：
a b c 表示将第a到b个插头移动到第c个插头的前面（这里也将插座算入，编号从0开始）
弄明白指令的含义之后，说实在的，对于该怎么做其实还是没有什么好的想法（因为操作有步数限制，要在规定步数内完成才算有效）。
但是观察nc看到的数据发现，似乎所有的字母永远都只出现2次，即都是唯一匹配的，然后当时脑子里很快就有了个猜测：
对于两个相邻的未匹配的插头，假设编号为a – 1和a，left[i]、right[i]分别表示第i个插头的两个面的颜色，那么，一定存在b、c，使得left[a] = right[c]、right[a – 1] = left[b]，如果b、c满足b < c且[a – 1, a]与[b, c]不相交，那么我们这一步就将[b, c]这一段移动到a – 1与a中间，即指令为b c a。
这个猜想很好理解，至于这样做是不是就是最好的抉择没太想清楚怎么证明，但感觉是可行的。
然后，对于不满足这个猜想的条件的，我最开始是采取随便取一个的方式，结果花了很多时间也没能解决，经常会比要求的步数多1步，最多好像是能跑到30多轮吧，但是看了下code200的数据组数，50组，于是觉得这题也是这个数，于是就对跑不出来的特例暴搜得到答案后硬编码判断，然后就成功的跑到了68轮，感觉已经无法再爱了……
最后，无奈，重写了一下搜索的代码，加上上面的那个猜测作为A*，同时限制了一下，保证每次移动都不会将两个已经配对的插头分开，然后就很轻松就秒了，最后结果有92轮……
#!/usr/bin/env python
#encoding:utf-8
import socket
def get_one(s):
try:
ret = s.recv(100)
while ret.find(":Xn") == -1 and ret.find("SCTF") == -1:
ret += s.recv(100)
print ret
return ret[:-1]
except Exception, e:
print 'Fail', ret
return ret
def check(now, size):
for i in xrange(1, size):
if now[i - 1][2] != now[i][0]:
return False
return True
def swap(now, i, j, k, deep):
history[deep] = [i, j, k]
if k < i:
return now[:k] + now[i:j + 1] + now[k:i] + now[j + 1:]
elif k > j:
return now[:i] + now[j + 1:k] + now[i:j + 1] + now[k:]
return now
def dfs(now, deep, max_deep, size):
if deep == max_deep:
if check(now, size):
return True
return False
for i in xrange(1, size):
if now[i - 1][2] != now[i][0]:
for j in xrange(1, size):
if now[i - 1][2] == now[j][0]:
start = j
break
for j in xrange(0, size - 1):
if now[i][0] == now[j][2]:
stop = j
break
if start <= stop and (start > i or stop < i - 1):
return dfs(swap(now, start, stop, i, deep), deep + 1, max_deep, size)
for i in xrange(1, size - 1):
if now[i - 1][2] == now[i][0]:
continue
for j in xrange(i, size - 1):
if now[j][2] == now[j + 1][0]:
continue
for k in xrange(1, i):
if now[k - 1][2] != now[k][0] and dfs(swap(now, i, j, k, deep), deep + 1, max_deep, size):
return True
for k in xrange(j + 2, size):
if now[k - 1][2] != now[k][0] and dfs(swap(now, i, j, k, deep), deep + 1, max_deep, size):
return True
return False
def get_answer(now, max_step):
now = now.replace(' ', '').replace('=', '*').split('*')
size = len(now)
for i in xrange(1, max_step + 1):
if dfs(now, 0, i, size):
print history
return i
history = [[] for i in range(10)]
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('218.2.197.248', 7777))
round_count = 1
ret = get_one(s)[len("Let's start this game!n"):]
while True:
step = get_answer(ret, 7)
for i in xrange(step):
s.send("%d %d %d" % (history[i][0], history[i][1], history[i][2]))
ret = get_one(s)
print 'Round', round_count, 'finsh.n'
round_count += 1
ret = get_one(s)[len('Round pass...n'):]
重写代码的时间比之前小调优化的时间少了不知道多少倍，感觉大好的时光就这么浪费了，还好最后pwn400轻松秒了，不然估计真得为这个事情后悔好久~~~
关于代码写的丑的问题，各位看官就不用吐槽了，毕竟当时大脑已经是一半浆糊了，只要能跑出来，哪还有心情管代码美不美，直接在暴力上面改的，所以DFS都没有改成BFS，强行枚举了max deep，我也是服了我自己的……
这道题最后比赛结束之后竟然还被打电话challenge了，被质疑速度，看起来似乎标答应该不是搜索的样子，也不知道有没有哪位会愿意把标准解法分享一下了~~~