数组

一般数组

  1. 数组的下标从 0 开始.
  2. 数组的长度是数组中元素的个数.
  3. 数组的长度 len 为奇数时, ⌊len/2⌋ 号单元是中间的元素; len 为偶数时, ⌊len/2⌋ 号单元是中间两个元素中的后一个.
  4. 子数组: 数组中连续单元组成的数组, 类似子串的概念.
  5. 前缀: 形如 [0..i] 的子数组; 后缀: 形如 [i..n-1] 的子数组.
使数组的元素倒序排列 
# 将子数组 [0..n-1] 逆置
# 时间 O(n), 空间 O(1)
L.reverse1(0, n):
	b = 0, e = n
	while b < e:
		L.swap(b, e)
		++b, --e

L.reverse2(0, n):
	cofor i = 0 to n/2-1: # 并行地
		L.swap(i, n-1-i)
设数组是两个不相交子数组 A, B 的并置, 要求将数组由 AB 变为 BA. 
# 使用三次逆置, 将子数组 A = [0..i-1] 和 B = [i..n-1] 交换位置
# AB → B-1A-1 → BA
# 时间 O(n), 空间 O(1)
L.cyclic_shift(i):
	reverse(0, n)
	cobegin: # 并行地
		reverse(0, i)
		reverse(i, n)
删除数组中所有使得 f(x) == True 的值 x. 假设 f 的时空复杂度均是 O(1). 
# n = L.len; 时间 O(n), 空间 O(1)
L.remove_if1(f):
	passed = 0	# f(x) == False 的元素计数
	for i = 0 to L.len-1:
		if !f(L[i]):
			L[passed++] = L[i]
	L.len = passed

# 时间 O(n), 空间 O(1)
L.remove_if2(f):
	removed = 0	# f(x) == True 的元素计数
	for i = 0 to L.len-1:
		if f(L[i]):
			++removed
		else:
			L[i-removed] = L[i]
	L.len -= removed
逆置 循环移位 按值删除

有序数组

  1. 有序数组, 是指升序或降序的数组. 升序数组是任意相邻两个元素满足 L[i] ≤ L[i+1] 的数组. 降序数组是任意相邻两个元素满足 L[i] ≥ L[i+1] 的数组.
  2. 一般来说, 通过排序能实现的算法, 也可以通过散列或计数来实现. 例如数组无序时, 去重操作可以实现如下:
删除一个有序数组中值重复的元素, 使得所有元素两两不相等. 
# n = L.len; 时间空间均 O(n)
L.unique1():
	HashTable set
	for i = 0 to L.len-1:
		set.add(i)
	L.len = 0
	for val in set:
		L[L.len++] = val

# n = L.len; 时间 O(n), 空间 O(1)
L.unique2():
	if L.len == 0:
		return
	i = 0 # i 指向数组的*无重复元素前缀*的最后一个单元
	for j = 1 to L.len-1:
		if L[i] != L[j] and ++i != j:
			L[i] = L[j]
	L.len = i+1
将两个升序数组合并为一个升序数组. 
# m = M.len, n = N.len; 时间空间均 O(m+n)
merge(M, N):
	A = new array[M.len+N.len]
	i = j = k = 0
	while i < M.len and j < N.len:
		if M[i] <= N[j]:
			A[k++] = M[i++]
		else:
			A[k++] = N[j++]
	# 下面两个循环只有一个执行
	while i < M.len:
		A[k++] = M[i++]
	while j < N.len:
		A[k++] = N[j++]

给定一个长度为 n 的整数数组, 求数组中未出现的最小正整数.

思路：先排序, 然后顺序遍历数组, 依次在数组中查找正整数 1, 2, 3... 即可. 根据的 2, 也可以开辟一个长度为 n 的数组, 在 a[i]记录数字 i 出现的次数, 通过计数实现算法.

给定一些平面上的两两不同的点 (x[i], y[i]), 规定 (x[i], y[i]) < (x[j], y[j]) 当且仅当 x[i] < x[j] 且 y[i] < y[j]. 求极大元, 即求所有的点 (x[i], y[i]), 使得不存在其它的点满足 (x[j], y[j]) > (x[i], y[i]).

思路：将所有点关于 x 按降序排序, 取第一个点 (x[0], y[0]), 由于它关于 x 是最大的, 所以它是一个极大元. 接着正向扫描数组, 寻找下一个满足 y[i1] > y[0] 的下标 i1. 可以证明 (x[i1], y[i1]) 也是一个极大元. 接下来再寻找下一个满足 y[i2] > y[i1] 的下标 i2... 从而找到所有的极大元.

给定值 val, 求 i, j (允许 i == j), 使得 L[i] + L[j] == val. 
# 先排序 (时空复杂度由排序方法决定), 再执行下面的代码
# n = L.len; 时间 O(n), 空间 O(1)
L.two_sum(val):
	i = 0, j = L.len-1
	while i <= j: # 不允许 i == j 时, 写 i < j
		if L[i] + L[j] == val:
			return i, j
		elif L[i] + L[j] < val:
			++i
		else:
			--j
	return None
给定两数组 A, B 和值 val, 求 i, j, 使得 A[i] - B[j] == val. 
# 先排序, 再执行下面的代码
two_diff(A, B, val):
	i = j = 0
	while i < A.len and j < B.len:
		if A[i] - B[j] == val:
			return i, j
		elif A[i] - B[j] < val:
			++i
		else:
			++j
	return None
去重 归并 mex 偏序集的极大元 寻找和为给定值的两整数 在两数组中寻找差为给定值的两整数

顺序统计量与其它

下中位数 定义为一个长度为 n 的升序数组中 下标为 ⌊(n-1)/2⌋ 的元素. 类似地, 上中位数定义为该数组中下标为 ⌈(n-1)/2⌉ 的元素. 例如, n == 5 时 ⌊(n-1)/2⌋ == 2, ⌈(n-1)/2⌉ == 2; 上, 下中位数都是中间的元素. n == 6 时 ⌊(n-1)/2⌋ == 2, ⌈(n-1)/2⌉ == 3. 上, 下中位数分别是中间两个元素的后一个与前一个. 已知两个长度为 n 的升序序列. 求它们合并后的升序序列的下中位数. 
# n = L1.len; 时间 O(log n), 空间 O(1)
# 设 m1, m2 是两序列 L1, L2 的下中位数.
# 如果两个序列都只有一个元素, 则较小者就是所求的下中位数.
# 如果 m1 == m2, 则 L[m1] 就是所求的下中位数;
# 如果 m1 < m2, 则舍弃 L1 中较小的一半和 L2 中较大的一半,
# 舍弃后仍保持 L1.len == L2.len;
# 如果 m1 > m2, 则舍弃 L1 中较大的一半和 L2 中较小的一半,
# 舍弃后仍保持 L1.len == L2.len.
median(L1, L2):
	if L1.len == 0:
		return None
	diff = L1.len-1
	lo1 = lo2 = 0
	hi1 = hi2 = diff
	while diff > 0:
		m1 = lo1 + diff/2
		m2 = lo2 + diff/2
		if L1[m1] == L2[m2]:
			return L1[m1]
		elif L1[m1] < L2[m2]:
			hi2 = m2
			# 元素奇数个时加 0, 否则加 1
			lo1 = m1 + diff % 2
		else:
			hi1 = m1
			lo2 = m2 + diff % 2
		diff = hi1 - lo1
	return min(L1[lo1], L2[lo2])
主元素 定义为一个长度为 n 的数组中出现次数大于 n/2 的元素. 显然主元素如果存在, 必惟一. 求给定数组的主元素. 
# n = L.len; 时间 O(n), 空间 O(1)
# 如果 candidate 是主元素, 那么数组必能分成若干段,
# 使得 candidate 是最后一段的主元素, 且前面的每一段中 candidate
# 恰好占了半数
L.marjority_number():
	if L.len == 0:
		return None
	candidate = L[0]
	count = 1
	for i = 1 to L.len-1:
		if L[i] == candidate:
			++count
		elif count > 0:
			--count
		else:
			candidate = L[i]	# 改变候选
			count = 1			# 重新计数
	# 计数 candidate 出现次数, 确认是否是主元素
	if count > 0:
		count = 0
		for i = 0 to L.len-1:
			if L[i] == candidate:
				++count
		if count > n//2:
			return candidate
	return None
下中位数 主元素

链表

单链表

若无特别说明, 总假定链表不含头结点.

删除单链表中所有使得 f(x) == True 的值 x. 假设 f 的时空复杂度均是 O(1). 
# n = L.len; 时间 O(n), 空间 O(1)
# 用指针 p 遍历链表
L.remove_if1(f):
	Node *p = head
	if !p:
		return
	while p->next:
		if f(p->next->val):
			tmp = p->next
			p->next = tmp->next
			delete tmp
		else:
			p = p->next
按值删除

二叉树

自下而上, 从右到左遍历二叉树.

思路：设一栈. 按正常次序进行层序遍历, 结点出队后先入栈; 所有结点入栈后再依次弹出并访问.

思路1：递归

height_rec(root):
	if !root:
		return 0
	return 1+max(height_rec(root->left), height_rec(root->right))

思路2：用栈实现中序 (或后序) 遍历, 最大栈长度即为二叉树的高度. 不可用 "三位一体" 写法.

思路3：层序遍历

# 使用层序遍历, 每次获取队列长度以保证严格按行遍历.
# 空指针不可以进队列
height_nonrec(root):
	level = 0
	if root:
		queue.enqueue(root)
	while queue:
		# 如果 queue 对象没有取得长度的方法, 可设一计数变量 len
		# 随出队入队操作而变化.
		cur_len = queue.len
		loop cur_len:
			root = queue.dequeue()
			if root->left:
				queue.enqueue(root->left)
			if root->right:
				queue.enqueue(root->right)
		++level
	return level
即二叉树结点最多的那一层的结点数 
# 类似上一题. 计数层序遍历
width(root):
	max = 0
	if root:
		queue.enqueue(root)
	while queue:
		if queue.len > max:
			max = queue.len
		loop max:
			root = queue.dequeue()
			if root->left:
				queue.enqueue(root->left)
			if root->right:
				queue.enqueue(root->right)
	return max

pre[], in[] # 前序和中序序列
init_pre_in(pre_lo, pre_hi, in_lo, in_hi):
	if pre.lo <= pre.hi:
		return NULL
	root = new BinaryTreeNode(pre[pre_lo], NULL, NULL)
	i = in_lo
	while in[i] != root->val:
		++i
	left_len = i - in_lo
	right_len = in_hi - i
	if left_len > 0:
		root->left = init_pre_in(
			pre_lo+1, pre_lo+left_len, in_lo, in_lo+left_len-1)
	if right_len > 0:
		root->right = init_pre_in(
			pre_hi-right_len+1, pre_hi, in_hi-right_len+1, in_hi)
	return root

# 层序遍历, 将空结点一并入队.
# 遇到第一个空结点后, 查看队列中是否还有非空结点,
# 如果有, 说明二叉树不完全.
is_complete(root):
	if !root:
		return True
	queue.enqueue(root)
	while queue:
		root = queue.dequeue()
		if root:
			queue.enqueue(root->left)
			queue.enqueue(root->right)
		else:
			break
	while queue:
		root = queue.dequeue()
		if root:
			return False
	return True

n2(root):
	if !root:
		return 0
	return n2(root->left) + n2(root->right) +
		(root->left and root->right ? 1 : 0)

swap_left_right(root):
	if root:
		swap_left_right(root->left)
		swap_left_right(root->right)
		tmp = root->left
		root->left = root->right
		root->right = tmp

find_nth_preorder_node(root):
	cnt = 0
	stack.push(NULL)
	while root:
		++cnt
		if cnt == n:
			return root->val
		if root->right:
			stack.push(root->right)
		if root->left:
			root = root->left
		else:
			root = stack.pop()
	return 'not found'
删除二叉树中所有使得 f(x) == True 的值 x 所在的根结点的子树. 假设 f 的时空复杂度均是 O(1). 
# 按层序查找待删结点
remove_if(root, f()):
	if !root:
		return
	if f(root->val):
		remove(root) # 删除整棵树
	queue.enqueue(root)
	while queue:
		root = queue.dequeue()
		if root->left:
			if f(root->left->val):
				remove(root->left)
			else:
				queue.enqueue(root->left)
		if root->right:
			if f(root->right->val):
				remove(root->right)
			else:
				queue.enqueue(root->right)
求二叉树中某结点的所有祖先. 
# 以非递归中序 (或后序) 遍历二叉树, 每访问一个结点,
# 栈中保存的都是它的全体祖先.
ancestors(root, node):
	while True:
		if root:
			stack.push(root)
			root = root->left
		elif stack:
			root = stack.pop()
			#### visit()
			if root == node:
				while stack:
					print(stack.pop()->val)
				break
			####
			root = root->right
		else:
			break

思路1：顺序存储.

nearest_common_ancestor1(i, j):
	while i != j:
		if i > j:
			i >>= 1
		else:
			j >>= 1
	return i

思路2：在父指针树中查找最近共同祖先, 和单链表一样, 用错位同步法.

思路3：二叉链表存储

# 以非递归中序 (或后序) 遍历二叉树, 每访问一个结点,
# 栈中保存的都是它的全体祖先.
nearest_common_ancestor2(root, p1, p2):
	first = True
	while True:
		if root:
			stack.push(root)
			root = root->left
		elif stack:
			root = stack.pop()
			#### visit()
			if root == p1 or root == p2:
				if first:
					stack1 = stack.copy()
					first = False
				else:
					# 使两栈长度相等
					while stack.len > stack1.len:
						stack.pop()
					while stack1.len > stack.len:
						stack1.pop()
					# 两栈长度相等时, 比较栈顶元素
					while stack.top() != stack1.top():
						stack.pop()
						stack1.pop()
					return stack.top()
			####
			root = root->right
		else:
			break
	return 'one of node p1, p2 not found'

pre[], post[]
pre2post(pre_lo, pre_hi, post_lo, post_hi):
	if pre_hi >= pre_lo:
		# 后序的最后一个结点就是前序的第一个结点
		post[post_hi] = pre[pre_lo]
		half = (pre_hi-pre_lo) >> 1
		pre2post(pre_lo+1, pre_lo+half, post_lo, post_lo+half-1)
		pre2post(pre_lo+half+1, pre_hi, post_lo+half, post_hi-1)

# 用中序 (或前序, 后序) 遍历二叉树, 设一头结点执行连接.
# 方法类似于中序线索化
BinaryTreeNode *pre

visit(root):
	if is_leaf(root):
		pre->right = root
	pre = root

thread_leaf(root):
	pre = head = new BinaryTreeNode(?, NULL, NULL)
	traverse(root, visit) # 任一遍历方法
	# 如果不需要头结点, 可以删除之
	tmp = head
	head = head->right
	delete tmp
两棵空树相似; 空树与非空树不相似; 两棵非空二叉树相似当且仅当它们的左子树和右子树分别对应相似. 
similar(root1, root2):
	if !root1 and !root2:
		return True
	if !root1 or !root2:
		return False
	return similar(root1->left, root2->left) and
			similar(root1->right, root2->right)

# p 的后序前驱是其最后一个子结点. 若 p 是叶子结点,
# 则它是某棵树的最左下叶子结点. 先找到 p 的中序前驱  s, 若 s 有左子结点,
# 则 s->left 就是 p 的后序前驱; 否则再找 s 的中序前驱,
# 直到 s 有左子结点, 或者 s 无中序前驱为止.
post_prev(root, node):
	if !node->right_thread: # 有右子结点
		return node->right
	if !node->left_thread: # 有左子结点
		return node->left
	while node->left_thread and node->left: # 有中序前驱
		node = node->left
	if !node->left_thread # 有左子结点
		return node->left
	else: # 无中序前驱
		return NULL

# 递归算法
wpl = 0
WPL(root, depth):
	if root:
		if is_leaf(root):
			wpl += root->weight * depth
		else:
			WPL(root->left, depth+1)
			WPL(root->right, depth+1)

# 又一递归算法, 注意 WPL 等于分支结点权和.
wpl = 0
weight(root):
	if !root:
		return 0
	if is_leaf(root):
		return root->weight
	w = weight(root->left) + weight(root->right)
	wpl += w
	return w

# 层序遍历
WPL_levelorder(root):
	wpl = 0
	depth = 0
	if root:
		queue.enqueue(root)
	while queue:
		cur_len = queue.len
		loop cur_len:
			root = queue.dequeue()
			if is_leaf(root):
				wpl += root->weight * depth
			if root->left:
				queue.enqueue(root->left)
			if root->right:
				queue.enqueue(root->right)
			++depth
	return wpl
不考虑运算符优先级, 统统加括号. 最外层不加括号. 
inorder_expr(root):
	if root:
		if if_leaf(root):
			print(root->val)
		else:
			do_inorder_expr(root->left)
			print(root->val)
			do_inorder_expr(root->right)

do_inorder_expr(root):
	if root:
		if is_leaf(root):
			print(root->val)
		else:
			print('(')
			inorder_expr(root->left)
			print(root->val)
			inorder_expr(root->right)
			print(')')
反向层序遍历 求二叉树高度 求二叉树宽度 由前序序列和中序序列确定二叉树 判断二叉树是否是完全二叉树 求二叉树的 2 度结点数 交换二叉树的左右子树 查找前序序列的第 n 个结点 按值删除 求所有祖先 查找两结点的最近共同祖先 给定满二叉树的前序序列, 求后序序列 将叶结点以 right 指针连成单链表 判断二叉树相似 在中序线索二叉树中寻找后序前驱 求带权路径长度 由表达式树求中缀表达式

树和森林

count_leaves(root):
	if !root:
		return 0
	elif !root->first_child:
		return 1 + count_leaves(root->next_sibling)
	return count_leaves(root->first_child)
		+ count_leaves(root->next_sibling)

height(root):
	if !root:
		return 0
	return max(1+height(root->first_child),
		height(root->next_sibling))

init_levelorder_deg(val[], deg[], n):
	nodes = new TreeNode[n](val[i], NULL, NULL)
	j = 0
	for i = 0 to n-1:
		d = deg[i]
		if d--:
			nodes[i]->first_child = nodes[++j]
			while d--:
				nodes[j]->next_sibling = nodes[j+1]
				++j
	return nodes[0]
来自群友的变态图论问题: 有向图中有 4 个节点, 女节点入度小于等于2, 出度为0; 男节点入度为 0, 出度为1; futa节点入度小于等于 2, 出度小于等于1; 男娘节点入度小于等于 1, 出度小于等于1. 要求不存在孤立点, 这样的图有多少个? 假如区分 2 个洞, 这样的图又有多少个? 
# 没有区分两个洞时, 答案是 12, 区分时答案是 40
import numpy as np

count = 0
for n in range(2**16):
    bits = [int(d) for d in format(n, 'b').rjust(16, '0')]
    a = np.array(bits).reshape((4, 4))
    # 不可自指
    if any(a[i][i] == 1 for i in range(4)):
        continue
    row_sum = a.sum(axis=0) # 出度
    col_sum = a.sum(axis=1) # 入度
    # 无孤立点
    if any(row_sum[i] == 0 and col_sum[i] == 0 for i in range(4)):
        continue
    # 女节点
    if col_sum[0] > 2 or row_sum[0] > 0:
        continue
    # 男节点
    if col_sum[1] > 0 or row_sum[1] != 1:
        continue
    # futa 节点
    if col_sum[2] > 2 or row_sum[2] > 1:
        continue
    # 男娘节点
    if col_sum[3] > 1 or row_sum[3] > 1:
        continue
    #print(a)
    add = 1
    # 区分女节点的两个洞
    if col_sum[0] > 1:
        add *= 2
    # 区分 futa 节点的两个洞
    if col_sum[2] > 1:
        add *= 2
    count += add

print(count)
森林的叶结点数 森林的高度 利用森林的层序序列和每个结点的度数建立森林 本子问题

杂例

思路: 保存并维护每个点的偶数最短路与奇数最短路. 
# palindromes(n, 1) 返回 n 位的回文数
def palindromes(n, start):
    if n == 1:
        return [i for i in range(10)]
    if n == 2:
        return [11*i for i in range(start, 10)]
    return [i*10**(n-1) + 10*k + i for i in range(start, 10) for k in palindromes(n-2, 0)]
[来自CDSN] 将 1 到 n 的全排列按字典序列出, 比如 1 到 4 的全排列是: 
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...
4 3 2 1
问题: 给定一个排列, 求它在列表中的第几位. 反之, 给定它在列表中的位次, 求这个排列. 
# 对于一个排列, 如 2 4 1 3, 它是以 2 开头的, 所以前面还有以 1 开头的 3! 个排列,
# 故 num += 6. 再看它的后三位是由 {4, 1, 3} 的排列组成的,
# 前面还有以 1 开头和以 3 开头的 2 * 2! = 4 个排列, 故 num += 4.
# 再看它的后两位是由 {1, 3} 的排列组成的, 1 已经是最小的数字,
# 前面没有其它排列, 故 num += 0. 最后由于列表的位次是从 1 开始的, 因此再给 num 加 1,
# 得到 num = 6 + 4 + 1 = 11.
def perm2num(arr):
    n = len(arr)
    num = 0
    perms = 1
    for i in range(n-2, -1, -1):
        num += sum(perms for j in range(i+1, n) if arr[j] < arr[i])
        perms *= n - i # perms = (n-i)! 是 arr[i+1:n] 的排列数
    return num + 1

def num2perm(n, num):
    arr = []
    candidate = [i+1 for i in range(n)] # 待插入的数
    perms = math.factorial(n)
    for i in range(n):
        perms //= n-i
        index = (num - 1) // perms
        num -= index * perms
        arr.append(candidate.pop(index))
    return arr
[来自群友 Eyelids] 给定 `n`, `S` 是全体 `n` 维 01 向量的子集，满足 `S` 中任两个元素的距离 `≥3`，`|S|` 的最大值是？ （距离就是两个向量相减后非零分量的个数） 
# 答案：https://oeis.org/A054243
# 这题本质是计算距离 = 3 的汉明码序列 https://oeis.org/A075926

buf = []
best = 0

def dist(a, b):
    res = 0
    n = a ^ b
    while n:
        res += 1
        n &= n - 1 # 消去最右边的一个 1
    return res

def dfs(n):
    global best
    if len(buf) > best:
        best = len(buf)
    for i in range(0, n):
        if all(dist(i, j) >= 3 for j in buf):
            buf.append(i)
            dfs(n)
            return

def search(n):
    global best
    best = 0
    buf.clear()
    buf.append(0)
    dfs(n)
    print(best, buf)

def check_answer(l):
    print([dist(a, b) for a in l for b in l if a != b])


search(2**7)
5个人过河，他们分别是妈妈、爸爸、哥哥、妹妹、路人。 妈妈是魅魔单独与男性时会对男性进行侵犯； 爸爸是鬼父单独与妹妹时会进行性行为； 哥哥是德国骨科与妹妹单独时会进行性行为； 妹妹也是德国骨科单独跟哥哥时会进行性行为，但妹妹身体弱不能开船； 路人是基佬单独与哥哥时会进行侵犯； 只有一艘船，每次只能坐两个人，船不会自己回来，过去就要有人开回来； 如何在不发生任何性行为的情况下，5个人成功到对面？ 
danger = [0b11000, 0b10100, 0b10001, 0b01010, 0b00110, 0b00101]
available_moves = [0b10000, 0b01000, 0b00100, 0b00001, 0b10010, 0b01100, 0b01001, 0b00011]
all_people = 0b11111
people = all_people
max_len = 7

def explain(v):
    buf = []
    if v & 0b10000:
        buf.append('妈妈')
    if v & 0b01000:
        buf.append('爸爸')
    if v & 0b00100:
        buf.append('哥哥')
    if v & 0b00010:
        buf.append('妹妹')
    if v & 0b00001:
        buf.append('路人')
    return ','.join(buf)

def solution():
    global people
    people = all_people
    moves = []
    def dfs(depth):
        global people
        if depth > max_len:
            return
        if people == 0:
            return print([explain(v) for v in moves])
        for move in available_moves:
            if len(moves) > 0 and move == moves[-1]:
                continue
            boat_here = len(moves) % 2 == 0
            if boat_here and (people & move == move):
                people ^= move
                if (people not in danger) and (all_people ^ people not in danger):
                    moves.append(move)
                    dfs(depth + 1)
                    moves.pop()
                people ^= move
            if not boat_here and ((all_people ^ people) & move == move):
                people ^= move
                if (people not in danger) and (all_people ^ people not in danger):
                    moves.append(move)
                    dfs(depth + 1)
                    moves.pop()
                people ^= move
    dfs(0)

solution()

2018 刑侦科推理试题

  1. 这道题的答案是：
    A. A B. B C. C D. D
  2. 第5题的答案是：
    A. C B. D C. A D. B
  3. 以下选项中哪一题的答案与其他三项不同：
    A. 第3题 B. 第6题 C. 第2题 D. 第4题
  4. 以下选项中哪两题的答案相同：
    A. 第1,5题 B. 第2,7题 C. 第1,9题 D. 第6,10题
  5. 以下选项中哪一题的答案与本题相同：
    A. 第8题 B. 第4题 C. 第9题 D. 第7题
  6. 以下选项中哪两题的答案与第8题相同：
    A. 第2,4题 B. 第1,6题 C. 第3,10题 D. 第5,9题
  7. 在此十道题中，被选中次数最少的选项字母为：
    A. C B. B C. A D. D
  8. 以下选项中哪一题的答案与第1题的答案在字母中不相邻：
    A. 第7题 B. 第5题 C. 第2题 D. 第10题
  9. 已知“第1题与第6题的答案相同”与“第X题与第5题的答案相同”的真假性相反，那么X为：
    A. 第6题 B. 第10题 C. 第2题 D. 第9题
  10. 在此10道题中，ABCD四个字母出现次数最多与最少者的差为：
    A. 3 B. 2 C. 4 D. 1
这是 2-sat 问题吗？ 
from itertools import product

for b in product(range(4), repeat=10):
    # 2.
    if b[4] != (2, 3, 0, 1)[b[1]]:
        continue
    # 3.
    t = (b[2], b[5], b[1], b[3])
    if t.count(t[b[2]]) > 1:
        continue
    # 4.
    x, y = ((0, 4), (1, 6), (0, 8), (5, 9))[b[3]]
    if b[x] != b[y]:
        continue
    # 5.
    if b[4] != b[(7, 3, 8, 6)[b[4]]]:
        continue
    # 6.
    x, y = ((1, 3), (0, 5), (2, 9), (4, 8))[b[5]]
    if b[7] != b[x] or b[7] != b[y]:
        continue
    # 7.
    counts = tuple(b.count(x) for x in range(4))
    minCounts = min(counts)
    if counts[(2, 1, 0, 3)[b[6]]] != minCounts:
        continue
    # 8.
    if abs(b[(6, 4, 1, 9)[b[7]]]-b[0]) < 1:
        continue
    # 9.
    flag1 = b[0] == b[5]
    flag2 = b[(5, 9, 1, 8)[b[8]]] == b[4]
    if flag1 == flag2:
        continue
    # 10.
    maxCounts = max(counts)
    diff = maxCounts - minCounts
    if diff != (3, 2, 4, 1)[b[9]]:
        continue
    print(''.join(chr(65+x) for x in b)) # BCACACDABA
求长度为奇数的最短路 求所有 n 位回文数 Cantor 展开 Hamming 距离 过河问题 刑侦推理试题