题目描述：给n×m的01矩阵，每次操作可以把某一行或者某一列的每一个数翻转。问是否可以经过若干次操作，使矩阵从左到右、从上到下数值不下降。
题目的数据范围为1≤n,m≤200，但完全可以用O(nm)时间完成。
显然一个数值不下降的矩阵，可以由这样一个矩阵转换得到：它仅有至多一行不全为0，且如果这一行存在，那么这一行的元素必须满足前i项为0，而i+1到n项为1$( 0 < i ≤ n)$。不妨将这一行称为特殊行。
根据定义，一个矩阵可以转换为前述矩阵的必要条件是非特殊行全部能转换为0。不妨设第一列不翻转(翻转第一列等价于翻转每一行和第2~m列)，因此先翻转所有a[i][1]=1的第i行。然后分两种情况：如果特殊行不是第一行，那么翻转所有a[1][i]=1的第i列，然后判断当前矩阵是否满足条件，满足条件就说明找到答案了。如果特殊行是第一行，那么随意取另外一行为非特殊行，类似翻转即可。实际翻转和判断时，并不需要对每一个元素进行操作，只要对一行或者一列进行标记操作，而求某元素数值只要与所在行列的标记进行异或运算即可。
注意输出时，还要把所得矩阵转换回不下降矩阵。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
int a[330][330],r[200],c[200];
int n,m;
bool check(){
int flag=0;
for(int i=1;i<=n;i+=1){
for(int j=1;j<=m;j+=1){
if(a[i][j]^r[i]^c[j]){
if(flag)return 0;
flag=1;
for(int k=j+1;k<=m;k+=1){
if(!(a[i][j]^r[i]^c[j]))return 0;
}
break;
}
}
}
return 1;
}
void print(){
cout<<"YES\n";
int flag=0;
for(int i=1;i<=n;i+=1){
for(int j=1;j<=m;j+=1){
if(a[i][j]^r[i]^c[j]){
for(int k=i+1;k<=n;k+=1){
r[k]^=1;
}
flag=1;break;
}
}
if(flag)break;
}
for(int i=1;i<=n;i+=1){
cout<<r[i];
}
cout<<endl;
for(int i=1;i<=m;i+=1){
cout<<c[i];
}
cout<<endl;
}
int main (/*int argc, char const* argv[]*/){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i+=1){
for(int j=1;j<=m;j+=1){
cin>>a[i][j];
}
}
c[1]=0;
for(int i=1;i<=n;i+=1){
r[i]=a[i][1];
}
for(int i=2;i<=m;i+=1){
c[i]=a[n][i]^r[n];
}
if(check()){print();return 0;}
for(int i=2;i<=m;i+=1){
c[i]=a[1][i]^r[1];
}
if(check()){print();return 0;}
cout<<"NO\n";
return 0;
}
以上。