Solution. CF512E Fox and Polygon

Description

定义一个 $n$ 边形的一种分割为用 $n-3$ 条对角线将多边形分为 $n-2$ 个三角形。

对于一条对角线 $(A,B)$，记与其相邻的两个三角形为 $\triangle ABC,\triangle ABD$。

定义翻转操作为删除对角线 $(A,B)$ 并添加对角线 $(C,D)$。

容易发现任意两种分割都能够通过翻转操作相互转换。

给出起始状态 $S$ 和终止状态 $T$，要求你在 $20000$ 步内将起始状态变换为终止状态。

$n\le1000$

Solution

既然任意两种状态之间都能够相互转换，那么我们考虑寻找一个中间状态 $M$，通过 $S\to M\to T$ 的方式完成转换。

同时我们还发现变换是可逆的，所以我们只需考虑如何将 $M$ 转换为其他状态，那么 $S\to M$ 的部分作逆变换即可。

在这道题中，最特殊的分割，我们可以考虑所有对角线都从 $1$ 出发的情况。

我们就将这种状态定义为 $M$，考虑此时从哪些对角线入手构造。

对于一条对角线 $(A,B)$ 定义 $dis$ 为 $|A-B|-1$。

不难发现，此时目标状态中所有 $dis=1$ 的对角线我们都能够通过一次翻转得到。

每做一次这样的操作，不难发现可以视作削掉了原来 $n$ 边形的一个角，边数 $-1$。

在所有 $k$ 条 $dis=1$ 的对角线构造完后，我们可以保证原来所有 $dis=2$ 的对角线在新的 $n-k$ 边形中 $dis=1$。

于是只需依次构造 $dis=1\to n-3$ 的对角线即可。

接下来考虑一下代码实现的细节，$S\to M$ 时只需考虑 $S$ 中 $dis=n-3\to1$ 的对角线，而 $M\to T$ 的部分，若想要构造 $T$ 中的一条对角线 $(P,Q)$，我们需要查询 $P,Q$ 之间还未作过翻转操作的点 $R$，对 $(1,R)$ 进行翻转操作，并将 $R$ 标记为已做过翻转操作，这一部分用 std::set 维护即可。

代码复杂度为 $O(n\log n)$，$\log$ 来自 std::set。

操作次数的上界为 $2n-6$，远低于 $20000$。

Code

namespace Main{
    int n, tot;
    struct line{
        int u, v;
        line() {}
        line(int u, int v): u(u), v(v) {}
    };
    vector<line> ans1[N], ans2[N];
    set<int> ext;
    void Main(){
        input(n);
        for(ri i = 0, u, v; i < n - 3; i++){
            input(u, v);
            if(u == 1 || v == 1) continue;
            if(u < v) swap(u, v);
            ans1[u - v].emplace_back(u, v);
            tot++;
        }
        for(ri i = 0, u, v; i < n - 3; i++){
            input(u, v);
            if(u == 1 || v == 1) continue;
            if(u < v) swap(u, v);
            ans2[u - v].emplace_back(u, v);
            tot++;
        }
        write(tot); puts("");
        for(ri i = N - 1; i; i--)
            for(line x: ans1[i])
                printf("%d %d\n", x.u, x.v);
        for(ri i = 3; i <= n - 1; i++) ext.emplace(i);
        for(ri i = 1; i < N; i++){
            for(line x: ans2[i]){
                set<int>::iterator iter = ext.upper_bound(x.v);
                printf("%d %d\n", 1, *iter);
                ext.erase(iter);
            }
        }
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。