这题放的比较迟，题目描述（Try SAT if you fail in GRE :P）也是直接，虽然没敢看GRE，但是看着描述想来这题是GRE的简化版了的样子。
这题同样是直接给出了Server端的程序，不过不得不提一下的是，似乎是题放出来过了好久才附上的，我也是醉了，难怪刚开始看这题完全不明所以。
这题首先有个sha1的检测，反正暴力就好，后面才开始关卡，我们直接看关键部分程序：
def SATexam(k): var = range(1, k + 1) * 3 random.shuffle(var) for i in xrange(k // 2): v = random.choice(var) var[v] = -var[v] return var def SATjudge(sat, answer): k = len(sat) // 3 assign = [0] * k assert(len(sat) == k * 3) assert(len(answer) * 8 >= k) # at least k bits i, j = 0, 0 for i in xrange(k): assign[i] = (ord(answer[i // 8]) >> (i % 8)) & 1 for i in xrange(k): r = 0 for j in xrange(3): # neither SAT-1 nor SAT-2, it's SAT-3v = sat[i * 3 + j] r |= (v < 0) ^ (assign[abs(v) - 1] == 1) if not r: print 'ERR: %d %s' % (i, str(sat[i * 3: (i + 1) * 3])) return False return True
其中SATexam产生输入，就是1-n重复三遍，随机排序，然后选取部分取相反数，不过看起来取相反数的数量不是很大，然后SATjudge用来检查结果是否正确，可以认为是要我们给出一个01串，满足某个性质即可。
简单点说就是，把3n个数，3个一组分成n组后，要求每组的数至少有一个满足：这个数是负数 xor 这个数对应的01串中那一位为1。反正感觉条件很蛋疼，不太好描述就是了……
很显然，如果输入没有负数，我们直接给出一个全1串，显然是满足条件的，于是我们以这个为初始状态，将其中一些1改成0就好，不过时间复杂度简直没法算，并且想来题目对输入中负数个数的限制应该也是对这题这样调整的效率很有影响的。不过按照之前的经验看，这种题暴力应该是都可以算出来的，于是果断对输入从前往后扫，如果发现，某一位不满足了，就尝试调整结果的01串就好，然后还准备了各种调整时的优化策略，虽然到最后都还没用上就轻松过了。
比赛时的程序如下：
#!/usr/bin/env python
#encoding:utf-8
import string
import hashlib
import itertools
import zlib
import struct
import zio
ROUNDS = 50
# n = 0
# cnt = []
# data = []
# adj_left = ''
# ans = []
# adj_right = ''
def link(i, j, sign):
adj_left[i].append(j)
adj_right[j].append((i, sign))
cnt[i] += sign ^ ans[j]
def update_right(right):
ans[right] = not ans[right]
for i, s in adj_right[right]:
if s ^ ans[right]:
cnt[i] += 1
else:
cnt[i] -= 1
def adjust_right(left, right):
update_right(right)
for i, s in adj_right[right]:
if left == i:
continue
if not adjust_left(right, i):
update_right(right)
return False
return True
def adjust_left(right, left):
if cnt[left] > 0:
return True
for i in adj_left[left]:
if right == i:
continue
if adjust_right(left, i):
return True
return False
def solve():
global n
global cnt
global data
global adj_left
global ans
global adj_right
n = len(data) / 3
cnt = [0] * n
adj_left = [[] for i in xrange(n)]
ans = [True] * n
adj_right = [[] for i in xrange(n)]
for i in xrange(n * 3):
link(i / 3, abs(data[i]) - 1, data[i] < 0)
for i in xrange(n):
if not adjust_left(-1, i):
print 'Error!!!'
result = ''
for i in xrange(0, n, 8):
s = ans[i:i + 8][::-1]
s = ''.join([str(int(j)) for j in s])
result += chr(int(s, 2))
result = zlib.compress(result)
print len(result), io.write(struct.pack('>I', len(result)) + result)
def challenge():
start = io.readline().strip('n')
print start
# all_chars = [chr(i) for i in xrange(256)]
for pad in itertools.combinations(string.printable, 20 - len(start)):
if hashlib.sha1(start + ''.join(pad)).digest().endswith('xFFxFFxFF'):
io.write(start + ''.join(pad))
print zio.HEX(start + ''.join(pad))
break
TARGET = ('202.112.26.111', 23333)
# TARGET = ('127.0.0.1', 8888)
io = zio.zio(TARGET, print_read=False, print_write=False, timeout=10000000)
challenge()
for i in xrange(1, ROUNDS + 1):
print '=' * 10 + 'Level ' + str(i) + '=' * 10
io.read_until('Enjoy your SAT:n')
data_len = struct.unpack('>I', io.read(4))[0]
data = zlib.decompress(io.read(data_len)).split(',')
data = [int(i) for i in data]
io.read_until_timeout()
print len(data)
solve()
print 'Win! Get flag:'
# s = ''
# while True:
# s += io.read(1)
# print s
io.read_until('scholarship:n')
print io.read_until_timeout(60)
当时先是本地跑的，很轻松的就过了，结果跑线上的时候真是跑到哭出来，要传的数据太大，然后传输起来各种超时，最后把超时加到N大之后终于可以跑过了，可是在最后一组算完之后收flag却总是收不到，然后以各种姿势一次次的试，最后终于有一次一个字符一个字符的收的时候收到了，真是哭出来啊。本来还担心过计算太慢，结果真是我想太多了，计算比这网络传输快了不知道多少个数量级了都……