题解 P3682 【[CERC2016]自由的套娃 Free Figurines】

· · 题解

这题主要要把套娃的拆开合并的方式模拟清楚，手动模拟一下会简单很多。

首先我们考虑一种最简单的完成任务的方法：把套娃全部拆开，然后再合并成所要求的样子，那么原来有父亲的都要拆开一次，把最后要求有父亲的都合并一次。

显然这样不是最优解，原来和现在状态都一样的，我们就不必拆开。一个例子：5个套娃连成这样的形状（套娃的关系用链表示）：（1最小，5最大）

1-2-3-4-5

假设我们要拆出3，其他的不变，得到如下的形状：

1-2-4-5\quad 3

那么1-2显然不用拆开，但4-5需要拆开来再装上，才能拿出3，那么我们的步骤就是：拆掉5，拆掉4，拆掉3，拼上4，拼上5，共5步

我们发现，在一条链中，我们只能保留最小的一部分，其他只要有所更改，套娃更大的部分就不能保留（要拆开才能能取到里面）。因此找出每条链最小的部分就是不用拆开的部分（如这个例子中的1-2），两个套娃不用拆开，就可以把原来做法的答案减2（拆开一次，拼上一次），就可以最优化答案了。实际操作时，找到在原始状态和目标状态中都是最小的套娃开始向大的去找，直到发现不同就可以了

时间复杂度O(n)

code:

#include <cstdio>

int a[100005], b[100005];
bool ntail[100005]; //表示i不是链的结尾

int main(){
    int n, ans = 0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        ntail[a[i]] = true; //已经不是链的结尾（最小的套娃）了
        if(a[i] != 0) ans++; //原始做法
    }
    for(int i=1; i<=n; i++){ //同上
        scanf("%d", &b[i]);
        ntail[b[i]] = true;
        if(b[i] != 0) ans++;
    }
    int p;
    for(int i=1; i<=n; i++){
        if(!ntail[i]){ //是链尾
            p = i;
            while(a[p] == b[p] && a[p] != 0 && b[p] != 0){ //一直找相同（可以不拆开的）
                ans -= 2; //避免2次操作
                p = a[p];
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

思路来自: 官方题解 BlackJack_的博客