TheDevice
作者：谢兴宇
关键词：位运算
简要题意
你有n个盘子，每个盘子是一个长为m的01串。你还有一台机器，你需要用两个盘子作为它的输入，然后它会在屏幕上输出一个长为m的01串。输出的每一位是对两个盘子的对应位的and,or,xor三种运算中的一种的结果。你需要确定机器在每一位上究竟会做何种运算。
你可以用这n个盘子的任意一对来测试这台机器，但是你可能依然不能确定某一位机器究竟是做的何种运算。所以请计算出确定机器的每一位上做的是哪种运算最少还需要几个盘子？
算法
显然每一位都是独立的，答案就是每一位需要的盘子数量的最大值。
我们考虑每一位还需要的盘子数量。区分and和or，需要0和1,0 and 1=0,0 or 1=1；区分and和xor，也需要0和1，0 and 1=0,0 xor 1=1；区分or和xor，需要1和1,1 xor 1=0,1 or 1=1.所以每一位至少需要1个0，2个1.所以这一位还需要的盘子数量就是max(2-这一位是1的盘子数量，0）+max（1-这一位是0的盘子数量）。