首页 > 代码库 > 微软2017年预科生计划在线编程笔试第二场 Queen Attack

微软2017年预科生计划在线编程笔试第二场 Queen Attack

排序。

分别按照$x$,$y$以及对角线排序,统计一下方案数就可以了。

#include<bits/stdc++.h>using namespace std;int n;struct X{    int x,y;}s[100010];bool cmp1(X a, X b){    return a.x<b.x;}bool cmp2(X a, X b){    return a.y<b.y;}bool cmp3(X a, X b){    return a.x+a.y<b.x+b.y;}bool cmp4(X a, X b){    return a.y-a.x<b.y-b.x;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);    long long sum=0;    sort(s+1,s+1+n,cmp1);    long long a=1;    for(int i=2;i<=n;i++)    {        if(s[i].x==s[i-1].x) a++;        else        {            sum=sum+a*(a-1)/2;            a=1;        }    }    sum=sum+a*(a-1)/2;    sort(s+1,s+1+n,cmp2);    a=1;    for(int i=2;i<=n;i++)    {        if(s[i].y==s[i-1].y) a++;        else        {            sum=sum+a*(a-1)/2;            a=1;        }    }    sum=sum+a*(a-1)/2;    sort(s+1,s+1+n,cmp3);    a=1;    for(int i=2;i<=n;i++)    {        if(s[i].y+s[i].x==s[i-1].y+s[i-1].x) a++;        else        {            sum=sum+a*(a-1)/2;            a=1;        }    }    sum=sum+a*(a-1)/2;    sort(s+1,s+1+n,cmp4);    a=1;    for(int i=2;i<=n;i++)    {        if(s[i].y-s[i].x==s[i-1].y-s[i-1].x) a++;        else        {            sum=sum+a*(a-1)/2;            a=1;        }    }    sum=sum+a*(a-1)/2;    printf("%lld\n",sum);    return 0;}

 

微软2017年预科生计划在线编程笔试第二场 Queen Attack