Yet Another Task with Queens
思路
我可能写的十分暴力吧,直接四次\(sort\),每一次sort进行一次手动\(unique\)判重。
不难发现每个皇后有八个攻击方向,但是大概可以合并为四大类:
- \(x\)方向的
- \(y\)方向的
- 斜向上\(45°\)角的
- 斜向下\(45°\)角的
当我们按照上面的四大类分别排好顺序之后,在同一条直线上的一定会连在一起,这个时候两端的只能攻击一个,在中间的可以同时攻击两个,就类似于一遍\(unique\)操作。
如何把x相同的放在一起,这个时候我们\(sort\)的条件就是\(x\)从小到达排,我们为了保证其首位顺序,\(x\)相等的时候按照\(y\)从小到大排序
如何把y相同的放在一起,这个时候我们\(sort\)的条件就是\(y\)从小到达排,我们为了保证其首位顺序,\(y\)相等的时候按照\(x\)从小到大排序
如何把斜向上\(45°\)角上的放在一起,我们发现在这条线上的坐标有一个共同的标志,就是\(x + y\)是相等的,我们为了保证其首位顺序,如果\(x + y\)相等我们按照\(x - y\)从小到达排序。
如何把斜向下\(45°\)角上的放在一起,我们发现在这条线上的坐标有一个共同的标志,就是\(x - y\)是相等的,我们为了保证其首位顺序,如果\(x - y\)相等我们按照\(x + y\)从小到达排序。
一定要注意这道题是输出9个数字,我就一开始一直输出8个数字,然后wa on test 1。
代码
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int id[N], n, m, num[N], ans[10];
struct point {
int x, y;
}a[N];
void init() {
for(int i = 1; i <= m; i++)
id[i] = i;
}
bool cmp1(int i, int j) {
if(a[i].x == a[j].x) return a[i].y < a[j].y;
return a[i].x < a[j].x;
}
bool cmp2(int i, int j) {
if(a[i].y == a[j].y) return a[i].x < a[j].x;
return a[i].y < a[j].y;
}
bool cmp3(int i, int j) {
if((a[i].x - a[i].y) == (a[j].x - a[j].y)) return (a[i].x + a[i].y) < (a[j].x + a[j].y);
return (a[i].x - a[i].y) < (a[j].x - a[j].y);
}
bool cmp4(int i, int j) {
if((a[i].x + a[i].y) == (a[j].x + a[j].y)) return (a[i].x - a[i].y) < (a[j].x - a[j].y);
return (a[i].x + a[i].y) < (a[j].x + a[j].y);
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d %d", &a[i].x, &a[i].y);
}
init();
sort(id + 1, id + 1 + m, cmp1);
int flag = 0;
for(int i = 1; i < m; i++) {//由于是判重i + 1所以这里不能直接到m,应该在最后单独判重。
if(!flag && a[id[i]].x == a[id[i + 1]].x) {
num[id[i]]++;
flag = 1;
}
else if(flag && a[id[i]].x == a[id[i + 1]].x)
num[id[i]] += 2;
else if(flag && a[id[i]].x != a[id[i + 1]].x) {
num[id[i]]++;
flag = 0;
}
}
if(a[id[m]].x == a[id[m - 1]].x && m != 1) num[id[m]]++;//单独判重。
init();
sort(id + 1, id + 1 + m, cmp2);
flag = 0;
for(int i = 1; i < m; i++) {
if(!flag && a[id[i]].y == a[id[i + 1]].y) {
num[id[i]]++;
flag = 1;
}
else if(flag && a[id[i]].y == a[id[i + 1]].y)
num[id[i]] += 2;
else if(flag && a[id[i]].y != a[id[i + 1]].y) {
num[id[i]]++;
flag = 0;
}
}
if(a[id[m]].y == a[id[m - 1]].y && m != 1) num[id[m]]++;
init();
sort(id + 1, id + 1 + m, cmp3);
flag = 0;
for(int i = 1; i < m; i++) {
if(!flag && (a[id[i]].x - a[id[i]].y) == (a[id[i + 1]].x - a[id[i + 1]].y)) {
num[id[i]]++;
flag = 1;
}
else if(flag && (a[id[i]].x - a[id[i]].y) == (a[id[i + 1]].x - a[id[i + 1]].y))
num[id[i]] += 2;
else if(flag && (a[id[i]].x - a[id[i]].y) != (a[id[i + 1]].x - a[id[i + 1]].y)) {
num[id[i]]++;
flag = 0;
}
}
if((a[id[m]].x - a[id[m]].y) == (a[id[m - 1]].x - a[id[m +- 1]].y) && m != 1) num[id[m]]++;
init();
sort(id + 1, id + 1 + m, cmp4);
flag = 0;
for(int i = 1; i < m; i++) {
if(!flag && (a[id[i]].x + a[id[i]].y) == (a[id[i + 1]].x + a[id[i + 1]].y)) {
num[id[i]]++;
flag = 1;
}
else if(flag && (a[id[i]].x + a[id[i]].y) == (a[id[i + 1]].x + a[id[i + 1]].y))
num[id[i]] += 2;
else if(flag && (a[id[i]].x + a[id[i]].y) != (a[id[i + 1]].x + a[id[i + 1]].y)) {
num[id[i]]++;
flag = 0;
}
}
if((a[id[m]].x + a[id[m]].y) == (a[id[m - 1]].x + a[id[m - 1]].y) && m != 1) num[id[m]]++;
for(int i = 1; i <= m; i++)
ans[num[id[i]]]++;
int is_od;
for(int i = 0; i <= 8; i++)
printf("%d ", ans[i]);
// puts("");
return 0;
}