[ABC377F] Avoid Queen Attack 题解

本题因为棋子数量少，可以采用和 C 题类似的思路，从已有的棋子出发，去计算不能放棋子的格子数量。

难点在于，皇后的攻击范围是沿着 8 个方向延伸的。所以我们不能简单地用一个 set 来存放不能放棋子的格子坐标。我们只能每次考虑新的皇后攻击范围和之前的皇后有哪些点重复，这样我 们就可以不断地往不能放棋子的格子数量中加上（原本能攻击到的格子数量 $-$ 已经被之前考虑的皇后攻击过的格子）即可。

实现上，可以先用 B 题的思路考虑纵横两个方向上有哪些格子会被攻击，计算剩余的格子数量。 然后再考虑一条对角线，用对角线长度减去和之前纵横两个方向上重复的格子数量，再将答案减去这个结果。最后再考虑另一条对角线，用对角线长度减去和之前所有方向上重复的格子数量， 再将答案减去这个结果即可。

AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	int n,q;
	cin>>n>>q;
	set<int> h,v,d1,d2; // d1 存 i+j=d 的对角线，d2 存 i-j=d 的对角线
	for(int k=1,i,j;k<=q;k++){
	    cin>>i>>j;
	    h.insert(i);
	    v.insert(j);
	    d1.insert(i+j);
	    d2.insert(i-j);
	 }
	ll ans=1ll*(n-h.size())*(n-v.size());
	for(int d:d1){ // i+j=d 的对角线
	    set<int> s; // 记录已经被算过的行坐标
	    for(int i:h){ // 找到所有和该对角线相交的水平线
	        if(1<=d-i&&d-i<=n){
	            s.insert(i);
	        }
	    }
	    for(int j:v){ // 找到所有和该对角线相交的垂直线
	        if(1<=d-j&&d-j<=n){
	            s.insert(d-j);
	        }
	    }
	    int len=0;
	    if(d<=n+1){ // 在左上部分, 列坐标只能取1~d-1
	        len=d-1;
	    }else{ // 在右下部分，列坐标只能取d-n~n
	        len=n-(d-n)+1;
	    }
	    ans-=len-s.size();
	}
	for(int d:d2){ // i-j=d 的对角线
	    set<int> s; // 记录已经被算过的行坐标
	    for(int i:h){ // 找到所有和该对角线相交的水平线
	        if(1<=i-d&&i-d<=n){
	            s.insert(i);
	        }
	    }
	    for(int j:v){ // 找到所有和该对角线相交的垂直线
	        if(1<=j+d&&j+d<=n){
	            s.insert(j+d);
	        }
	    }
	    for(int e:d1){ // i-j=d i+j=e => i=(d+e)/2 j=(e-d)/2
	        if((d+e)%2) continue; // 不相交
	        int si=(d+e)/2,sj=(e-d)/2;
	        if(si>=1&&si<=n&&sj>=1&&sj<=n){
	            s.insert(si);
	        }
	    }
		int len=0;
		if(d>=0){ // i>=j 在左下部分，列坐标只能取1~n-d
			len=n-d;
		}else{ // 在右上部分，列坐标只能取1-d~n
			len=n-(1-d)+1;
		}
		ans-=len-s.size();
	}
	cout<<ans;
	return 0;
}

$\textit{\textmd Write by @xpz0525 }$$\textit{\textmd On November 6, 2024}$