前往
大廳
主題

ZeroJudge - b530: 板條編年史 (四):板擦界、板條界與板燒界 解題心得

Not In My Back Yard | 2021-05-18 00:00:05 | 巴幣 0 | 人氣 141

題目連結:


題目大意:
輸入第一列給定一正整數 n (1 ≦ n ≦ 3000),代表 01 方陣 A 、 B 、 C 之大小。接著若干列之內容為方陣 A 、 B 、 C 的內容。

試問 A × B 是否等於 C ?

其中 01 方陣之乘法跟一般矩陣不大一樣,例如:
1 1
0 0
乘以
1 1
0 1
之結果的左上角為 (1, 1)・(1, 0) = (1 & 1) ^ (1 & 0) = 1。

其中「&」為位元運算裡的「AND」、「^」為位元運算裡的「XOR」。由此可以看到,本題將原本的矩陣乘法之「乘」的部分換成了「&」、「加」的部分換成了「^」。



範例輸入:
2
1 0
0 1
1 0 0 1
1
0
0
1


範例輸出:
YES


解題思維:
因為資料量有點多,所以建議將輸出入最佳化(簡單的即可,如這題)。

然後按照類似一般矩陣乘法將 A 、 B 相乘(記得將「乘」換成「&」、「加」換成「^」)得出每一格的值。然後將該值去比較對應行列的 C 的格子之值。如果不一樣,則剩下就不必比較了,直接跳出即可。

最後看過程中間有沒有中途跳出,如果有則代表 AB ≠ C ;反之, AB = C 。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作