组合最值之主教问题 / QOJ7178 Bishops 题解

FFTotoro · 2024-06-04 16:59:46 · 算法·理论

题意简述

在一个 n\times m 的棋盘上放置若干主教，使其两两互不攻击。问最多能放置多少个主教。

题目解法

证明答案上界

显然可以将黑格和白格分开考虑，对于某个颜色答案有一个上界，为该颜色的主对角线和副对角线的条数的较小值；但是对于某些情况，单种颜色的上界还需要在其基础上 -1，将其记为 u。对于 n 和 m 的奇偶性分类讨论（可以画出棋盘进行推导）：

n 和 m 均为偶数

单种颜色的上界为两种对角线条数的较小值即 u=\dfrac{1}{2}(n+m)-1，故答案上界为 2u=n+m-2。

n 和 m 均为奇数

分两种情况讨论：当 n=m 时，单种颜色的上界为主对角线数量即 u=\dfrac{1}{2}(n+m)-1，故答案上界为 2u=n+m-2；当 n\ne m 时，显然两种颜色的格子数目不同，其中一种颜色的上界为 u_0=\dfrac{1}{2}(n+m)，另一种颜色的上界为 u_1=\dfrac{1}{2}(n+m)-1，故答案上界为 u_0+u_1=n+m-1。

n 和 m 奇偶性不同

单种颜色的上界为 u=\dfrac{1}{2}(n+m-1)，故答案上界为 2u=n+m-1。

构造方法

不妨设 n\ge m。考虑依次进行如下构造：

• 选择所有最左边一列能选的所有格子；
• 选择所有最右边一列能选的所有格子；
• 选择最中间的 1 行（n 为奇数）/ 2 行（n 为偶数）能选的所有格子，在这些格子中靠左的优先选择。

分类可知以上的构造都可以达到上界。

参考代码

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int h,w; bool f=false; cin>>h>>w;
  if(h>w)f=true,swap(h,w);
  vector<pair<int,int> > r;
  set<int> p,m;
  auto I=[&](int x,int y){
    if(p.find(x+y)==p.end()&&m.find(x-y)==m.end())
      p.emplace(x+y),m.emplace(x-y),r.emplace_back(x,y);
  };
  for(int i=0;i<h;i++)I(i,0);
  for(int i=0;i<h;i++)I(i,w-1);
  for(int i=0;i<w;i++)I(h-1>>1,i),I(h>>1,i);
  cout<<r.size()<<endl;
  if(f)for(auto &[x,y]:r)swap(x,y);
  for(auto [x,y]:r)cout<<x+1<<' '<<y+1<<'\n';
  return 0;
}