【二进制矩阵】ACwing 暑假每日一题
本文最后更新于:2021年8月18日下午1点45分
原题链接:
解析:
修改元素方法:
题目中给了以下这段话
想要证明这个答案一定存在,方法是:
对于一个2X2
的矩阵,如下图
我们进行如图所示的编号
当我们用题目所描述的方法:**选中一个 2×2 的子矩阵,改变其中 3 个元素的值(00 变为 11,11 变为 00) **
修改①号元素方法如下:(按照 a , b , c 的顺序改变3个元素的值
可以看到,①号位置的元素被修改了3次,其余②③④位置的元素被修改了两次
最终只有①号位置的元素被修改,因此总操作数最多为数据量的3倍,即:3mn
姑且叫这种方法叫做:3L变换(即通过3次L型变换修改其中的数据
同理:修改②号元素的方法为:
自定义L型方向:
特判:
相同的颜色可以对应同一种变换方式,只需要分四种情况讨论即可:
- 红色对应 i<n 且 j=1:选择以该点为左上角的矩阵
- 绿色对应 i=1 且 j>1:选择以该点为右上角的矩阵
- 黄色对应 i=n 且 j<m:选择以该点为左下角的矩阵
- 蓝色对应 i>1 且 j=m:选择以该点为右下角的矩阵
注意:
- 注意特判
- 传入的
i
和j
的值,应该是拐点的IO坐标 - 注意读取二维数组读取字符的时候,
scanf("%s",a[i] + 1);
,其中这里的+1
是代表从a[i][1]
开始放字符串,因为这题数组下标是从1
开始的,例如传入10010
,那么a[i][1]=1
a[i][2]=0
a[i][3]=0
a[i][4]=1
a[i][5]=0
- 这题只要输出一种可能情况即可
AC源代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!