天天看点

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,而且每次不用重新创建一个临时对象