1. 题目

传送门= ̄ω ̄=

2. 题解

很显然是高斯消元解异或方程组。

因为$\mod 2$意义下的加法等同于异或。

消元的时候记录一下最大访问到方程组的哪一行,这个就是“到多少行确定答案”。

其他就没什么了。无解就是消着消着某一列都变成0了(除了之前已经访问过的行),则答案不唯一。

另外就是$2000 \times 1000 ^ 2$的复杂度过不了,需要用bitset压位,复杂度降到$\frac {2000 \times 1000 ^ 2} {32} = 6.25 \times 10 ^ 7$,就能过了。

代码:

#include <bits/stdc++.h>

#define NS (1005)
#define MS (2005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, ans, res[NS];

bitset<NS> h[MS];

char str[NS];

void GS()
{
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = i; j <= m; j += 1)
            if (h[j][i])
            {
                ans = max(ans, j);
                if (i != j) swap(h[i], h[j]);
                break;
            }
        if (!h[i][i]) puts("Cannot Determine"), exit(0);
        for (int j = i + 1; j <= m; j += 1)
            if (h[j][i]) h[j] ^= h[i];
    }
    for (int i = n; i >= 1; i -= 1)
    {
        res[i] = h[i][n + 1];
        for (int j = i + 1; j <= n; j += 1)
            if (h[i][j]) res[i] ^= res[j];
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= m; i += 1)
    {
        scanf("%s", str + 1);
        for (int j = 1; j <= n; j += 1) if (str[j] == '1') h[i].set(j, 1);
        scanf("%s", str);
        if (str[0] == '1') h[i].set(n + 1, 1);
    }
    GS(), printf("%d\n", ans);
    for (int i = 1; i <= n; i += 1)
        if (res[i]) puts("?y7M#");
        else puts("Earth");
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *