DigitalCircuit

本关是一个由不同逻辑门（可能包含与非门、异或门等）构成的数字电路，包含 4 个输入端和 8 个输出端，初始输出为 00000000。

你需要通过合理输入，使得此电路能够输出 11111111。

本关的情况有点出乎意料，因为很多人过关不是依靠真的把题解出来，而是「一不小心碰出全 1 然后就通关了」，可见题目的复杂度还有待提升。我的预期好歹也是大家要测测电路，找找规律才行。

解析

这道题对于没学过数电的人来说并不友好，因为它不是一个简单的组合逻辑电路。在组合逻辑电路中，由确定的输入只会得出确定的输出。但在本题，你只要连续使用同样的输入来观测输出，就会发现输出结果是变化的。所以说，这个电路很有可能是时序逻辑电路。

具体的找规律过程就不提了，我直接说结果。

设输入为 $a_{3} a_{2} a_{1} a_{0}$ ，上一轮的输出为 $b_{7} b_{6} b_{5} b_{4} b_{3} b_{2} b_{1}$ ，本轮输出为 $c_{7} c_{6} c_{5} c_{4} c_{3} c_{2} c_{1}$ ，那么：

$c_{7} c_{5} c_{3} c_{1}$ 就等于你的输入，也就是说

$c_{7} = a_{3} c_{5} = a_{2} c_{3} = a_{1} c_{1} = a_{0}$

$c_{6}$ 只有在「本次输入与上次输入（上次输入的结果间接记录在了上次输出当中）完全相反」时，才会得到 1；否则得到 0。

$c_{4} c_{2}$ 组成二位计数器，也就是说

$c_{4} = b_{4} \oplus b_{2} c_{2} = \neg b_{2}$

$c_{0}$ 则等于所有输入 $a_{k}$ 、输出 $b_{k}$ 的异或和。

以下 C++ 代码可以实现由输入和上次输出推算本次输出。

std::array<bool,preset::OutputNum> operate::signal(std::array<bool,preset::InputNum> &input,std::array<bool,preset::OutputNum> &output){
	std::array<bool,preset::OutputNum> result;
	//result[7,5,3,1]记录了本次的输入
	result[7]=input[3];
	result[5]=input[2];
	result[3]=input[1];
	result[1]=input[0];
	//result[6]只有在「本次输入与上次输入完全相反」时，才会得到true
	result[6]=input[3]^output[7]&&input[2]^output[5]&&input[1]^output[3]&&input[0]^output[1];
	//result[4,2]组成二位计数器
	result[4]=output[4]^output[2];
	result[2]=!output[2];
	//result[0]等于所有输入、输出的异或和
	result[0]=false;
	for(int i=0;i<preset::InputNum;i++)
		result[0]^=input[i];
	for(int i=0;i<preset::OutputNum;i++)
		result[0]^=output[i];
	return result;
}

回到我们的问题。我们的初始状态是 00000000，而我们希望到达全 11111111，这其实就是一个在有向图上寻找路径的问题，那么无论做广度优先搜索还是求最短路都是可行的。

人工推导

当然，这题不编程也完全可以做，我们试着寻找一下思路：

就像走迷宫那样，有的时候从终点开始要比从起点开始更加容易。

要想达到 11111111，最后一步的输入必定要是 1111，因为输出当中就有四位数等于输入。

而我们又要保证 $c_{6}$ 等于 1，那么前一次的输入必须是 0000 才行。

同时， $c_{4} c_{2}$ 构成二位计数器，也就是说，在前一回合，它们的输出将是 $10$ 。

接下来的流程也可以照猫画虎地做，不过分岔会越来越多，很难逐个分析；因此我建议能编程的玩家还是试试编程求解一下。

编程求解

我们可以运用图论的知识建立一个有向图 $G (V, E)$ ，图上的点表示「输出的结果」，图中共有 $2^{8} = 256$ 个点；边表示「经过一次输入，某个状态可以转移成另一个状态」，图中共有 $2^{1} 2 = 4096$ 条边。

我们还可以推断出这个图的一些特征，例如：因为有两位计数器每回合都会发生变化，所以任何一个状态在经历一次输入之后不可能返回它自身，因而 $G$ 中没有自环。（当然这是题外话了）

接下来就可以在图上搜索或者求最短路。我用的是 Floyd 算法。

#include<array>
#include<limits>
#include"operate.hpp"
#include"preset.hpp"
void operate::floyd(
	std::array<std::array<int,1<<preset::OutputNum>,1<<preset::OutputNum> &dist,
	std::array<std::array<int,1<<preset::OutputNum>,1<<preset::OutputNum> &prev
){
	for(int o=0;o<1<<preset::OutputNum;o++)
		for(int r=0;r<1<<preset::OutputNum;r++){
			dist[o][r]=std::numeric_limits<int>::max()/2;
			prev[o][r]=-1;
		}
	for(int o=0;o<1<<preset::OutputNum;o++){
		dist[o][o]=0;
		prev[o][o]=o;
		std::array<bool,preset::OutputNum> output;
		for(int d=0;d<preset::OutputNum;d++)
			output[d]=o&1<<d;
		for(int i=0;i<1<<preset::InputNum;i++){
			std::array<bool,preset::InputNum> input;
			for(int d=0;d<preset::InputNum;d++)
				input[d]=i&1<<d;
			std::array<bool,preset::OutputNum> result{operate::signal(input,output)};
			int r{0};
			for(int d=0;d<preset::OutputNum;d++)
				if(result[d])
					r+=1<<d;
			dist[o][r]=1;
			prev[o][r]=o;
		}
	}
	for(int k=0;k<1<<preset::OutputNum;k++)
		for(int i=0;i<1<<preset::OutputNum;i++)
			for(int j=0;j<1<<preset::OutputNum;j++)
				if(dist[i][j]>dist[i][k]+dist[k][j]){
					dist[i][j]=dist[i][k]+dist[k][j];
					prev[i][j]=prev[k][j];
				}
}

Floyd 算法应该是这里面最麻烦的了，不过我有不得不用的理由——那就是分析整个图的性质。

不过这些内容就是出题时需要考虑的了，如果我有空的话，之后会对此做进一步说明。

解谜末班车

DigitalCircuit

解析

人工推导

编程求解