Chlience

【题解】SPOJ JZPLIT - Turn on the lights
Problem给定一个 $n*m$ 的矩阵,每个格子是白色或者黑色,每次可以选择一个格子使得行列反色(黑变白,白变...
扫描右侧二维码阅读全文
28
2019/01

【题解】SPOJ JZPLIT - Turn on the lights

Problem

给定一个 $n*m$ 的矩阵,每个格子是白色或者黑色,每次可以选择一个格子使得行列反色(黑变白,白变黑),求需要选择哪些格子使其全部变白

Thought

首先一个比较奇妙的性质:

$$ a_{x,y}\oplus a_{x+1,y} \oplus a_{x,y+1} \oplus a_{x+1,y+1} \oplus X_{x,y}\oplus X_{x+1,y} \oplus X_{x,y+1} \oplus X_{x+1,y+1}=0 $$

其中, $a_{x,y}$ 表示原格子, $X_{i,j}$ 表示是否选择该格子进行反色

当然,这个方程亦可以扩展到这样的形式

$$ a_{x,y}\oplus a_{x+c,y} \oplus a_{x,y+d} \oplus a_{x+c,y+d} \oplus X_{x,y}\oplus X_{x+c,y} \oplus X_{x,y+d} \oplus X_{x+c,y+d}=0 $$

比较简单,请自行证明

有了这个式子之后,我们就可以用在第一行第一列上的点来表示所有点,即

$$ X_{i,j}=a_{1,1} \oplus a_{i,1} \oplus a_{1,j} \oplus a_{i,j} \oplus X_{1,1} \oplus X_{i,1} \oplus X_{1,j} $$

那么再将第一行第一列的每个点用其他点表示出来,进行高斯消元即可

手写bitset过不了也不知道为啥...难受的很,随随便便就被卡掉了...

Code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 1010;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
struct Bitset {//手写了但是并没有用
    ull num[35];
    bool operator [] (int pos) {
        return num[pos / 63] & (1ull << (pos % 63));
    }
    void flip(int pos) {
        num[pos / 63] ^= (1ull << (pos % 63));
    }
    void flip() {
        for(int i = 0; i < 35; ++ i)
            num[i] = ~ num[i];
    }
    void set(int pos) {
        num[pos / 63] |= (1ull << (pos % 63));
    }
    void set() {
        for(int i = 0; i < 35; ++ i)
            num[i] = ~ 0ull;
    }
    void reset(int pos) {
        num[pos / 63] &= ~(1ull << (pos % 63));
    }
    void reset() {
        for(int i = 0; i < 35; ++ i)
            num[i] = 0ull;
    }
    void build(char* str) {
        reset();
        int len = strlen(str);
        for(int i = 0 ; i < len; ++ i)
            if(str[len - i - 1] == '1')
                flip(i);
    }
    bool operator < (const Bitset a) {
        for(int i = 34; i >= 0; -- i)
            if(num[i] != a.num[i])
                return num[i] < a.num[i];
        return 0;
    }
    bool operator > (const Bitset a) {
        for(int i = 34; i >= 0; -- i)
            if(num[i] != a.num[i])
                return num[i] > a.num[i];
        return 0;
    }
    bool operator == (const Bitset a) {
        for(int i = 0; i < 35; ++ i)
            if(num[i] != a.num[i])
                return 0;
        return 1;
    }
    Bitset operator ^ (const Bitset a) {
        Bitset ans; ans.reset();
        for(int i = 0; i < 35; ++ i)
            ans.num[i] = num[i] ^ a.num[i];
        return ans;
    }
    Bitset operator & (const Bitset a) {
        Bitset ans; ans.reset();
        for(int i = 0; i < 35; ++ i)
            ans.num[i] = num[i] & a.num[i];
        return ans;
    }
    Bitset operator | (const Bitset a) {
        Bitset ans; ans.reset();
        for(int i = 0; i < 35; ++ i)
            ans.num[i] = num[i] | a.num[i];
        return ans;
    }
    void operator ^= (const Bitset a) {
        for(int i = 0; i < 35; ++ i)
            num[i] ^= a.num[i];
    }
    void operator &= (const Bitset a) {
        for(int i = 0; i < 35; ++ i)
            num[i] &= a.num[i];
    }
    void operator |= (const Bitset a) {
        for(int i = 0; i < 35; ++ i)
            num[i] |= a.num[i];
    }
};
void print(Bitset a) {
    int end = 0;
    for(int i = N - 1 ; i >= 0 && !end; -- i)
        if(a[i])
            end = i;
    for(int i = 1; i <= end; ++ i)
        putchar(a[i] ? '1' : '0');
    puts("");
}
//Bitset l[N], h[N], g[N << 1];
bitset <2020> l[N], h[N], g[N << 1];
int n, m;
bool a[N][N];
bool b[N][N];
char s[N];

void guess() {
    for(int i = 1; i < n + m; ++ i) {
        int now = 0;
        for(int j = i; j < n + m; ++ j)
            if(g[j][i]) {
                now = j;
                if(now != i)
                    swap(g[i], g[now]);
                break;
            }
        if(!now) continue;
        for(int j = i + 1; j < n + m; ++ j)
            if(g[j][i])
                g[j] ^= g[i];
    }
    for(int i = n + m - 1; i; -- i)
        for(int j = i + 1; j < n + m; ++ j)    
            if(g[i][j] && g[j][n + m])
                g[i].flip(n + m);
}
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        for(int j = 1; j <= m; ++ j)
            a[i][j] = s[j] - '0';
    }
    l[1].flip(1);
    for(int i = 2; i <= n; ++ i)
        l[1].flip(m + i - 1);
    for(int j = 2; j <= m; ++ j) {
        if(n % 2) {
            l[j].flip(j);
            l[j].flip(1);
        }
        bool Flip = 0;
        for(int i = 2; i <= n; ++ i)
            Flip ^= a[1][1] ^ a[i][1] ^ a[1][j] ^ a[i][j];
        l[j] ^= l[1];
        if(Flip) l[j].flip(n + m);;
    }

    h[1].flip(1);
    for(int j = 2; j <= m; ++ j)
        h[1].flip(j);
    for(int i = 2; i <= n; ++ i) {
        if(m % 2) {
            h[i].flip(m + i - 1);
            h[i].flip(1);
        }
        bool Flip = 0;
        for(int j = 2; j <= m; ++ j)
            Flip ^= a[1][1] ^ a[i][1] ^ a[1][j] ^ a[i][j];
        h[i] ^= h[1];
        if(Flip) h[i].flip(n + m);
    }

    g[1] = h[1] ^ l[1];
    g[1].flip(1);
    if(a[1][1])
        g[1].flip(n + m);
    for(int i = 2; i <= n; ++ i) {
        g[m + i - 1] = h[i] ^ l[1];
        g[m + i - 1].flip(m + i - 1);
        if(a[i][1])
            g[m + i - 1].flip(n + m);
    }
    for(int j = 2; j <= m; ++ j) {
        g[j] = h[1] ^ l[j];
        g[j].flip(j);
        if(a[1][j])
            g[j].flip(n + m);
    }
    guess();
    b[1][1] = g[1][n + m];
    for(int i = 2; i <= n; ++ i)
        b[i][1] = g[m + i - 1][n + m];
    for(int j = 2; j <= m; ++ j)
        b[1][j] = g[j][n + m];
    for(int i = 2; i <= n; ++ i)
        for(int j = 2; j <= m; ++ j)
            b[i][j] = a[1][1] ^ a[i][1] ^ a[1][j] ^ a[i][j] ^ b[1][1] ^ b[i][1] ^ b[1][j];
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j)
            printf("%d", b[i][j]);
        puts("");
    }
    return 0;
}
Last modification:January 28th, 2019 at 03:11 pm

Leave a Comment