CF1720C Corners 题解

· · 题解

赛时因为把 m 写成 n 了，吃了好几次罚时……好在最后 AC 了。就当给大家做个提醒。

本题解题的关键点在于：如何让每次操作删除较少的 1？

我们定义一片“空区”为两个相邻的 0 或者在对角线上相邻的 0。即，它们有可能长这样：

00
0
0

也有可能长这样（用 x 代表未知元素）：

0
x0

如果是这样，我们每次就可以消去可以与它们构成“L 形”的某个 1。容易证明，除非整个矩阵不存在“空区”或全都是 0，否则这样的操作每次可以消去 1 个 1。

所以，如果整个矩阵刚开始存在空区，那么我们就可以让上面的操作一直执行下去，于是操作数就等于 1 的个数。

但，如果刚开始的时候没有“空区”怎么办？

很显然，进行 1 次任意操作后，必然会形成若干个“空区”。这是因为，操作后必然有若干个相邻的元素都是 0，而这也满足了我们形成“空区”的条件。

我们可以推出，如果整个矩阵刚开始没有“空区”，就分两种情况：有 0 和没有 0。

如果有 0 的话，就把其中某个 0 和另外某 2 个 1 形成“L 形”，就可以构造出“空区”，接下来就可以开始进行有“空区”时的操作，总操作数等于 1 的个数减去 1（第一次操作消去 2 个 1）。

类似地，如果刚开始全都是 1，就随便选择 3 个 1 消除，形成“空区”后操作，总操作数等于 1 的个数减去 2（第一次操作消去 3 个 1）。

所以，设 1 的个数为 C_1，记条件 R 为“矩阵初始时有空区”，那么总操作数 P 满足以下条件：

P=\begin{cases}C_1&R\\C_1-2&\forall a_{i,j}=1\\C_1-1&\operatorname{otherwise}\end{cases}

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,m,c=2,x=0; cin>>n>>m;
    vector<string> a(n+2,string(m+2,'0'));
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++){
        cin>>a[i][j];
        x+=(a[i][j]-=48); // 统计 1 的个数
        if(!a[i][j])c=1; // 有 0
      }
    for(int i=1;i<=m;i++)a[n+1][i]=1;
    for(int j=1;j<=n;j++)a[j][m+1]=1;
    a[n+1][m+1]=1; // 把边缘全部设为 1，方便处理
    for(int i=1;i<=n;i++){
      bool f=false;
      for(int j=1;j<=m;j++){
        if(!a[i][j]){
          if(!a[i+1][j]||!a[i][j+1]||!a[i+1][j+1]||(j>1&&!a[i+1][j-1])){
            c=0,f=true; break;
          } // 判断“空区”
        }
      }
      if(f)break;
    }
    cout<<x-c<<endl; // 减去 c 后输出
  }
  return 0;
}