CodeForces - 1016D 补零思想

题目连接：

https://vjudge.net/problem/1753263/origin

其实这道题跟行列式里的分块发有点类似，但也是类似罢了。

主要的思想是每一行，每一列的第一行（或者最后一行）空出，让后根据下列算式：

行异或和：suma = a[1]^a[2]^a[3]...^a[n].

列异或和：sumb = b[1]^b[2]^b[3]...^b[m].

且本题的判断为YES的充要条件是：suma = sumb

有异或和的算法：x^a = b  <==> x^b = a 知：

a[1]^a[2]^a[3] ... ^a[n-1] = a[n]^suma

b[1]^b[2]^b[3] ... ^b[m-1] = = b[m]^sumb

|

|

------------------------| ---x

比如这两条线的交点为x 则要找到一个x(a[n] = b[m])使他满足：

x^a[1]^a[2]^a[3]^ ... ^a[n-1] = b[m]  且

x^b[1]^b[2]^b[3]^ ... ^ b[m-1] = a[n]

也就是 x^suma^a[n] = b[m],

故 x = suma^a[n]^b[m].

AC代码以及步骤解释如下:

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

const int MX = +;

int a[MX], b[MX];

int mp[MX][MX];

int main()

{

    memset(mp, , sizeof(mp)); //初始化填充0

    int n, m;

    int suma = , sumb = ;

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; ++i)

    {

        scanf("%d", &a[i]); //行的异或和

        suma ^= a[i]; //suma是行的总异或和

    }

    for(int i = ; i <= m; ++i)

    {

        scanf("%d", &b[i]); //列的异或和

        sumb ^= b[i]; //sumb是列的总异或和

    }

    if(suma != sumb) //若行的总异或和不等于列的总异或和，则不成立

    {

        printf("NO\n");

        return ;

    }

    int x = suma^a[n]^b[m]; //根据公式得到x

    for(int i = ; i <= n; ++i) mp[i][m] = a[i]; //最后行，列进行初始化

    for(int i = ; i <= m; ++i) mp[n][i] = b[i];

    mp[n][m] = x; //赋值X

    printf("YES\n");

    for(int i = ; i <= n; ++i) //打印矩阵

    {

        for(int j = ; j <= m; ++j)

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

        printf("\n");

    }

}

如有疑问，欢迎评论提出！