题解：CF226D The table

正负君 · 2026-07-21 09:01:21 · 题解

正确地分析。

题意

给定一个 n \times m 的整数矩阵 a。你可以进行若干次以下操作：

1. 选定一行，取反这一行每个数字；
2. 选定一列，取反这一列每个数字。

请构造一个操作次数最少的操作序列，使得每一行和每一列中的数字之和都不为负数。

保证 1 \leq n,m \leq 100,|a_{i,j}|\leq100。

思路

每次反转，\sum_{i=1}^n\sum_{j=1}^ma_{i,j} 必然至少增加 2，因为最大的负整数为 -1，取反后变成 1。

而 -100^3\le\sum_{i=1}^n\sum_{j=1}^ma_{i,j}\le100^3，操作次数不会超过 10^6，单次修改时间复杂度为 O(n)，总时间复杂度为 O(n^4)。

显然操作顺序是可以调换的，那如果同一行或列操作了偶数次，就相当于没有操作。

::::success[代码]

#include<iostream>
#define int long long
using namespace std;
const int N=110;
int n,m,a[N][N],sum1[N],sum2[N],cnt1,cnt2,x[N],y[N];
bool flag;
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>m;
  for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j)
    {
      cin>>a[i][j];
      sum1[i]+=a[i][j];
      sum2[j]+=a[i][j];
    }
  while(true)
  {
    flag=false;
    for(int i=1; i<=n; ++i)if(sum1[i]<0)
      {
        flag=true;
        sum1[i]=-sum1[i];
        ++x[i];
        for(int j=1; j<=m; ++j)
        {
          sum2[j]-=2*a[i][j];
          a[i][j]=-a[i][j];
        }
      }
    for(int j=1; j<=m; ++j)if(sum2[j]<0)
      {
        flag=true;
        sum2[j]=-sum2[j];
        ++y[j];
        for(int i=1; i<=n; ++i)
        {
          sum1[i]-=2*a[i][j];
          a[i][j]=-a[i][j];
        }
      }
    if(!flag)break;
  }
  for(int i=1; i<=n; ++i)if(x[i]%2==1)++cnt1;
  for(int j=1; j<=m; ++j)if(y[j]%2==1)++cnt2;
  cout<<cnt1<<' ';
  for(int i=1; i<=n; ++i)if(x[i]%2==1)cout<<i<<' ';
  cout<<'\n'<<cnt2<<' ';
  for(int j=1; j<=m; ++j)if(y[j]%2==1)cout<<j<<' ';
  return 0;
}

::::