统计奇数和的行列；零个则 OK，恰各一个则是唯一需翻转的位置。
OJ: noi_openjudge
题目 ID: ch0108-04
难度:普及-
标签:矩阵模拟数学python
日期: 2026-07-30 23:01
题意
判断
思路
翻转一个格子只会改变它所在行和列的奇偶性。因此没有奇数和行列时为 OK；恰好一条奇数和行、恰好一条奇数和列时，交点就是修复位置；其余为 Corrupt。
代码
cpp
#include <cstdio>
int m,n;
int map[200][200];
bool is_ok(){
int i,j;
for (i=1;i<=n;i++){
int cnt=0;
for (j=1;j<=n;j++){
if( map[i][j]) cnt++;
}
if( cnt % 2 != 0)
return 0;
}
for (j=1;j<=n;j++){
int cnt=0;
for (i=1;i<=n;i++){
if( map[i][j]) cnt++;
}
if( cnt % 2 != 0)
return 0;
}
return 1;
}
int main(){
scanf("%d",&n);
int i,j;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
scanf("%d",&map[i][j]);
}
}
if( is_ok()){
printf("OK");
return 0;
}
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
map[i][j] = !map[i][j];
if( is_ok()){
printf("%d %d\n",i,j);
return 0;
}
map[i][j] = !map[i][j];
}
}
printf("Corrupt");
return 0;
}复杂度
总结
Python代码
python
size = int(input())
matrix = [list(map(int, input().split())) for _ in range(size)]
odd_rows = [index for index, row in enumerate(matrix) if sum(row) % 2]
odd_columns = [index for index in range(size) if sum(matrix[row][index] for row in range(size)) % 2]
if not odd_rows and not odd_columns:
print("OK")
elif len(odd_rows) == len(odd_columns) == 1:
print(odd_rows[0] + 1, odd_columns[0] + 1)
else:
print("Corrupt")C++代码
cpp
#include <cstdio>
int m,n;
int map[200][200];
bool is_ok(){
int i,j;
for (i=1;i<=n;i++){
int cnt=0;
for (j=1;j<=n;j++){
if( map[i][j]) cnt++;
}
if( cnt % 2 != 0)
return 0;
}
for (j=1;j<=n;j++){
int cnt=0;
for (i=1;i<=n;i++){
if( map[i][j]) cnt++;
}
if( cnt % 2 != 0)
return 0;
}
return 1;
}
int main(){
scanf("%d",&n);
int i,j;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
scanf("%d",&map[i][j]);
}
}
if( is_ok()){
printf("OK");
return 0;
}
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
map[i][j] = !map[i][j];
if( is_ok()){
printf("%d %d\n",i,j);
return 0;
}
map[i][j] = !map[i][j];
}
}
printf("Corrupt");
return 0;
}复杂度
时间复杂度为
总结
先分析一次操作影响哪些不变量，可避免枚举所有翻转位置。