天天看點

AcWing 3814. 矩陣變換

原題連結

給定一個 \(n×n\) 的 01 矩陣。

你可以選擇若幹列(也可以不選),并将這些列上的所有元素進行變換(1 變 0,0 變 1)。

你的目标是使得矩陣中有盡可能多的行滿足:一行中的所有元素都為 1。

輸出可以得到的滿足條件的行的最大數量。

第一行包含整數 \(n\)。

接下來 \(n\) 行,每行包含一個長度為 \(n\) 的 01 字元串,表示整個矩陣。

思維題, 考慮到兩點:1、若改變某列的元素,行與行之間的相等關系依然不變;2、任意行都可以變成全1。

通過這兩點,我們可以将問題轉化為,相同字元串的最大數量,将每一行作為一個字元串,再用哈希表存,最後周遊哈希表,找到最大的就可以了。

PS: <code>auto&amp; [k, v] : cnt</code>是C++ 17中的新特性。

&amp;是引用,等價于傳遞的是指針,隻不過不用∗解位址,直接當變量用即可,因為底部是用指針實作的是以,可以直接修改容器内的值 帶&amp;速度更快,因為傳遞的是指針,隻有4B,而且每次不用重新建立一個臨時對象