Visits: 251

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$ 的「方案」定义的，因此实际上这个定义是一个递归定义，边界自然是没有障碍的情况。

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

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

但现在还有两个问题：

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)$。

代码

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;
}