NC15295. m皇后
描述
输入描述
第一行两个整数n，m表示棋盘大小和皇后数量。
接下来m行每行两个整数ri，ci表示皇后坐标。
1 <= n, m <= 100,000
1 <= ri, ci <= n
数据保证没有皇后在同一个位置上。
输出描述
一行九个整数表示答案。
空格隔开，结尾无空格
示例1
输入:
8 4 4 3 4 8 6 5 1 6
输出:
0 3 0 1 0 0 0 0 0
示例2
输入:
10 3 1 1 1 2 1 3
输出:
0 2 1 0 0 0 0 0 0
C++(g++ 7.5.0) 解法, 执行用时: 466ms, 内存消耗: 31232K, 提交时间: 2022-11-06 17:41:03
#include<bits/stdc++.h>
using namespace std;
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MPD = (int)1e9+7;
const int MAXN = (int)1e5+5;
map<int,vector<pii> >vis[4];
int dx[] = {0,1,1,1};
int dy[] = {1,0,1,-1};
int ans[MAXN];
int mk[MAXN];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1; i<= m; i++){
int x,y;
cin >> x >> y;
for(int k = 0;k <4;k++)
{
vis[k][x*dx[k]+y*dy[k]].push_back(mp(k!=1?x:y,i));
}
}
for(int i = 0; i < 4; i++)
{
map<int,vector<pii> >::iterator it;
for(it = vis[i].begin();it != vis[i].end();it++)
{
vector<pii> ve = it -> second;
sort(ve.begin(),ve.end());
ans[ve.begin()->second]++;
ans[ve.back().second]++;
}
}
for(int i = 1; i <= m; i++)
{
mk[8-ans[i]]++;
}
for(int i = 0; i <= 8; i++)
{
printf("%d%c", mk[i],i!=8?' ':'\n');
}
}
Python3 解法, 执行用时: 1600ms, 内存消耗: 52096K, 提交时间: 2022-11-20 14:41:54
n,k=map(int,input().split())
dt={}
res,tmp=[],[]
for _ in range(k):
x,y=map(int,input().split())
dt[(x,y)]=0
res.append((x,y))
tmp=sorted(res)
for i in range(1,k):
if tmp[i][0]==tmp[i-1][0]:
dt[tmp[i-1]]+=1
dt[tmp[i]]+=1
tmp=sorted(res,key=lambda p:(p[1],p[0]))
for i in range(1,k):
if tmp[i][1]==tmp[i-1][1]:
dt[tmp[i-1]]+=1
dt[tmp[i]]+=1
tmp=[(x,y,x+y) for x,y in res]
#print(tmp)
tmp=sorted(tmp,key=lambda p:(p[2],p[0],p[1]))
for i in range(1,k):
if tmp[i][2]==tmp[i-1][2]:
dt[(tmp[i-1][0],tmp[i-1][1])]+=1
dt[(tmp[i][0],tmp[i][1])]+=1
tmp=[(x,y,x-y) for x,y in res]
tmp=sorted(tmp,key=lambda p:(p[2],p[0],p[1]))
for i in range(1,k):
if tmp[i][2]==tmp[i-1][2]:
dt[(tmp[i-1][0],tmp[i-1][1])]+=1
dt[(tmp[i][0],tmp[i][1])]+=1
tmp=list(dt.values())
for i in range(9):
print(tmp.count(i),end=' ')
C++14(g++5.4) 解法, 执行用时: 72ms, 内存消耗: 5956K, 提交时间: 2018-10-23 17:36:16
#include<bits/stdc++.h>
using namespace std;
const int N = 202000 + 5;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define mst(a,b) memset(a,b,sizeof(a))
typedef long long LL;
struct node{
int Max,Min;
}a[4][N];
int x[N],y[N];
void upd(node &t,int v) {
if( v < t.Min || t.Min == 0) {
t.Min = v;
}
t.Max = max(t.Max,v);
}
int num[10];
int main() {
int n,m;
scanf("%d %d",&n,&m);
rep(i,1,m) {
scanf("%d %d",&x[i],&y[i]);
upd(a[0][x[i]],y[i]);
upd(a[1][y[i]],x[i]);
upd(a[2][x[i]+y[i]],x[i]);
upd(a[3][x[i]-y[i]+n],x[i]);
}
rep(i,1,m) {
int ans = 8;
if(a[0][x[i]].Min == y[i]) ans--;
if(a[0][x[i]].Max == y[i]) ans--;
if(a[1][y[i]].Min == x[i]) ans--;
if(a[1][y[i]].Max == x[i]) ans--;
if(a[2][x[i]+y[i]].Min == x[i]) ans--;
if(a[2][x[i]+y[i]].Max == x[i]) ans--;
if(a[3][x[i]-y[i] + n].Min == x[i]) ans--;
if(a[3][x[i]-y[i] + n].Max == x[i]) ans--;
num[ans] ++;
}
rep(i,0,8) printf(i == 8?"%d":"%d ",num[i]);
}
C++11(clang++ 3.9) 解法, 执行用时: 650ms, 内存消耗: 31280K, 提交时间: 2020-02-29 15:59:36
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD=(int)1e9+7;
const int MAXN=(int)1e5+5;
map<int,vector<pii> >vis[4];
int dx[]={0,1,1,1};
int dy[]={1,0,1,-1};
int ans[MAXN];
int mk[MAXN];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
for(int k=0;k<4;k++)
{
vis[k][x*dx[k]+y*dy[k]].push_back(mp(k!=1?x:y,i));
}
}
for(int i=0;i<4;i++)
{
map<int,vector<pii> >:: iterator it;
for(it=vis[i].begin();it!=vis[i].end();it++)
{
vector<pii> ve=it->second;
sort(ve.begin(),ve.end());
ans[ve.begin()->second]++;
ans[ve.back().second]++;
}
}
for(int i=1;i<=m;i++)
{
mk[8-ans[i]]++;
}
for(int i=0;i<=8;i++)
{
printf("%d%c",mk[i],i!=8?' ':'\n');
}
return 0;
}