洛谷 题解 P2117 【小Z的矩阵】

这题这么无聊，亏我还用了读入输出优化。。。

关键在于，这还是道黄题QWQ

掀桌而起 (╯‵□′)╯︵┻━┻

显而易见，在i != j的情况下，a[i][j] + a[j][i]和a[j][i] + a[i][j]都会被记录到，so (a[i][j] * a[j][i]) + (a[j][i] * a[i][j]) mod 2对答案毫无影响。

在i = j的情况下，a[i][j] + a[j][i]就是a[j][i] + a[i][j]，而且只会记录一次，so a[i][j] * a[j][i] mod 2对答案的影响即为a[i][i]本身(1 * 1 = 1, 0 * 0 = 0)。

先上读入代码：

int n = readint(), q = readint(); // n, q即为题目中的含义，"readint()"是我自己写的读入优化函数
bool ans = false; // 因为是要"mod 2", 所以一个bool变量就够了
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (i == j) {
            if (readint()) ans = !ans; // i = j, 且值为1，则对答案有“1”的影响
        }
        else readint(); // i != j, 对答案无影响
    }
}

那么后面的q个操作，可以这样看：

因为当操作值为1 or 2时，翻转了1列或1行，所以只对对角线有一次的影响，则对答案有“1”的影响

if (readint() == 3) writeint(ans); //输出
else readint(), ans = !ans; //操作值为1 or 2

完整代码：

#include <stdio.h>
#define Char_Int(a) ((a) - '0')
#define Int_Char(a) ((a) + '0')

int readint();
int writeint(int);

int main()
{
    int n = readint(), q = readint();
    bool ans = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                if (readint()) ans = !ans;
            }
            else readint();
        }
    }
    for (int i = 0; i < q; i++) {
        if (readint() == 3) writeint(ans);
        else readint(), ans = !ans;
    }
}

inline int readint()       
{
    char c = getchar();
    while (c > '9' || c < '0') c = getchar();
    int init = Char_Int(c);
    while ((c = getchar()) <= '9' && c >= '0') init = (init << 3) + (init << 1) + Char_Int(c);
    return init;
}

inline int writeint(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) writeint(x / 10);
    putchar(Int_Char(x % 10));
    return x; 
}