首页 > ACM题库 > HDU-杭电 > HDU 4592-Boring Game-数论-[解题报告]HOJ
2015
09-17

HDU 4592-Boring Game-数论-[解题报告]HOJ

Boring Game

问题描述 :

Zero likes to play a boring game when he feels extremely boring. This his game proceeds in a square board with n rows and n column. Each grid in the board has either of two colors black or white. In each turn, Zero chooses a grid first. Let’s assume that the grid he chooses locates in the xth row and the yth column. And then, the neighbors which are existed of this grid (x + 1, y), (x �C 1, y), (x, y + 1), (x, y �C 1) and itself will convert their color into another. Till the end, Zero will transform the initial board to the goal board whose grids are all white. For instance, Here is the way to attain his goal. In his first turn, he selects (2, 2). And then he selects (1, 1) in the second turn. After that, he reaches his goal.
Math Homework

Zero reckons this mission, however, is too simple and naive. So he prefers to accomplish this assignment in minimal turns. He doesn’t know whether the turns he needs are the minimal turns, because of that he needs you to tell him the minimal turns of these initial boards.

输入:

There are several test cases in the input file. The first line of the input file contains an integer m(m <= 106), then m cases follow.
The first line of each test case contains an integer n(1 <= n <= 8), which is the length of a side of the square board.
Then the next line contains n integer a[i](0 <= a[i] <= 2n, 1 <= i <= n), which is the statement of the ith row respectively. The definition of a statement can be illustrated as n-length binary numbers, zero represents white and one represents black. For example, when n is equal to 4 and a[0] is equal to 5 = (0101)2, you can consider that the condition in the first line of this board is white, black, white, black.

输出:

There are several test cases in the input file. The first line of the input file contains an integer m(m <= 106), then m cases follow.
The first line of each test case contains an integer n(1 <= n <= 8), which is the length of a side of the square board.
Then the next line contains n integer a[i](0 <= a[i] <= 2n, 1 <= i <= n), which is the statement of the ith row respectively. The definition of a statement can be illustrated as n-length binary numbers, zero represents white and one represents black. For example, when n is equal to 4 and a[0] is equal to 5 = (0101)2, you can consider that the condition in the first line of this board is white, black, white, black.

样例输入:

2
3
4 3 2
4
1 0 0 0

样例输出:

2
-1

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4592

分析:

本题的数据量特别大,所以要对高斯消元尽可能多的优化。

因为n的范围比较小为1~8 ,因此我们可以将系数阵的逆给求出来 然后根据逆来判断有没有解 ,

有解的情况下 直接用A^(-1)*B=X; 求解,但是由于系数阵是0,1的 相当于二进制, 我们可以将其改成10进制 

然后进行运算的时候就快一点了 ,然后统计解中1的个数 直接枚举即可

代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
//#define debug
using namespace std;

int a[30][30];
int x[80],n,equ,var;

void init()
{
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x[0])*30);
    equ=n*n;
    var=equ;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i!=0) a[i*n+j][(i-1)*n+j]=1;
            if(i!=n-1) a[i*n+j][(i+1)*n+j]=1;
            if(j!=0) a[i*n+j][i*n+j-1]=1;
            if(j!=n-1) a[i*n+j][i*n+j+1]=1;
            a[i*n+j][i*n+j]=1;
        }
    }
}

int Gauss()
{
    int k,col,max_r;

    for(k=0,col=0; k<equ&&col<var; k++,col++)
    {
        if(a[k][col]==0)
        {
            max_r=k;
            for(int i=k+1; i<equ; i++)
                if(a[i][col]>a[max_r][col])
                {
                    max_r=i;
                    break;
                }
            if(max_r!=k)
                for(int i=0; i<=var; i++)
                    swap(a[max_r][i],a[k][i]);
        }
        if(a[k][col]==0)
        {
            k--;
            continue;
        }
        for(int i=k+1; i<equ; i++)
        {
            if(a[i][col])
                for(int j=col; j<=var; j++)
                    a[i][j]=a[i][j]^a[k][j];
        }
    }
    for(int i=k; i<equ; i++)
        if(a[i][var]) return -1;

    int lim=(1<<(var-k)),ans=100000;
    for(int i=0; i<lim; i++)
    {
        int temp=i,sum=0;
        for(int j=var-1; j>=k; j--)
        {
            x[j]=temp&1;
            temp>>=1;
        }
        for(int j=k-1; j>=0; j--)
        {
            x[j]=a[j][var]&1;
            for(int r=j+1; r<var; r++)
                x[j]=x[j]^(a[j][r]&x[r]);
        }
        for(int j=0; j<var; j++)
            sum+=x[j];
        ans=min(ans,sum);
    }
    return ans;
}
int n2[4][2]=
{
    3,2,3,1,2,3,1,3
};
int n3[9][3]=
{
    5,1,6,0,2,7,5,4,3,1,3,1,
    2,7,2,
    4,6,4,
    6,1,5,
    7,2,0,
    3,4,5
};
int n6[36][6]=
{
    43,8,55,10,44,40,
    3,20,53,17,14,4,
    44,42,7,32,55,34,
    13,21,56,1,59,17,
    48,10,43,34,28,8,
    53,4,59,20,13,5,
    8,28,2,27,34,44,
    20,54,5,59,21,14,
    42,43,10,48,2,55,
    21,53,20,3,16,59,
    10,27,40,55,42,28,
    4,14,16,54,17,13,
    55,2,48,42,27,10,
    53,5,56,1,59,17,
    7,10,28,40,48,32,
    56,20,14,5,3,1,
    43,40,7,32,55,34,
    59,16,3,21,54,20,
    10,27,42,48,2,55,
    17,59,1,56,5,53,
    32,48,40,28,10,7,
    1,3,5,14,20,56,
    34,55,32,7,40,43,
    20,54,21,3,16,59,
    44,34,27,2,28,8,
    14,21,59,5,54,20,
    55,2,48,10,43,42,
    59,16,3,20,53,21,
    28,42,55,40,27,10,
    13,17,54,16,14,4,
    40,44,10,55,8,43,
    4,14,17,53,20,3,
    34,55,32,7,42,44,
    17,59,1,56,21,13,
    8,28,34,43,10,48,
    5,13,20,59,4,53
};
int n7[49][7]=
{
    109,65,14,84,88,16,96,
    108,34,27,2,28,40,112,
    3,20,53,81,110,84,56,
    107,0,107,8,119,42,28,
    96,20,86,69,59,21,14,
    27,34,108,32,28,10,7,
    91,65,56,21,13,4,3,
    65,99,21,86,68,56,16,
    34,119,32,7,42,108,40,
    20,54,69,91,5,86,84,
    0,0,8,28,34,107,42,
    20,54,81,109,80,53,21,
    34,119,2,112,42,27,10,
    65,99,84,53,17,14,4,
    14,21,59,5,54,68,88,
    27,32,107,8,119,42,28,
    53,69,88,17,99,5,110,
    107,8,119,34,0,34,119,
    86,81,13,68,99,80,59,
    108,2,107,8,119,42,28,
    56,84,110,80,54,17,13,
    84,86,5,91,5,86,84,
    2,7,8,27,8,7,2,
    81,91,17,96,17,91,81,
    8,28,34,107,34,28,8,
    69,109,68,3,68,109,69,
    32,112,8,108,8,112,32,
    21,53,80,109,80,53,21,
    88,68,54,5,59,21,14,
    28,42,119,8,107,32,27,
    110,5,99,17,88,69,53,
    119,34,0,34,119,8,107,
    59,80,99,68,13,81,86,
    28,42,119,8,107,2,108,
    13,17,54,80,110,84,56,
    16,56,68,86,21,99,65,
    40,108,42,7,32,119,34,
    84,86,5,91,69,54,20,
    42,107,34,28,8,0,0,
    21,53,80,109,81,54,20,
    10,27,42,112,2,119,34,
    4,14,17,53,84,99,65,
    96,16,88,84,14,65,109,
    112,40,28,2,27,34,108,
    56,84,110,81,53,20,3,
    28,42,119,8,107,0,107,
    14,21,59,69,86,20,96,
    7,10,28,32,108,34,27,
    3,4,13,21,56,65,91
};
int n8[64][8]=
{
    220,138,7,128,199,170,108,40,
    214,81,13,64,237,1,238,68,27,0,27,32,107,168,199,130,237,81,54,16,14,5,3,1,183,138,108,8,112,160,192,128,216,0,216,4,214,21,227,65,107,138,176,2,183,128,119,34,
    59,81,224,1,227,85,54,20,138,219,10,192,42,171,130,108,81,219,17,224,65,3,69,238,0,0,32,112,136,172,42,199,81,219,65,56,21,13,4,3,138,219,130,28,168,176,32,192,0,0,4,14,17,53,84,227,138,219,136,7,130,192,162,119,
    81,219,80,3,84,213,65,54,
    7,10,28,160,172,2,171,170,
    13,17,54,16,14,5,3,1,
    27,32,107,136,183,10,172,168,
    54,65,213,68,59,20,13,5,
    108,130,171,34,220,40,176,160,
    216,4,214,17,237,80,53,21,
    176,136,108,8,112,160,192,128,
    224,80,56,5,53,64,213,85,
    128,192,160,112,136,172,42,199,
    64,224,16,216,84,14,65,237,
    32,112,136,172,10,183,136,107,
    16,56,68,214,69,59,21,14,
    8,28,34,107,162,220,168,112,
    4,14,17,53,80,237,17,214,
    2,7,8,27,42,112,130,183,
    1,3,5,14,17,53,84,227,
    199,42,172,136,112,160,192,128,
    237,65,14,84,216,16,224,64,
    107,136,183,10,172,136,112,32,
    14,21,59,69,214,68,56,16,
    112,168,220,162,107,34,28,8,
    214,17,237,80,53,17,14,4,
    183,130,112,42,27,8,7,2,
    227,84,53,17,14,5,3,1,
    170,171,2,172,160,28,10,7,
    1,3,5,14,16,54,17,13,
    168,172,10,183,136,107,32,27,
    5,13,20,59,68,213,65,54,
    160,176,40,220,34,171,130,108,
    21,53,80,237,17,214,4,216,
    128,192,160,112,8,108,136,176,
    85,213,64,53,5,56,80,224,
    108,130,171,42,192,10,219,138,
    238,69,3,65,224,17,219,81,
    199,42,172,136,112,32,0,0,
    3,4,13,21,56,65,219,81,
    192,32,176,168,28,130,219,138,
    227,84,53,17,14,4,0,0,
    119,162,192,130,7,136,219,138,
    54,65,213,84,3,80,219,81,
    40,108,170,199,128,7,138,220,
    68,238,1,237,64,13,81,214,
    130,199,168,107,32,27,0,27,
    1,3,5,14,16,54,81,237,
    128,192,160,112,8,108,138,183,
    65,227,21,214,4,216,0,216,
    34,119,128,183,2,176,138,107,
    20,54,85,227,1,224,81,59
};



int ans[80];
int b[10];
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        int sum=0;
        for(int i=0; i<n; i++)
            scanf("%d",&b[i]);
        if(n==4||n==5)
        {
            init();
            for(int i=0; i<n; i++)
            {
                int r=(i+1)*n-1,l=i*n;
                while(r>=l)
                {
                    a[r][var]=b[i]&1;
                    b[i]>>=1;
                    r--;
                }
            }
            int ans=Gauss();
            printf("%d\n",ans);
            continue;
        }
        if(n==1)
        {
            printf("%d\n",b[0]);
            continue;
        }
        equ=n*n;
        memset(ans,0,sizeof(ans[0])*(equ+4));
        if(n==2)
        {
            for(int j=0; j<n; j++)
                if(b[j])
                {
                    for(int i=0; i<equ; i++)
                        ans[i]=ans[i]^(n2[i][j]&b[j]);
                }
        }
        else if(n==3)
        {
            for(int j=0; j<n; j++)
                if(b[j])
                {
                    for(int i=0; i<equ; i++)
                        ans[i]=ans[i]^(n3[i][j]&b[j]);
                }
        }
        else if(n==6)
        {
            for(int j=0; j<n; j++)
                if(b[j])
                {
                    for(int i=0; i<equ; i++)
                        ans[i]=ans[i]^(n6[i][j]&b[j]);
                }
        }
        else if(n==7)
        {
            for(int j=0; j<n; j++)
                if(b[j])
                {
                    for(int i=0; i<equ; i++)
                        ans[i]=ans[i]^(n7[i][j]&b[j]);
                }
        }
        else if(n==8)
        {
            for(int j=0; j<n; j++)
                if(b[j])
                {
                    for(int i=0; i<equ; i++)
                        ans[i]=ans[i]^(n8[i][j]&b[j]);
                }
        }
        for(int i=0; i<equ; i++)
        {
            int cnt=0;
            while(ans[i])
            {
                cnt^=(ans[i]&1);
                ans[i]>>=1;
            }
            sum+=cnt;
        }
        printf("%d\n",sum);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/bigbigship/article/details/39101587