当前位置: 代码迷 >> 综合 >> 1026. 皇后问题
  详细解决方案

1026. 皇后问题

热度:38   发布时间:2023-12-06 11:28:39.0

在这里插入图片描述
样例:
input:
3
1 1
1 2
1 3
output:
3

input:
2
1 1
2 2
output:
1

input:
4
1 3
2 1
3 4
4 2
output:
0
思路:
一开始的思路其实是想记录一下出现在某一行某一列的皇后个数,然后发现对角线的没有办法操作,所以把每个皇后能走到的位置都标记下来,这样就能算出有多少对,当然在题目所给的这个数据范围里,显然是会wa的,如果都是100以内的,那可以使用。
60分做法:

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n;
int num[11111][11111];
void mark(int x,int y)
{
    for(int i=1;i<=n;i++) num[x][i]++;for(int i=1;i<=n;i++) num[i][y]++;for(int i=1;i<n;i++){
    int tempx=x+i,tempy=y+i;if(tempx>n||tempy>n) break;num[tempx][tempy]++;}for(int i=1;i<n;i++){
    int tempx=x-i,tempy=y-i;if(tempx<1||tempy<1) break;num[tempx][tempy]++;}for(int i=1;i<n;i++){
    int tempx=x+i,tempy=y-i;if(tempx>n||tempy<1) break;num[tempx][tempy]++;}for(int i=1;i<n;i++){
    int tempx=x-i,tempy=y+i;if(tempx<1||tempy>n) break;num[tempx][tempy]++;}
}
int main()
{
    cin>>n;int x,y,cnt;for(int i=1;i<=n;i++){
    cin>>x>>y;if(num[x][y]!=0) cnt+=num[x][y];mark(x,y);//cout<<"i="<<i<<" "<<"cnt="<<cnt<<endl;}cout<<cnt<<endl;return 0;
}

然后经过指导发现一开始的思路是可行的,通过y+x,y-x来确定对角线(emmmm实际上这好像是个数学问题了)
tips:
1.a[-1]这种属于数组越界,数组的下标不能小于0
2.数据的强转:如果得到计算结果不是这个类型,需要在计算之前对数据进行处理,如果在计算之后对结果进行处理无济于事。

上满分代码:

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=444444;
int n;
int numx[maxn],numy[maxn],num1[maxn],num2[maxn];
int main()
{
    cin>>n;long long x,y,cnt;for(int i=1;i<=n;i++){
    cin>>x>>y;numx[x]++;numy[y]++;num1[y+x]++;num2[y-x+200000]++;}for(int i=1;i<=n;i++){
    cnt=cnt+((long long)numx[i]*(numx[i]-1)/2);cnt=cnt+((long long)numy[i]*(numy[i]-1)/2);}for(int i=2;i<=2*n;i++) cnt=cnt+((long long)num1[i]*(num1[i]-1)/2);for(int i=1-n+200000;i<=n-1+200000;i++) cnt=cnt+((long long)num2[i]*(num2[i]-1)/2);cout<<cnt<<endl;return 0;
}