自动搬运

查看原文

来自洛谷，原作者为

	fkxr 看主页

搬运于2025-08-24 23:01:35，当前版本为作者最后更新于2024-07-31 16:13:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题是一题签到题。

题目大意是在一个二维平面中有 $n_1$ 个第一阵营的车和 $n_2$ 个第二阵营的车，求每个车是否会被攻击，一个车会被另一个车攻击的条件是：

1. 属于不同阵营；
2. $x$ 坐标相等或 $y$ 坐标相等
3. 他们中间没有其他车

我们可以建立结构体出存每个车的 $x$ 坐标、$y$ 坐标、所属阵营、序号，然后对他们的 $x$ 坐标排序，如果 $x$ 坐标相同，就对相同 $x$ 坐标的车的 $y$ 坐标进行排序，这样做可以让我们只用比较这个车的信息和上一个车的信息，看看他们可不可以互相攻击，反之亦然。

最终代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
bool ok[400005];

struct node {
	int x, y;
	int id;
	int z;
} a[400005];

bool cmp(node a1, node a2) {
	if (a1.x != a2.x) {
		return a1.x < a2.x;
	}
	return a1.y < a2.y;
}

bool cmpp(node a1, node a2) {
	if (a1.y != a2.y) {
		return a1.y < a2.y;
	}
	return a1.x < a2.x;
}

signed main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
		a[i].z = 0;
	}
	for (int i = n; i < n + m; i++) {
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
		a[i].z = 1;
	}
	sort(a, a + n + m, cmp);
	for (int i = 1; i < n + m; i++) {
		if (a[i - 1].x == a[i].x && a[i].z != a[i - 1].z) {
			ok[a[i].id] = 1;
			ok[a[i - 1].id] = 1;
		}
	}
	sort(a, a + n + m, cmpp);
	for (int i = 1; i < n + m; i++) {
		if (a[i - 1].y == a[i].y && a[i].z != a[i - 1].z) {
			ok[a[i].id] = 1;
			ok[a[i - 1].id] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		cout << ok[i];
	}
	cout << "\n";
	for (int i = n; i < m + n; i++) {
		cout << ok[i];
	}
	return 0;
}

AC记录