[COTS/CETS 2020] 辣椒 Sadnice 题解

· · 题解

Izborne Pripreme 最喜欢出的组合构造。下文中使用了官方题解内的部分图片。

由于绳索形成了该网格图的一个生成树，每切断一条边连通块的个数就会 +1，所以最后我们只需要让被切断的边最少。

试图求出答案的一个下界：总共有 (NM+N+M) 条边，有 N 行和 M 列可以被选择切断，根据基础的不等式知识，下界为 L=\left\lceil\dfrac{NM+N+M}{N+M}\right\rceil=\left\lceil\dfrac{NM}{N+M}\right\rceil+1。下面我们提出一种构造，使得对于所有 N\le M，这个下界都可以被取到。

首先考虑一个基本结构：令辣椒的行、列编号从 0 开始，对于编号为偶数的行，将整行横着连起来，对于最右边的一列（即第 M 列），将整列竖着连起来，如下图：

接着考虑将奇数行的辣椒向上 / 下 / 右连边以形成生成树，由于每一“行”（这里带引号的“行”指绳索的行）最多放 (L-1) 个竖向绳索，所以我们对于每一“行”都放 (L-1) 条绳索，并且为了让横向绳索不至于重叠过多，这些竖向绳索需要尽量“错开”放置，如下图：

即对于奇数行，从上一个奇数行往上 / 下连边的最后一列往后一列开始，向上依次连 (L-1) 条边，接着向下连 (L-1) 条边，如果到 (M-1) 列了就回到第 0 列继续……对于其他没有往上 / 下连边的就直接往右连，这样连通性是可以保证的。特别的，如果最后一行是奇数行，那么显然不能往下连，此时直接往右连即可。

观察到上面往右连的绳索也是尽量错开的，又由于 N\le M，于是经过计算得出横向绳索的答案并不会超过下界，而竖向绳索的答案根据上面的构造必然不会超过下界。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,m,k; cin>>n>>m,k=(n*m-1)/(n+m)+1;
  // 这里 k 为上文所述的 (L - 1)
  vector s(n<<1|1,string(m*3+1,32));
  for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
      s[i<<1][j*3]='o';
  auto connect=[&](int x,int y,int op){
    if(op)s[(x<<1)+op][y*3]='|';
    else s[x<<1][y*3+1]=s[x<<1][y*3+2]='-';
    /* 连边：
     * op = 0 表示向右连
     * op = 1 表示向下连
     * op = -1 表示向上连
     */
  };
  for(int i=0;i<=n;i++){
    if(i&1){
      for(int j=0;j<m;j++){
        int x=((i-1)*k+j)%m;
        if(j<k)connect(i,x,-1);
        else if(j<k<<1&&i<n)connect(i,x,1);
        else connect(i,x,0);
      }
    }
    else for(int j=0;j<m;j++)
      connect(i,j,0);
    if(i<n)connect(i,m,1);
  }
  for(auto r:s)cout<<r<<'\n';
  return 0;
}