P5427 [USACO19OPEN] Left Out S

发布时间 2023-07-18 11:21:20作者: DaisySunchaser
 
你有个01矩阵,每次可翻转一行或一列,问能否使得最后只有一个0或1。其中翻转指1变0,0变1。
 
做法基本上都是取第一行第一列给他全部翻成0。这个是一定可以办到的。你只需要找1的位置翻掉那一行/列即可。
 该图来自洛谷
完了之后答案要么在红色,要么紫要么黄。
1、红:此时黄色区域全为1。显然紫各翻一次即可全1,但红无法做到。
2、黄:黄区只有一个1。就是他。
3、紫:黄区有一行/列为1。翻那行/列,紫区就会有一个1。就是他。
4、如果都不满足,就无解。
 
Q:一定要翻第一行第一列吗?
A:不一定。任意一行一列都可。反正就那意思。
Q:为什么先要这样翻?为什么后面就不能这样翻而是直接讨论了?
A:因为第一次这样翻,可以保证做到全部变0。而后面这样翻必定会破坏先前的。所以我们这样做实际上是添加了一个限制条件,以遏制一开始的混乱局面,使得矩阵条例清晰、以便我们下一步更加接近答案。显然,我们的做法就是分类进行讨论。
Q:还是有点不明白怎么办?
A:凉拌。下来再想想吧,已经没话说了。
Q:为什么黄色部分不满足上述三条件之一就一定无解?如果黄色区域还是一团乱七八糟的,就没有其他做法了吗?
A:因为答案只可能在这三区之中,而三区有解的条件我们已经得出了。不符合这三种条件的,难道答案会在三区之外?。很显然没有别的做法了,因为黄色区域再翻只会破坏一开始的红紫区。你搞来搞去,反正做法还不就是找一行一列来搞上述步骤。现在明白了吗?
Q:这个做法是怎样想到的?
A:我认为,就是分类讨论。本身我们拿到这个题的时候,他是有N种复杂难以想象的情况的。但是我们可以想办法把这个大问题分成一些我们可以容易解决的小问题,也就是分类。将答案的全部分成不同类别讨论,化繁为简。
Q:但是分红黄紫区域这种是咋想到的?
A:这可能是很好想到的,但思维题的事情总是抽象的。多做题去解决这个疑问吧。