P2447题解

· · 题解

吐槽一句：SDOI2010 真的魔幻……共计 12 题，上能外星捉虫，下能帮猪打牌（逃

Step1 审题 + 题意转化

由于“昆虫点足机”返回的是虫子腿总数 \text{mod}\ 2 的值，又考虑到昆虫腿数仅有奇偶的差异，不妨令地球虫子的腿数为 0，外星虫子的腿数为 1（因为这样不会影响结果）。那么问题就可以转化为求解如下方程组：

\begin{cases} \sum\limits_{i=1}^na_{1,i}\cdot x_i&=b_1 \pmod 2&&(1)\\ \sum\limits_{i=1}^na_{2,i}\cdot x_i&=b_2 \pmod 2&&(2)\\ \cdots&\cdots&&\cdots\\ \sum\limits_{i=1}^na_{m,i}\cdot x_i&=b_m \pmod 2&&(m) \end{cases}

其中 a_{i,j} 表示输入的第 i 次测量是否将第 j 条虫放入机器（放入为 1，未放入为 0），b_i 表示第 i 次测量的结果。

考虑到在正整数的情况下，模 2 可以转化为取二进制下的最低位，那么方程组的等号右边只会用到左边的最低位，所以我们对于方程组的左边可以不考虑高位，只考虑低位。既然不需要考虑高位，我们就可以采用异或（二进制下的不进位加法），将上面的方程组转化为“异或同余方程组”（我自己起的名字）：

\begin{cases} a_{1,1}x_1 \operatorname{xor} a_{1,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{1,n}x_n &\equiv b_1 \pmod 2&&(1)\\ a_{2,1}x_1 \operatorname{xor} a_{2,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{2,n}x_n&\equiv b_2 \pmod 2&&(2)\\ \cdots&\cdots&&\cdots\\ a_{m,1}x_1 \operatorname{xor} a_{m,2}x_2\operatorname{xor}\cdots\operatorname{xor}a_{m,n}x_n&\equiv b_m \pmod 2&&(m) \end{cases}

众所周知， 同余方程组一般情况下比较棘手，那么我们有没有可能将她转化为普通的方程组呢？我们知道，这里的每一条方程中所有参数（如 a_{i,j} 与 b_i）均在 \{0,1\} 中，且我们上面也令了 x_i\in\{0,1\}。由于异或运算的特性，每条方程的“\equiv”左右两边在二进制表示下均仅含一位（即最低位）；而我们的模 2 运算也可以转化为取最低位的运算（奇数低位为 1，偶数低位为 0）。所以我们就可以把这个同余方程组转化为普通的异或方程组了！

总而言之，我们就成功的将题意转化为了：

  1. 求解异或方程组
  2. 输出最少用的方程数

（另外多嘴说一句：为什么要转化为异或方程组呢？因为这样我们就可以用 C++ 中的 std::bitset 与一些二进制优化的方法极大地减小我们的常数 （简称高级卡常），甚至可以做到 \text{TLE}\to\text{AC}！）

Step2 解题思路

转化为异或方程组之后我们又能对她进行什么操作呢？我们知道，异或运算是符合交换律和结合律，所以可以使用类似高斯消元法的方法解决这个异或方程组。具体来说，我们可以在每一次选取一条方程消元时将方程间的加减消元改为异或消元，并且由于 \forall i\in\mathbb{Z}\cap[1,m],j\in\mathbb{Z}\cap[1,n]，有 a_{i,j}\in\{0,1\}，所以我们在消元的时候可以不用对方程进行乘除操作，直接异或就可以了！当然，在消元过程中如果碰到了多解的情况，记得输出 \texttt{Cannot Determine}！

解决了如何求解这个方程组，接下来我们就要解决如何求出最少的方程使用数。实际上，我们可以在每一次消元寻找该元系数非零时找一个编号最小的（即输入顺序最靠前的），然后更新答案取最大值。

分析一下复杂度。首先空间复杂度自然是存增广矩阵的复杂度 O(nm)。而时间复杂度有点奇怪：裸的高斯消元显然是 O(n^2m) 的，明显无法通过此题。

考虑一下用 std::bitset 优化大常数。我们知道 bitset 的异或操作是 O(\dfrac n\omega) 的，那么用一个 bitset 数组来表示增广矩阵，总的时间复杂度就是 O(\dfrac{n^2m}\omega)。稍微计算一下， 在 n=10^3 且 m=2\times 10^3，评测机为 32 位（即 \omega=32）且数据为最坏情况时，式中的\dfrac{n^2m}\omega\leq 7\times10^7，完全可以通过此题。

Step3 码

嗯？你为什么露出这么期待的表情？

那么有了思路就可以开始写代码了。实际上此题对码力的要求并没有看猪打牌这一题这么高，有了思路基本就可以写出来了。

AC 代码：

#include <iostream> 
#include <cstdio> 
#include <bitset>
#include <cctype>
// 使用宏定义使程序更清晰（虽然也没有清晰多少）
#define ALIEN "?y7M#"
#define EARTH "Earth"
char buffer[1010];
std::bitset<1010> matrix[2010]; // matrix[1~n]：增广矩阵，0 位置为常数
int GaussElimination(int n, int m) // n 为未知数个数，m 为方程个数，返回 0 表示多解，否则返回最少用到的方程数 
{
    int ans = -1; // 方程使用数
    for (int i = 1; i <= n; i++) // 循环消去第 i 个元
    {
        int cur = i;
        while (cur <= m && !matrix[cur].test(i))
            cur++;
        if (cur > m) // 第 i 个元的所有系数均为 0，有多解
            return 0;
        ans = std::max(ans, cur); // 更新 ans
        if (cur != i)
            swap(matrix[cur], matrix[i]); // 交换方程
        for (int j = 1; j <= m; j++)
            if (i != j && matrix[j].test(i)) // 可以消元
                matrix[j] ^= matrix[i];     // 异或消元
    }
    return ans;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, res; i <= m; i++)
    {
        scanf("%s%d", buffer, &res);
        for (int j = 0; j < n; j++)
            matrix[i].set(j + 1, buffer[j] == '1'); // 增广矩阵赋值系数
        matrix[i].set(0, res); // 常数
    }
    int ret = GaussElimination(n, m); // 高斯消元
    if (ret)
    {
        printf("%d\n", ret);
        for (int i = 1; i <= n; i++)
            printf("%s\n", matrix[i].test(0) ? ALIEN : EARTH);
    }
    else printf("Cannot Determine\n");
    return 0;
}