20241101 模拟赛

· · 个人记录

A. 操作 (opt)

通过观察和猜测可以发现，选择最靠左的那个转轮概率一定是越大越好，那么就选 a_i 最小且最靠左的，原因是：一旦选择了下一个转轮，概率就要乘上上个转轮转到相等数带来的 \dfrac{1}{10}，所以概率大的往后放一定不会更优，a_i 小的要靠前放。选择完当前的 a_i 之后，就变成了一个 [i+1,n] 的子问题了，循环下去做即可。

提交记录

B. 树 (tree)

关键结论：一个点在树上距离它最远的点一定是直径的一端。 所以需要维护树直径的两端。

[提交记录](http://218.5.5.242:9019/contest/submission/148537) # [C. 翻转 (rev)](http://218.5.5.242:9019/contest/872/problem/3) 对一个数操作过后，它与相邻的数的绝对值之差会由 $|A_i - A_{i + 1}|$ 变为 $|A_i + A_{i + 1}|$，所以考虑对于这 $n - 1$ 个空隙，我们视作 $n - 1$ 张卡牌，正面是 $|A_i - A_{i + 1}|$，反面是 $|A_i + A_{i+1}|$。对一个位置 $\times -1$ 的操作就变为翻转相邻两张卡牌。 再观察可以发现，对于一段区间 $\times -1$，其实只对左右两端产生了影响，中间的差的绝对值是没有改变的，所以区间 $\times - 1$ 操作就变成了翻转任意两张卡牌。 那接下来的问题就变为了求最少的翻转卡牌次数，使得正面朝上的数字互不相同。把反面向正面连有向边，边的指向就代表了这张卡牌的选择。 建图后形成了很多个连通块。连通块可能有树、基环树、图（额就是边数大于点数的图）。由鸽巢原理可知，一条边必须对应一个点，所以对于第三种情况，一定会存在多条边对应同一个点，所以无解。 基环树的情况，只有两种可能，就是环方向选择逆时针或顺时针，环上的树一定是外向树，对于这两种情况都算一遍，取最小值即可。 树的情况，发现最终情况一定有一个节点入度为 $0$，形成一棵外向树，枚举这个点是不行的，考虑换根 DP，记 $f_i$ 表示 $i$ 为根的子树形成外向树需要翻转多少条边。第二遍 dfs 的时候计算每个点的答案即可。 这样所有的情况就讨论完了，最后需要翻转的最少边数记作 $cnt$，最后的操作次数就是 $\left\lfloor \dfrac{cnt+1}{2} \right\rfloor$。 实现上有很多的细节，比如边的方向我是用一个 map 去存储的，就把有向图换成无向图，后期方便遍历。基环树的找环 dfs 跑一遍，记上一个点 pre，找到访问过的点就跳 pre……真正自己手写一遍才能体会到这题的魅力！ [提交记录](http://218.5.5.242:9019/contest/submission/148582) # [D. 最小值 (min)](http://218.5.5.242:9019/contest/872/problem/4)