m皇后（牛客）
题目链接
本题：
https://ac.nowcoder.com/acm/problem/15295
“八皇后问题”题目链接：
NOI：
http://noi.openjudge.cn/ch0205/1700/
洛谷：
https://www.luogu.com.cn/problem/P1219
题目大意
棋盘上有若干皇后，每个皇后有八个方向，分别是上、下、左、右、左上、右上、左下、右下。存在其他皇后在此皇后的这八个方向，那么这个方向就是不安全的。
最后输出在0，1，2，3，4，5，6，7，8个方向上不安全的皇后的个数。
简单分析
- 看到这种皇后八个方向的问题，我们第一时间会想到的就是“八皇后问题”。从“八皇后问题”中，我们学到的一种方法：与主对角线（包含主对角线）平行的直线上点的横纵坐标之差为定值；与副对角线（包含副对角线）平行的直线上点的横纵坐标之和为定值。因此，对于本题也可以试试是否可以运用这个方法。
- 思考是否能暴力遍历？
暴力1：遍历每个点，暴力它的八个方向，有点就记录，时间复杂度的极限大概是O(10^10)，显然不行。
暴力2：遍历每个点，再确定其他点是否在它的八个方向上，有点就记录，时间复杂度的极限大概也是O(10^10)，显然不行。
既然无法完全暴力，我们就要思考一下技巧了。
-
我们尝试着从某个方向去遍历所有的点。
以确定某皇后左右是否安全为例：反映在图上，就是找此皇后的左边是否有皇后，右边是否有皇后。可以发现，此时，若此皇后左右存在不安全的其他皇后，那么这些皇后（包括此皇后）的横坐标都相同，不同的是纵坐标。再深度思考一下，也就是说，我们实际上比较的是与此皇后横坐标相同的皇后的纵坐标与此皇后的纵坐标的大小关系（这句话有点绕 ）。如果满足“横坐标与此皇后相同”的条件，且“其纵坐标小于此皇后的纵坐标”，那么就要标记此皇后的左侧是一个不安全的方向；如果满足“横坐标与此皇后相同”的条件，且“其纵坐标大于此皇后的纵坐标”，那么就要标记此皇后的右侧是一个不安全的方向。
进一步分析这个例子：如何高效的完成确定某皇后左右是否安全？这时我们要用到排序，按横坐标从小到大将所有皇后排序，横坐标相等的按纵坐标从小到大排序，从横坐标相等的里面比较纵坐标就行了。这样方便我们确定左右是否有其他皇后。（具体如何实现放在下一个标题下了）
- “确定某皇后左右是否安全”的例子探索完了，该解决其他方向上的了。类比一下，要是“确定某皇后上下是否安全”，我们就找与此皇后纵坐标相同的其他皇后，比较横坐标大小，进行记录；要是“确定一三象限角平分线是否安全”，我们就找与此皇后横纵坐标之和相同的其他皇后，比较横坐标大小（比较纵坐标也可以，本质就是找相对位置的关系），进行记录；要是“确定二四象限角平分线是否安全”，我们就找与此皇后横纵坐标之差相同的其他皇后，比较横坐标大小（括号内容同上），进行记录。
实现讲解
- 输入：
结构体输入，包括x，y，id。其中x表示横坐标，y表示纵坐标，id表示第id个皇后（就是为了给皇后编个号）
- 核心代码实现：
建立四个cmp函数，用于分上述四种情况去sort。每次排完序之后，我们遍历每个顺序遍历每个点。以确定某皇后左右是否安全为例，如果此点左边的点的横坐标与此点的横坐标相同，那么此点左边的点的纵坐标一定比此点小，因为咱们就是这么排的序，所以满足“此点左边的点的横坐标与此点的横坐标相同”就让cnt[此点id]++，cnt[此点左边的点的id]++，表示此点左边不安全，记录一下；此点左边的点的右边不安全，记录一下。以此循环。思考一下，其实被遍历的每个点的cnt最多加两次，一次是遍历到自己时，另一次是遍历到它后面的一个点时。当遍历到自己时，cnt[自己]++表示加上我左边不安全的情况；当遍历到自己的下一个点的时候（即自己作为当前遍历点的左边的点时）cnt[自己，即当前遍历点的左边的点]++表示自己右边不安全的情况。
其他三个情况类似，不再赘述。
- 输出
自己想办法输出cnt=0，1，2，3，4，5，6，7，8有几个就行了，很简单。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int book[10],cnt[N];
struct queen{
int x,y,id;
}q[N];
bool cmp1(queen a,queen b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(queen a,queen b){
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
bool cmp3(queen a,queen b){
if(a.x+a.y==b.x+b.y) return a.x<b.x;
return (a.x+a.y)<(b.x+b.y);
}
bool cmp4(queen a,queen b){
if(a.x-a.y==b.x-b.y) return a.x<b.x;
return (a.x-a.y)<(b.x-b.y);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>q[i].x>>q[i].y;
q[i].id=i;//进行编号，为了方便合并，输出
}
//四个方向上判断的代码如出一辙
//判断左右是否安全
sort(q+1,q+m+1,cmp1);
for(int i=2;i<=m;i++)
if(q[i].x==q[i-1].x)
{cnt[q[i].id]++;cnt[q[i-1].id]++;}
//判断上下是否安全
sort(q+1,q+m+1,cmp2);
for(int i=2;i<=m;i++)
if(q[i].y==q[i-1].y)
{cnt[q[i].id]++;cnt[q[i-1].id]++;}
//判断副对角线是否安全
sort(q+1,q+m+1,cmp3);
for(int i=2;i<=m;i++)
if(q[i].x+q[i].y==q[i-1].x+q[i-1].y)
{cnt[q[i].id]++;cnt[q[i-1].id]++;}
//判断主对角线是否安全
sort(q+1,q+m+1,cmp4);
for(int i=2;i<=m;i++)
if(q[i].x-q[i].y==q[i-1].x-q[i-1].y)
{cnt[q[i].id]++;cnt[q[i-1].id]++;}
//输出实现，book[i]记录的是不安全方向数为i的皇后个数
for(int i=1;i<=m;i++) {book[cnt[i]]++;}
for(int i=0;i<=8;i++) cout<<book[i]<<' ';
}
哔哔赖赖（读者忽略）
这部分一直是用来哔哔赖赖自己的，读者忽略就行，完全为了警醒自己。
首先，我没有AC，甚至可以说我不会，看了大佬的思路才写了写。用了lower & upper_bound，用错了，也不知道咋改，最后放弃了。与大佬一样的就是四个cmp函数。最后，好歹是临摹出来了（坚决不能照抄代码，和废人没什么区别）
再者，得有四五天没做题了，真的是惭愧，一直搞黑苹果，可算搞完了，以后要边复习课程边学算法，两不误。
总结一下本题中自己的问题所在：
1.主要问题在于自己的思维不够灵活，想不到要如何暴力，如何遍历。
2.代码的实现，这个比较前一个点与当前的点，这种遍历方式并没有想到，也就是没抓到这样暴力的本质：就俩方向，左/右，上/下……，说实话，这样遍历也挺巧妙的，不是我这种小白能达到的水平。要是双重循环的话时间复杂度必然不行。
最后的最后我想问上天一句：我什么时候才能成为大佬啊啊啊！！！
