题解：P11168 「CMOI R1」First Town of This Journey／Grid Covering

晴空一鹤 · 2024-10-07 16:20:42 · 题解

本题最大难点在于要开 unsigned long long。

要求选的黑点最少，相当于要求选的白点最多。

考虑一个白点选了之后对问题有什么影响，显然与他挨着的行与列就不能选，否则连起来是不会经过黑点的。

然后就很容易想出构造方案，选择所有 (i,j)(i \equiv 1 \pmod 2,j \equiv 1 \pmod 2)，画个图可以发现这显然是满足要求的。

接下来考虑指定颜色：

• 指定一个点为黑点，如果它不在我们的初始方案上就不用管，如果在，考虑能否将初始方案向右或向下平移，不能答案要加 1。

• 指定一个点为白点，如果它在初始方案上就不用管，否则将初始方案略微平移过来即可。

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll n,m,a,b,x,ans,yyn,ym;
int main(){

  cin>>n>>m>>a>>b>>x;yyn=n,ym=m;
  if(x==0&&a%2==0)n--;
  if(x==0&&b%2==0)m--;
  if(x==1&&(a%2==1&&b%2==1&&n%2==1&&m%2==1))ans--;
  ans+=((n+1)/2)*((m+1)/2);
  cout<<yyn*ym-ans<<"\n";
}