欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF226D The table

程序员文章站 2024-02-07 09:39:16
题意 给出一个$n\times m$的矩阵,可以把某些行和某些列上面的数字变为相反数。问修改那些行和哪些列可以使得所有行和所有列之和都为非负数。 思路 ......

题目链接

题意

给出一个\(n\times m\)的矩阵,可以把某些行和某些列上面的数字变为相反数。问修改那些行和哪些列可以使得所有行和所有列之和都为非负数。

思路

每次将负数的行或者列变为相反数。因为矩阵上面的数字绝对值不超过\(100\),而每改变一次,最少使得整个矩阵和\(+2\),所以最多操作\(n\times m \times 100 = 10^6\)次。

代码

/*
* @author: wxyww
* @date: 2019-03-02 18:19:07
* @last modified time: 2019-03-02 18:54:53
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int n = 1100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a[n][n],sum[2][n],ans[2][n];
void work1(int x) {
    sum[0][x] = -sum[0][x]; 
    for(int i = 1;i <= m;++i) {
        sum[1][i] -= a[x][i];
        sum[1][i] += -a[x][i];
        a[x][i] = -a[x][i];
    }
}
void work2(int x) {
    sum[1][x] = -sum[1][x];
    for(int i = 1;i <= n;++i) {
        sum[0][i] -= a[i][x];
        sum[0][i] += -a[i][x];
        a[i][x] = -a[i][x];
    }
}
int main() {
    n = read(),m = read();
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            a[i][j] = read();
            sum[0][i] += a[i][j];
            sum[1][j] += a[i][j];
        }
    }
    while(1) {
        int bz = 0;
        for(int i = 1;i <= n;++i) 
            if(sum[0][i] < 0) work1(i),bz = 1,ans[0][i] ^= 1;
        for(int i = 1;i <= m;++i) 
            if(sum[1][i] < 0) work2(i),bz = 1,ans[1][i] ^= 1;
        if(!bz) break;
    }
    int js = 0;
    for(int i = 1;i <= n;++i) js += ans[0][i];
    printf("%d ",js);
    for(int i = 1;i <= n;++i) if(ans[0][i]) printf("%d ",i);
    js = 0;
    for(int i = 1;i <= m;++i) js += ans[1][i];
    puts("");
    printf("%d ",js);
    for(int i = 1;i <= m;++i) if(ans[1][i]) printf("%d ",i);
    return 0;
}
/*
5 10
-2 -7 -10 -9 5 -9 -3 8 -8 5
3 0 9 8 -4 -3 -8 1 8 1
2 3 7 5 -8 -3 0 -9 -7 -2
-6 -7 0 0 6 9 -8 6 -8 3
7 9 -4 -5 -9 -3 8 6 -5 6
*/