POJ 1222【异或高斯消元|二进制状态枚举】

时间：2021-09-28 09:48:15

题目链接：【http://poj.org/problem?id=1222】

题意：Light Out，给出一个5 * 6的0，1矩阵，0表示灯熄灭，反之为灯亮。输出一种方案，使得所有的等都被熄灭。

题解：首先可以用高斯消元来做，对于每个点，我们列出一个方程，左边是某个点和它相邻的点,他们的异或值等于右边的值（灯亮为1 ，灯灭为0），然后求一个异或高斯消元就可以了。可以用bitset优化，或者__int128优化（其实unsigned就可以了）。

　　还可以枚举第一行的按开关的状态共有1<<6中状态，从上到下检查，如果某一行的某一个灯是亮的，那只有用按下下一行的这个位置的开关使得这个位置的灯熄灭，最后判断最后一行是否熄灭就可以了。

高斯消元：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 35;

int T;

int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

int a[maxn][maxn], ans[maxn];

int idx(int x, int y)

{

    return (x - 1) * 6 + y;

}

void Guess()

{

    int i, j, k, l;

    for(i = 1, j = 1; i <= 30 && j <= 30; j++)

    {

        for(k = i; k <= 30; k++)

            if(a[k][j]) break;

        if(a[k][j])

        {

            for(l = 1; l <= 31; l++) swap(a[i][l], a[k][l]);

            for(l = 1; l <= 30; l++) //debug从1开始（回代）

            {

                if(l != i && a[l][j])

                    for(k = 1; k <= 31; k++)

                        a[l][k] ^= a[i][k];

            }

            i++;

        }

    }

    for(int j = 1; j < i; j++) ans[j] = a[j][31];

    //*元不是必须按的，则标记为0

}

int main ()

{

    int ic =0;

    scanf("%d", &T);

    while(T--)

    {

        memset(a, 0, sizeof(a));

        for(int i = 1; i <= 5; i++)

            for(int j = 1; j <= 6; j++)

            {

                scanf("%d", &a[idx(i, j)][31]);

            }

        for(int i = 1; i <= 30; i++)

        {

            a[i][i] = 1;

            int X = (i - 1) / 6 + 1;

            int Y = i - idx(X, 0);

            for(int j = 0; j < 4; j++)

            {

                int x = X + dir[j][1];

                int y = Y + dir[j][0];

                if(x < 1 || y < 1 || x > 5 || y > 6) continue;

                a[i][idx(x, y)] = 1;

            }

        }

        Guess();

        printf("PUZZLE #%d\n",++ic);

        for(int i = 1; i <= 30; i++)

        {

            printf("%d", ans[i]);

            if(!(i % 6)) printf("\n");

            else printf(" ");

        }

    }

    return 0;

}

Bitset:

#include<bitset>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 35;

int T;

int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

bitset<maxn>a[maxn];

int idx(int x, int y)

{

    return (x - 1) * 6 + y;

}

void Guess()

{

    int i, j, k, l;

    for(i = 1, j = 1; i <= 30 && j <= 30; j++)

    {

        for(k = i; k <= 30; k++)    if(a[k][j]) break;

        if(a[k][j])

        {

            swap(a[i], a[k]);

            for(l = 1; l <= 30; l++) //debug从1开始（回代）

                if(l != i && a[l][j])   a[l] ^= a[i];

            i++;

        }

    }

}

int main ()

{

    int ic = 0;

    scanf("%d", &T);

    while(T--)

    {

        for(int i = 1; i <= 31; i++) a[i].reset();

        for(int i = 1; i <= 5; i++)

            for(int j = 1; j <= 6; j++)

            {

                int t = 0 ;

                scanf("%d", &t);

                if(t)   a[idx(i, j)].set(31);

            }

        for(int i = 1; i <= 30; i++)

        {

            a[i][i] = 1;

            int X = (i - 1) / 6 + 1;

            int Y = i - idx(X, 0);

            for(int j = 0; j < 4; j++)

            {

                int x = X + dir[j][1];

                int y = Y + dir[j][0];

                if(x < 1 || y < 1 || x > 5 || y > 6) continue;

                a[i].set(idx(x, y));

            }

        }

        Guess();

        printf("PUZZLE #%d\n", ++ic);

        for(int i = 1; i <= 30; i++)

        {

            if(a[i][31]) printf("1");

            else printf("0");

            if(!(i % 6)) printf("\n");

            else printf(" ");

        }

    }

    return 0;

}

　unsigned:

#include<bitset>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 35;

int T;

int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

unsigned long long a[maxn];

int idx(int x, int y)

{

    return (x - 1) * 6 + y;

}

void Guess()

{

    int i, j, k, l;

    for(i = 1, j = 1; i <= 30 && j <= 30; j++)

    {

        for(k = i; k <= 30; k++)    if(a[k] & ((unsigned long long)1 << (j - 1))) break;

        if(a[k] & ((unsigned long long)1 << (j - 1)))

        {

            swap(a[i], a[k]);

            for(l = 1; l <= 30; l++)

                if(l != i && a[l] & ((unsigned long long)1 << (j - 1)))   a[l] ^= a[i];

            i++;

        }

    }

}

int main ()

{

    int ic = 0;

    scanf("%d", &T);

    while(T--)

    {

        for(int i = 1; i <= 31; i++) a[i] = 0;

        for(int i = 1; i <= 5; i++)

            for(int j = 1; j <= 6; j++)

            {

                int t = 0 ;

                scanf("%d", &t);

                if(t)   a[idx(i, j)] |= ((unsigned long long)1 << 30);

            }

        for(int i = 1; i <= 30; i++)

        {

            a[i] |= ((unsigned long long)1 << (i - 1));

            int X = (i - 1) / 6 + 1;

            int Y = i - idx(X, 0);

            for(int j = 0; j < 4; j++)

            {

                int x = X + dir[j][1];

                int y = Y + dir[j][0];

                if(x < 1 || y < 1 || x > 5 || y > 6) continue;

                a[i] |= ((unsigned long long)1 << idx(x, y) - 1);

            }

        }

        Guess();

        printf("PUZZLE #%d\n", ++ic);

        for(int i = 1; i <= 30; i++)

        {

            if(a[i] & ((unsigned long long)1 << 30)) printf("1");

            else printf("0");

            if(!(i % 6)) printf("\n");

            else printf(" ");

        }

    }

    return 0;

}

　　

二进制状态枚举：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 15;

int T;

int a[maxn][maxn], tmp[maxn][maxn], ans[maxn][maxn];

int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

void flip(int x, int y)

{

    ans[x][y] = 1;

    tmp[x][y] ^= 1;

    for(int i = 0; i < 4; i++)

    {

        int X = x + dir[i][0];

        int Y = y + dir[i][1];

        if(X < 1 || X > 5 || Y < 1 || Y > 6) continue;

        tmp[X][Y] ^= 1;

    }

}

int main ()

{

    int ic = 0;

    scanf("%d", &T);

    while(T--)

    {

        for(int i = 1; i <= 5; i++)

            for(int j = 1; j <= 6; j++)

                scanf("%d", &a[i][j]);

        for(int k = 0; k <= (1 << 6) - 1; k++)

        {

            for(int i = 1; i <= 5; i++)

                for(int j = 1; j <= 6; j++)

                    tmp[i][j] = a[i][j], ans[i][j] = 0;

            int t = k, pos = 1;

            while(t)

            {

                if(t & 1) flip(1, pos);

                t >>= 1;

                pos++;

            }

            for(int i = 1; i <= 4; i++)

                for(int j = 1; j <= 6; j++)

                    if(tmp[i][j]) flip(i + 1, j);

            int sum = 0;

            for(int i = 1; i <= 6; i++)

                sum += tmp[5][i];

            if(!sum) break;

        }

        printf("PUZZLE #%d\n",++ic);

        for(int i = 1; i <= 5; i++)

        {

            for(int j = 1; j <= 5; j++)

                printf("%d ", ans[i][j]);

            printf("%d\n", ans[i][6]);

        }

    }

    return 0;

}

　　

相关文章