题解 CF698D 【Limak and Shooting Points】
xht
2020-03-05 19:27:41
> [CF698D Limak and Shooting Points](https://codeforces.com/contest/698/problem/D)
## 题意
- 平面上有 $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$ 的「方案」定义的，因此实际上这个定义是一个递归定义，边界自然是没有障碍的情况。
回到我们的思路：枚举「顺序」和怪物，判断按照这个「顺序」能否击中怪物。
由于每种「方案」都定义了一个「顺序」，因此如果存在击中目标怪物「方案」，我们就一定可以枚举到它定义的「顺序」。
但现在还有两个问题：
1. 我们对「方案」定义了「顺序」，那一个「顺序」是否只唯一的对应了一个「方案」呢？
2. 如果一个「顺序」只唯一的对应了一个「方案」，我们如何通过「顺序」还原「方案」？
其实这两个问题是同一个问题，因为根据还原的过程可以发现一个「顺序」确实唯一的对应了一个「方案」。
下面是还原的过程：
> 假设某种「顺序」为 $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)$。
## 代码
```cpp
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;
}
```