杂谈

· · 题解

杂谈

由于一些题目发不出来，所以这里放一些能发出来的题目

没错大部分题目还是口胡的小朋友们不要学哦

题目一 带权并查集

虽然这个知识点非常的简单，但是蒟蒻没有写过，所以蒟蒻就来写一写。

P1196 银河英雄传说

题目描述：

自己看，懒得打了（逃）

题解：

题目大家都会，这里强调几个代码细节：

  1. 并查集的实现：
int finf(int x){
    if(fa[x] == x) return x;
    int k = fa[x]; fa[x] = finf(fa[x]);
    dis[now] += dis[k];
    return fa[x];
}

这里注意我们先存档了原来的父亲，然后统计dis的时候，要加上原来的父亲的dis。这里非常容易想错。而且小样例不易错大样例de不出

2.merge的实现

为了实现merge，我们需要额外维护一个集合 num_i 表示这个并查集的大小。在merge的时候，我们需要在 dis_u 上加上 num_i来维护被插入并查集的 dis 正确。

i = finf(i); j = finf(j);
if(i != j){
    fa[i] = j; dis[i] = num[j] + dis[i];
    num[j] += num[i]; num[i] = num[j];
}

题目二 P4145 上帝造题的七分钟2 / 花神游历各国

题目描述

当然也没有

题解

我们考虑这个操作非常的线段树，但是由于上次的惨痛经验我们完全不用尝试直接维护，这种信息是无法通过常规手段维护的。

我们考虑这个操作其实非常浪费，因为一个数最多被操作 \log n 次，然后就会一直为 1，我们考虑批量处理这些东西。

其实也非常简单，我们在线段树上每个节点维护一下这个节点是不是归零（准确的，归一）了，然后打上tag不下传即可。

题目三 P5889 跳树

题目描述

就是不写~

题解

蒟蒻不会做，但是蒟蒻会说：

一眼线段树，离线不下来所以我们考虑merge操作怎么办

相当于把左区间的点当做右区间操作的根节点，那么我们考虑会有哪几种情况：

综上，我们考虑如何记录这个相对位置。

具体实现上，我们考虑一个二叉树上两个相对位置如何唯一确定。

那么合并是简单的。然后蒟蒻口胡完了。

TIPS

虽然说蒟蒻基本上把题目口胡了七七八八，但是具体实现上有一些细节口胡的时候没有考虑到，在这种情况下下笔是非常危险的，所以也不算口胡成功了把。

总结一下这种题你要保证细节不出问题，你要考虑以下几个东西：

P.S. 如果没有修改，那么这道题大概率可以不用考虑线段树的合并了（直接线段树往往不行），可以考虑离线下来枚举右端点然后线段树维护区间答案等等套路维护一些不好合并的区间查询。

另：像上面花神游历各国，如果操作变成平方（线段树大爹+1）并且支持离线，那么可以考虑使用莫队/分块的离线算法维护。

ABC376F cycle(hard)

这道题蒟蒻考场上面想了好久把所有需要的trick都找到了但是最后还是没写出来然后对着3000的数量级打了一个 O(n) 的代码555555555

好了前言到此结束我们来看题目。

首先有一个非常显然的暴力，我们令 dp[i][j][k] 表示现在在第 i 个操作，左手在 j 位置，右手在 k 位置，我们需要的答案最少是多少。

不难发现上一步操作固定了一个位置，那么我们考虑去掉一维，然后用一个数组 dp[i][j] 表示现在在第 i 个操作，副手在 j 位置，我们需要的答案最少是多少。

但是这个时候复杂度仍然是 O(n^3)，因为我们要枚举原来副手的位置。我们不难发现一个状态有可能从好几个状态转移过来，我们不妨考虑我们这个状态能转移到哪几个状态。

由于我们现在知道我们现在的两只手在哪里，目标的一只手在哪里，那么此时我们能转移到的状态只能是逆时钟转到位置和顺时钟转到位置的两种终局状态。那么这个时候问题就解决了。细节比较多，根据实现方式，码量有不少差距。

ABC376G 宝藏猎人

首先这是一道非常显然的树上贪心。我们考虑分几步来求解：

  1. 去掉限制，考虑怎么做

如果不在树上，那么我们直接从大往小排序，然后贪心地选择。

  1. 列出式子

假设我们现在已经有了一个操作序列，那么我们考虑如何计算这个序列的价值。

那么有

ans = \sum_{i = 1}^{i <= n}{i * p_{q_i}}

其实 q 是我们操作序列，p 是每个点的概率。

  1. 考虑如何贪心

我们考虑贪心地选择操作。

在一个父节点，我们想要考虑哪一个儿子我们先搜完，那么我们考虑交换这两个儿子，然后通过上面的式子计算那个答案更小即可。在计算父亲答案的时候，我们可以假定儿子的答案已经求出。

在此基础上，我们考虑把贡献合并到父亲即可。由于我们不一定按照儿子父亲的顺序合并，所以我们需要维护一个并查集。

然后我们就愉快AC了。