讨论/题目交流/🏆 第 166 场力扣周赛/
🏆 第 166 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 整数的各位积和之差
4 分 - 用户分组
5 分 - 使结果不超过阈值的最小除数
6 分 - 转化为全零矩阵的最少反转次数

展开讨论
  • 整数的各位积和之差
    暴力计算每一位,然后计算和和积做差就行了。时间复杂度 O(n)O(n)nn 为数字位数。

  • 用户分组
    先把数字相同的分到一个组,然后例如一个组里面全是3,那么就每三个作为一个新组就可以了。时间复杂度 O(n)O(n)

  • 使结果不超过阈值的最小除数
    显然除数越小,最后的结果和越大,这是满足单调关系的。于是我们可以二分我们的除数,每次判断中间结果和阈值的大小关系就可以了。时间复杂度 O(nlogn)O(nlogn)

  • 转化为全零矩阵的最少反转次数

需要先证明几个推论:

  1. 不会以同一个位置为中心翻转超过1次:如果某个位置翻转 n 次,结果和翻转 n % 2 次其实等价,因为翻过去再翻过来等于没变化。
  2. 对于两个要翻转的位置,翻转顺序对结果没有影响:因为翻转本质上是对5个位置取异或操作,所以最后的改变只和该位置被操作的次数有关,而与操作顺序无关。

那么有了这两个结论以后,我们就可以枚举每个格子是否翻转,由于只有 9 个格子,所以可能的状态只有 29=5122^9=512 种。每一种我们暴力判断一下就可以了。

如果题目只要求一组可行解而不是次数最少的解的话,题目是存在多项式解的:

假设我们有 n 行 m 列,我们记每行每列是否翻转为 xijx_{ij}, 那么 xij0,1x_{ij}∈{0,1}。对于每个格子,假设他本身的值是 aija_{ij},能影响到他的点有 (i,j),(i,j1),(i1,j),(i,j+1),(i,j1)(i,j),(i,j-1),(i-1,j),(i,j+1),(i,j-1) 五个,最后我们希望他的值是 0, 那么:

(xij1+xij+1+xij+xi+1j+xi1j+aij)%2=0(x_{ij-1} + x_{ij+1} + x_{ij} + x_{i+1j} + x_{i-1j} + a_{ij} ) \% 2 = 0

对于每个格子我们都有这样的一个方程,最后就变成了一个n元1次模线性方程组,可以直接在多项式时间内用高斯消元求解各个变量。

2
展开全部 22 讨论