zrj2012-A3-0003

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意是说给出K（《20000）个N（《30）位的01串，这些串通过相互异或（注意：是任意数量的串异或，我在考试时看成任意2个串异或），构成一个集合。
然后输入M个串，问你这M个串，每个串至多可以改变3位（0变1,1变0），问每个串十分能够属于这个集合，如果能，输出在改变位数最少的情况下字典序最小的。
这题乍看之下K很大，但是实际上，由于是异或操作，这K个串许多是可以相互表示的，事实上，我们可以用至多N个串来表示着K个串，并且这些串相互异或可以还原K个串构成的集合。
因此实现用N^2*K的复杂度进行类似高斯消元的位运算，得到这个集合的一组基（s1,s2...sr)，一般，为了方便之后的计算，我们可以将这r个串化成类似上三角矩阵的形式，即每个串，都存在一位，只有它在这一位是1，其他串在这一位都是0，这样，当我们要判断一个串是否属于那个集合（即可由这一组基构成）时，只需要依次序，把这r个串特有的r个位置上的1消去，看看此时这个串是否恰好等于0即可。这个复杂度是o(n)的。
最后稍微麻烦一点的是，需要枚举一下改变1~3位的情况

题意是说给出K（《20000）个N（《30）位的01串，这些串通过相互异或（注意：是任意数量的串异或，我在考试时看成任意2个串异或），构成一个集合。

然后输入M个串，问你这M个串，每个串至多可以改变3位（0变1,1变0），问每个串十分能够属于这个集合，如果能，输出在改变位数最少的情况下字典序最小的。

这题乍看之下K很大，但是实际上，由于是异或操作，这K个串许多是可以相互表示的，事实上，我们可以用至多N个串来表示着K个串，并且这些串相互异或可以还原K个串构成的集合。

因此实现用N^2*K的复杂度进行类似高斯消元的位运算，得到这个集合的一组基（s1,s2...sr)，一般，为了方便之后的计算，我们可以将这r个串化成类似上三角矩阵的形式，即每个串，都存在一位，只有它在这一位是1，其他串在这一位都是0，这样，当我们要判断一个串是否属于那个集合（即可由这一组基构成）时，只需要依次序，把这r个串特有的r个位置上的1消去，看看此时这个串是否恰好等于0即可。这个复杂度是o(n)的。

最后稍微麻烦一点的是，需要枚举一下改变1~3位的情况