2021秋季《数据结构》_EOJ 1026.皇后问题

问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在$8\times 8$的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题可以推广为更一般的 $n\times n$ 皇后摆放问题：这时棋盘的大小变为 $n\times n$，而皇后个数也变成$n$ 。

现在给你 $n(1\le n\le 10^5)$个皇后的位置座标，问总共有多少对皇后互相冲突。

输入格式
第一行一个整数 ，表示有$n$个皇后。

接下来 $n$ 行，每行两个整数 $x,y(1\le x,y\le n)$ ，中间用空格分开，表示 $n$ 个皇后的坐标。

数据保证不会有两个皇后在同一个地方。

思路

（暴力遍历可行，不过时间规模达到1e10，超时。）
进行数据预处理，存储每一行、每一列、每一对角线的皇后个数，最后在O(n)规模下累加。
（不过如此一来空间复杂度高了不少）

• row[i]=j表示第i行有j个皇后，列同理；
• 使用截距对对角线进行处理
  截距可以用x,y表示，以截距为数组下标。

代码

在这里插入代码片#include<bits/stdc++.h>
using namespace std;// 对数据进行预处理，时间复杂度为O(n)
// 读入皇后struct，避免地图数组过大
typedef struct
{
    int x, y;
}Queen;Queen a[100002];long long Sum(long long x)  
// 注意此处的参数为long long
{
    if(x==1||x==0) return 0;elsereturn x*(x-1)/2;
}int main()
{
    int n; cin>>n;for(int i = 1; i <= n; i++){
    int x, y;cin>>x>>y;a[i].x = x, a[i].y = y;}// 对行、列、k<0的对角、k>0的对角分别讨论// 动态分配内存，防止内存空洞过大int* row = new int[n+2];     // row[i]=j表示第i行有j个皇后int* column = new int[n+2];// 对角线以y轴截距为下标存储，// 分别用x+y和y-x表示int* negK = new int[2*n+2];// y轴截距的范围为[0,2n]int* posK = new int[2*n+2];// y轴截距的范围为[-n,n]// 为了使得posK[i]=j表示截距为i的对角线有j个皇后，// 读入数据时用y-x+n进行平移for(int i = 1; i <= n; i++){
    row[i] = 0;column[i] = 0;}for(int i = 1; i <= 2*n; i++){
    negK[i] = 0;posK[i] = 0;}for(int i = 1; i <= n; i++)// 遍历每一个皇后{
    int x = a[i].x, y = a[i].y;column[x]++;row[y]++;negK[x+y]++;posK[y-x+n]++;}long long res = 0;for(int i = 1; i <= n; i++){
    res += (Sum(row[i])+Sum(column[i]));}for(int i = 1; i <= 2*n; i++){
    res += (Sum(negK[i])+Sum(posK[i]));}cout<<res<<endl;system("pause");return 0;
}