题解 P7315 【[COCI2018-2019#3] Sajam】
Computer1828
·
·
题解
一血。
先定义几个东西，方便后面叙述：
$A$ 表示操作 $1$ 和 $2$。
$B$ 表示操作 $3$。
$\sum h$ 表示某一行 `o` 的个数。
------------
假设有方案，显然存在一种是经过若干次 $A$ 后再 $B$，且在若干次 $A$ 后总 `o` 的数量不大于 $k$。
那么显然对于某一行，如果其 $\sum h > \dfrac{n}{2}$，那就进行 $A1$，下面称对于每一行都进行上述操作为 $X$。对于某一列同理，下称 $Y$。
然后对样例瞪眼，这里提供两种做法：
做法一：先 $Y$ 后 $X$，然后看全局 `o` 个数是否不大于 $k$。
然后对做法一的过程继续瞪眼就有做法二：
定义 $X'$ 为对于每一行，若其 $\sum h \leq \dfrac{n}{2}$，那么进行 $A1$。$Y'$ 同理。
那么做法二就是：$X'$，$Y'$，$X$，然后判断。
时间复杂度 $O(n^2)$。
代码：
```cpp
//x:1 o:0
//X
for(int i = 1;i<=n;++i){
int sum = 0;
for(int j = 1;j<=n;++j) sum += a[i][j];
if(sum>n/2){
for(int j = 1;j<=n;++j) a[i][j] ^= 1;
}
}
//Y
for(int i = 1;i<=n;++i){
int sum = 0;
for(int j = 1;j<=n;++j) sum += a[j][i];
if(sum>n/2){
for(int j = 1;j<=n;++j) a[j][i] ^= 1;
}
}
//X'
for(int i = 1;i<=n;++i){
int sum = 0;
for(int j = 1;j<=n;++j) sum += a[i][j];
if(sum<=n/2){
for(int j = 1;j<=n;++j) a[i][j] ^= 1;
}
}
//Y'
for(int i = 1;i<=n;++i){
int sum = 0;
for(int j = 1;j<=n;++j) sum += a[j][i];
if(sum<=n/2){
for(int j = 1;j<=n;++j) a[j][i] ^= 1;
}
}
```