用时 : 参考了答案
看完题目首先是想到dp是跑不掉的
但是写出转化方程式需要一定的技巧
观察到 dp[1][1] = matrix[0][0] ^ matrix[0][1] ^ matrix[1][0] ^ matrix[1][1]
然后利用异或的性质
相同值异或为0,任何值与0异或为其本身
可以写成
dp[1][1] = matrix[0][0] ^ (matrix[0][1] ^ matrix[0][0]) ^ (matrix[1][0] ^ matrix[1][0]) ^ matrix[1][1]
进而得到
dp[i][j] = dp[i - 1][j - 1] ^ dp[i][j - 1] ^ dp[i - 1][j] ^ matrix[i][j]
(这我是我没有想到的技巧,如果能画图的话其实可以想明白
(1,1) | (1,2) | |
(2,1) | (2,2) |
(1,2) 和 (2,1) 的区域 异或之后,重叠的部分被消除
而重叠的部分正好是(1,1)的区域,因此 可以再 异或(1,1) 来补偿
1 | const swap = function (arr,i,j) { |
然后K大 应该用 最小堆来做,这边用了最大堆不过问题不大