正題

CF226D

---

題目大意

給一個n*m的矩陣，每次操作可以使一行或一列全部變號（+變-，-變+），問如何操作可以使所有行列之和都是正數

---

解題思路

考慮每次暴力找小于0的一行或一列，然后反轉

因為每次反轉肯定會使數字之和至少加2，且$a_i\le 100$，數字之和最小為-1e6，最多反轉到1e6，所以最多反轉1e6次

時間復雜度 $O(n^4)$

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 110 using namespace std; int n,m,pp,sum,a[N][N],s1[N],s2[N],q[N],qq[N]; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){scanf("%d",&a[i][j]);s1[i]+=a[i][j];s2[j]+=a[i][j];}while(1){pp=0;for(int i=1;i<=n&&!pp;++i)if(s1[i]<0)pp=i;if(pp){q[pp]^=1;for(int i=1;i<=m;++i){s1[pp]-=a[pp][i]*2;s2[i]-=a[pp][i]*2;a[pp][i]*=-1;}}else{for(int i=1;i<=m&&!pp;++i)if(s2[i]<0)pp=i;if(pp){qq[pp]^=1;for(int i=1;i<=n;++i){s1[i]-=a[i][pp]*2;s2[pp]-=a[i][pp]*2;a[i][pp]*=-1;}}else break;}}sum=0;for(int i=1;i<=n;++i)if(q[i])sum++;printf("%d",sum);for(int i=1;i<=n;++i)if(q[i])printf(" %d",i);putchar(10);sum=0;for(int i=1;i<=m;++i)if(qq[i])sum++;printf("%d",sum);for(int i=1;i<=m;++i)if(qq[i])printf(" %d",i);return 0; }

總結

以上是生活随笔為你收集整理的The table（CF226D）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。