CF698D Limak and Shooting Points 题解

CF698D Limak and Shooting Points

题意

平面上有 $k$ 个人和 $n$ 个怪物，每个人手中有一支箭。
每支箭可以往任意方向射出，击中这个方向上的第一个怪物后，箭和怪物都会消失。
问有多少怪物可能会被击中。
$k \le 7$ ， $n \le 10^3$ 。

题解

考虑枚举某种射击「顺序」和怪物，然后判断按照这个「顺序」能否击中怪物。

这里的「顺序」指的并不是射击时间的顺序（称之为「方案」）。对于一种「方案」，我们如下定义其「顺序」：

设这种「方案」为 $p_{1,2,\cdots,c}$ ，则 $p_c$ 就是最后击中目标怪物的人，之前都是在清理障碍。

假设障碍为 $x_{1,2,\dots,m}$ ，则 $p_{1,2,\dots,c-1}$ 可以被分成 $m$ 段，其中第 $i$ 段是清理障碍 $x_i$ 的「方案」。注意，击中某个怪物可能为多次清理障碍提供便利，因此段可以为空，如果单独把段拿出来也可能无法清理障碍。

这种「方案」对应的「顺序」为：

$p_c$ ，清理障碍 $x_1$ 的「顺序」，清理障碍 $x_2$ 的「顺序」， $\cdots$ ，清理障碍 $x_m$ 的「顺序」。

其中清理障碍 $x_i$ 的「顺序」是用清理障碍 $x_i$ 的「方案」定义的，因此实际上这个定义是一个递归定义，边界自然是没有障碍的情况。

回到我们的思路：枚举「顺序」和怪物，判断按照这个「顺序」能否击中怪物。

由于每种「方案」都定义了一个「顺序」，因此如果存在击中目标怪物「方案」，我们就一定可以枚举到它定义的「顺序」。

但现在还有两个问题：

我们对「方案」定义了「顺序」，那一个「顺序」是否只唯一的对应了一个「方案」呢？
如果一个「顺序」只唯一的对应了一个「方案」，我们如何通过「顺序」还原「方案」？

其实这两个问题是同一个问题，因为根据还原的过程可以发现一个「顺序」确实唯一的对应了一个「方案」。

下面是还原的过程：

假设某种「顺序」为 $q_{1,2,\dots,c}$ ，则击中目标怪物的人为 $q_1$ 。

在 $q_1$ 击中目标怪物的路上，如果有障碍，则障碍为 $x_{1,2,\dots,m}$ ，击中 $x_1$ 的人为 $q_2$ 。

在 $q_2$ 击中 $x_1$ 的路上，如果有障碍，则障碍为 $x_{2,\dots,?}$ ，击中 $x_2$ 的人为 $q_3$ 。

依次类推。

如果在某个 $q$ 击中某个 $x$ 的路上没有障碍，则回溯，可以发现还原的过程也是递归的。

由于还原的方式唯一，因此一个「顺序」唯一的对应了一个「方案」。

至此，我们算法的主体思路如下：

枚举「顺序」和怪物，通过还原「顺序」为「方案」的过程判断按照这个「顺序」能否击中怪物。

考虑时间复杂度，「顺序」的总个数是 $\mathcal O(k!)$ 的......吗？

好像不是，因为「顺序」的长度可能为 $1 \sim k$ 。

但是通过还原的过程可以发现，我们只用枚举所有长度为 $k$ 的「顺序」，如果这个「顺序」的某个前缀就是一种「方案」，是可以直接被判断出来的。

所以，重来一遍！

考虑时间复杂度，「顺序」的总个数是 $\mathcal O(k!)$ 的，怪物的总个数为 $\mathcal O(n)$ ，还原的过程复杂度为 $\mathcal O(k)$ ，总时间复杂度 $\mathcal O(nk!k)$ 。

代码

const int N = 1e3 + 7, K = 9;
int k, n, q[K], ans, t;
bool v[N];
pi a[K], b[N];
vi p[K][N], e;

inline bool pd(pi x, pi y, pi z) {
	if (y == z) return 0;
	if (z.fi < min(x.fi, y.fi) || z.fi > max(x.fi, y.fi)) return 0;
	if (z.se < min(x.se, y.se) || z.se > max(x.se, y.se)) return 0;
	return 1ll * (y.se - x.se) * (z.fi - x.fi) == 1ll * (z.se - x.se) * (y.fi - x.fi);
}

bool dfs(int x) {
	if (t > k) return 0;
	for (int y : p[q[t]][x])
		if (!v[y]) {
			++t;
			if (!dfs(y)) return 0;
		}
	return e.pb(x), v[x] = 1;
}

int main() {
	rd(k), rd(n);
	for (int i = 1; i <= k; i++) rd(a[i].fi), rd(a[i].se); 
	for (int i = 1; i <= n; i++) rd(b[i].fi), rd(b[i].se);
	for (int i = 1; i <= k; i++)
		for (int j = 1; j <= n; j++)
			for (int o = 1; o <= n; o++)
				if (pd(a[i], b[j], b[o])) {
					p[i][j].pb(o);
					if ((int)p[i][j].size() == k) break;
				}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) q[j] = j;
		do {
			while (e.size()) v[e.back()] = 0, e.pop_back();
			t = 1;
			if (dfs(i)) {
				++ans;
				break;
			}
		} while (next_permutation(q + 1, q + k + 1));
	}
	print(ans);
	return 0;
}

题意

题解

代码

评论