CF698D Limak and Shooting Points 题解

作者: xht37 分类: 题解 发布时间: 2020-03-05 19:23

点击数:45

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注