[GDKOI 2021 DAY1 T1] 普及組 地圖 (map) 題解

題目描述

 Alice 得到了一張神秘地圖，并将神秘地圖的規則給了你。

其中a的值為0或1，ri ，ci 定義如下:

即cici 表示第ii列和第n列裡面全部a的異或和，ri 表示的是第ii行和第n行全部的異或和。

很不幸的是，現在這個地圖裡面有一個數字錯了，你能找出來嗎?

輸入

第一行一個整數n，表示矩陣大小。

接下來 n行，每行n個整數，表示一個n×n的矩陣。

輸出

一行，兩個整數x,y，表示(x,y)位置出錯。

樣例輸入

4

0 0 0 0

0 0 1 1

1 1 1 0

1 1 1 0

 樣例輸出

2 2

樣例解釋

資料範圍 

對于 30% 的資料，n≤4n≤4

對于 60%的資料，n≤200n≤200

對于 100%的資料，4≤n≤2000

思路

根據小例子，找題目描述的規律。

發現按照題意直接xor後，通過對比xor結果資料與輸入資料得到的特征，可以得到哪個位置錯了。

注:xor 是異或的意思

如果不知道的同學：https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin

簡單來說，異或就是。。。。

額(我也不知道啊)，舉個例子：

a^b 就是如果a==b,a^b=0;否則a^b=1;

即同為0，異為負。（要不然怎麼叫異或呢？）

這道題的細節有“億”點點多：

1. 我們可以發現，除了(1,1)(1,n)(n,1)這幾個位置的值是給定值外，其他的(1, i)和(i ,1)都是通過按照規則計算生成的。
2. 那麼就可以用第一行n-2個位置的計算結果與原始輸入結果進行比較，統計不同數ansc
3. 同理，第一列也可以進行類似操作，統計ansr
4. 通過規律：假設是(x,y) （2≤x,y≤n−1） 位置出錯，那麼ansc=ansr=1；

代碼實作

#include<bits/stdc++.h>
using namespace std;
int a[2002][2002];
int r[2002], c[2002];
int n;
int ansr, ansc;
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        ansr^=a[n][i];
    }
    for (int i = 1; i <= n; i++) {
        ansc^=a[i][n];
    }
    for (int i = 2; i < n; i++) {
        for (int j = 2; j <= n; j++) {
            r[i] ^= a[i][j];
            c[i] ^= a[j][i];
        }
        r[i]^=ansr;
        c[i]^=ansc;
    }
    int x=1, y=1;
    for (int i=2; i<n; i++) {
        if (a[i][1]!=r[i]) {
            if (x==1)
                x=i;
            else {
                x = n;
                break;
            }
        }
    }
    for (int i = 2; i < n; i++) {
        if (a[1][i]!=c[i]) {
            if (y==1)
                y=i;
            else {
                y=n;
                break;
            }
        }
    }
    printf("%d %d\n", x, y);
    return 0;
}
           

完結撒花✿